A symbolic shortest path algorithm for computing subgame-perfect Nash equilibria

DOI10.1515/AMCS-2015-0043MaRDI QIDQ747538zbMATH OpenOpenAlexFDO

Authors Pedro Arturo Góngora, David A. Rosenblueth

Publication date 16 October 2015

Published in International Journal of Applied Mathematics and Computer Science (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://doi.org/10.1515/amcs-2015-0043

zbMATH Keywords

model checkingNash equilibriumshortest pathbinary decision diagram (BDD)Bellman-Ford

Mathematics Subject Classification ID

Applications of graph theory (05C90) Noncooperative games (91A10) Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05)

Recommendations

• The complexity of subgame perfect equilibria in quantitative reachability games
• scientific article; zbMATH DE number 7649921
• Subgame perfection for equilibria in quantitative reachability games
• scientific article; zbMATH DE number 6767615
• Equilibrium computation for two-player games in strategic and extensive form

Cites work

• scientific article; zbMATH DE number 3870578 (Why is no real title available?)
• scientific article; zbMATH DE number 1099369 (Why is no real title available?)
• scientific article; zbMATH DE number 1150567 (Why is no real title available?)
• scientific article; zbMATH DE number 2063025 (Why is no real title available?)
• scientific article; zbMATH DE number 783783 (Why is no real title available?)
• scientific article; zbMATH DE number 7088727 (Why is no real title available?)
• scientific article; zbMATH DE number 5585443 (Why is no real title available?)
• A course in game theory.
• A survey on multi-constrained optimal path computation: exact and approximate algorithms
• Automatic verification of finite-state concurrent systems using temporal logic specifications
• Automatic verification of multi-agent systems by model checking via ordered binary decision diagrams
• Branching time, perfect information games, and backward induction
• Generating BDDs for symbolic model checking in CCS
• Graph-Based Algorithms for Boolean Function Manipulation
• Introduction to algorithms.
• Min-max Computation Tree Logic
• On the use of binary decision diagrams for solving problems on simple games
• Optimization and Multiobjective Control of Time-Discrete Systems
• Power indices of simple games and vector-weighted majority games by means of binary decision diagrams
• Selected Multicriteria Shortest Path Problems: An Analysis of Complexity, Models and Adaptation of Standard Algorithms
• Symbolic model checking: \(10^{20}\) states and beyond

Cited in

(3)

• Nonmonotone game labellings
• Programming and Verifying Subgame-Perfect Mechanisms
• A robust algorithm to solve the signal setting problem considering different traffic assignment approaches

Describes a project that uses

Uses Software

• Gambit

This page was built for publication: A symbolic shortest path algorithm for computing subgame-perfect Nash equilibria

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q747538)