Byrski, Aleksander - ed. ; Kisiel-Dorohinicki, Marek - ed. ; Dobrowolski, Grzegorz - ed.
Consider games where players wish to minimize the cost to reach some state. A subgame-perfect Nash equilibrium can be regarded as a collection of optimal paths on such games. Similarly, the well-known state-labeling algorithm used in model checking can be viewed as computing optimal paths on a Kripke structure, where each path has a minimum number of transitions. ; We exploit these similarities in a common generalization of extensive games and Kripke structures that we name "graph games". By extending the Bellman-Ford algorithm for computing shortest paths, we obtain a model-checking algorithm for graph games with respect to formulas in an appropriate logic. Hence, when given a certain formula, our model-checking algorithm computes the subgame-perfect Nash equilibrium (as opposed to simply determining whether or not a given collection of paths is a Nash equilibrium). ; Next, we develop a symbolic version of our model checker allowing us to handle larger graph games. We illustrate our formalism on the critical-path method as well as games with perfect information. Finally, we report on the execution time of benchmarks of an implementation of our algorithms.
Zielona Góra: Uniwersytet Zielonogórski
AMCS, volume 25, number 3 (2015) ; click here to follow the link
Biblioteka Uniwersytetu Zielonogórskiego
May 6, 2024
May 6, 2024
27
https://www.zbc.uz.zgora.pl/publication/88904
Edition name | Date |
---|---|
A symbolic shortest path algorithm for computing subgame-perfect Nash equilibria | May 6, 2024 |
Clempner, Julio Korbicz, Józef (1951- ) - red. Uciński, Dariusz - red.
Tarapata, Zbigniew Korbicz, Józef (1951- ) - red.
Karpowicz, Michał P. Cordón, Oskar - ed. Kazienko, Przemysław - ed.
Speck, Andreas Pulvermüller, Elke Jerger, Michael Franczyk, Bogdan Korbicz, Józef (1951- ) - red. Uciński, Dariusz - red.
Opara, Adam Kania, Dariusz Korbicz, Józef (1951- ) - red. Uciński, Dariusz - red.