On pure Nash equilibria in stochastic games. (English) Zbl 1461.91029
Jain, Rahul (ed.) et al., Theory and applications of models of computation. 12th annual conference, TAMC 2015, Singapore, May 18–20, 2015. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 9076, 359-371 (2015).
Summary: M. Ummels and D. Wojtczak [Lect. Notes Comput. Sci. 5556, 297–308 (2009; Zbl 1248.91016)] initiated the study of finding Nash equilibria in simple stochastic multi-player games satisfying specific bounds. They showed that deciding the existence of pure-strategy Nash equilibria (pureNE) where a fixed player wins almost surely is undecidable for games with \(9\) players. They also showed that the problem remains undecidable for the finite-strategy Nash equilibrium (finNE) with \(14\) players. In this paper, we improve their undecidability results by showing that pureNE and finNE problems remain undecidable for \(5\) or more players.
For the entire collection see [Zbl 1320.68020].
For the entire collection see [Zbl 1320.68020].
Citations:
Zbl 1248.91016References:
| [1] | Baier, C., Größer, M., Leucker, M., Bollig, B., Ciesinski, F.: Probabilistic controller synthesis. In: International Conference on Theoretical Computer Science, IFIP TCS 2004, pp. 493-506. Kluwer Academic Publishers (2004) · Zbl 1073.93037 |
| [2] | Bouyer, P., Markey, N., Stan, D.: Mixed Nash equilibria in concurrent games. In: FSTTCS (to appear, 2014) · Zbl 1360.91041 |
| [3] | Chatterjee, K.; Majumdar, R.; Jurdziński, M.; Marcinkowski, J.; Tarlecki, A., On nash equilibria in stochastic games, Computer Science Logic, 26-40 (2004), Heidelberg: Springer, Heidelberg · Zbl 1095.91001 · doi:10.1007/978-3-540-30124-0_6 |
| [4] | Chen, X.; Deng, X.; Teng, S-H, Settling the complexity of computing two-player Nash equilibria, J. ACM, 56, 3, 1-57 (2009) · Zbl 1325.68095 · doi:10.1145/1516512.1516516 |
| [5] | Condon, A., On algorithms for simple stochastic games, Adv. Comput. Complex. Theor., 13, 51-73 (1993) · Zbl 0808.90141 |
| [6] | Conitzer, V., Sandholm, T.: Complexity results about Nash equilibria. In: Proceedings of the 18th International Joint Conference on Artificial Intelligence, IJCAI 2003, pp. 765-771. Morgan Kaufmann (2003) · Zbl 1142.91365 |
| [7] | Daskalakis, C.; Goldberg, PW; Papadimitriou, CH, The complexity of computing a Nash equilibrium, SIAM J. Comput., 39, 1, 195-259 (2009) · Zbl 1185.91019 · doi:10.1137/070699652 |
| [8] | Nash, JF, Equilibrium points in \({N}\)-person games, Proc. National Acad. Sci. USA, 36, 48-49 (1950) · Zbl 0036.01104 · doi:10.1073/pnas.36.1.48 |
| [9] | Neyman, A.; Sorin, S., Stochastic Games and Applications (2003), Berlin: Springer, Berlin · Zbl 1027.00040 |
| [10] | Ummels, M.; Amadio, RM, The complexity of Nash equilibria in infinite multiplayer games, Foundations of Software Science and Computational Structures, 20-34 (2008), Heidelberg: Springer, Heidelberg · Zbl 1138.91359 · doi:10.1007/978-3-540-78499-9_3 |
| [11] | Ummels, M.; Wojtczak, D.; Albers, S.; Marchetti-Spaccamela, A.; Matias, Y.; Nikoletseas, S.; Thomas, W., The complexity of Nash equilibria in simple stochastic multiplayer games, Automata, Languages and Programming, 297-308 (2009), Heidelberg: Springer, Heidelberg · Zbl 1248.91016 · doi:10.1007/978-3-642-02930-1_25 |
| [12] | Ummels, M.; Wojtczak, D.; Katoen, J-P; König, B., The complexity of Nash equilibria in limit-average games, CONCUR 2011 - Concurrency Theory, 482-496 (2011), Heidelberg: Springer, Heidelberg · Zbl 1343.68177 · doi:10.1007/978-3-642-23217-6_32 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
