The Complexity of Nash Equilibria in Simple Stochastic Multiplayer Games | SpringerLink
Skip to main content

The Complexity of Nash Equilibria in Simple Stochastic Multiplayer Games

  • Conference paper
Automata, Languages and Programming (ICALP 2009)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 5556))

Included in the following conference series:

Abstract

We analyse the computational complexity of finding Nash equilibria in simple stochastic multiplayer games. We show that restricting the search space to equilibria whose payoffs fall into a certain interval may lead to undecidability. In particular, we prove that the following problem is undecidable: Given a game \(\mathcal G\), does there exist a pure-strategy Nash equilibrium of \(\mathcal G\) where player 0 wins with probability 1. Moreover, this problem remains undecidable if it is restricted to strategies with (unbounded) finite memory. However, if mixed strategies are allowed, decidability remains an open problem. One way to obtain a provably decidable variant of the problem is to restrict the strategies to be positional or stationary. For the complexity of these two problems, we obtain a common lower bound of NP and upper bounds of NP and PSpace respectively.

This research was supported by the DFG Research Training Group 1298 (AlgoSyn).

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 11439
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 14299
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Allender, E., Bürgisser, P., Kjeldgaard-Pedersen, J., Miltersen, P.B.: On the complexity of numerical analysis. In: Proc. CCC 2006, pp. 331–339. IEEE Computer Society Press, Los Alamitos (2006)

    Google Scholar 

  2. Brázdil, T., Brožek, V., Forejt, V., Kučera, A.: Stochastic games with branching-time winning objectives. In: Proc. LICS 2006, pp. 349–358. IEEE Computer Society Press, Los Alamitos (2006)

    Google Scholar 

  3. Canny, J.: Some algebraic and geometric computations in PSPACE. In: Proc. STOC 1988, pp. 460–469. ACM Press, New York (1988)

    Google Scholar 

  4. Chatterjee, K., Henzinger, T.A., Jurdziński, M.: Games with secure equilibria. Theoretical Computer Science 365(1-2), 67–82 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  5. Chatterjee, K., Jurdziński, M., Henzinger, T.A.: Quantitative stochastic parity games. In: Proc. SODA 2004, pp. 121–130. ACM Press, New York (2004)

    Google Scholar 

  6. Chatterjee, K., Majumdar, R., Jurdziński, M.: On Nash equilibria in stochastic games. In: Marcinkowski, J., Tarlecki, A. (eds.) CSL 2004. LNCS, vol. 3210, pp. 26–40. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

  7. Chen, X., Deng, X.: Settling the complexity of two-player Nash equilibrium. In: Proc. FOCS 2006, pp. 261–272. IEEE Computer Society Press, Los Alamitos (2006)

    Google Scholar 

  8. Condon, A.: The complexity of stochastic games. Information and Computation 96(2), 203–224 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  9. Conitzer, V., Sandholm, T.: Complexity results about Nash equilibria. In: Proc. IJCAI 2003, pp. 765–771. Morgan Kaufmann, San Francisco (2003)

    Google Scholar 

  10. Daskalakis, C., Goldberg, P.W., Papadimitriou, C.H.: The complexity of computing a Nash equilibrium. In: Proc. STOC 2006, pp. 71–78. ACM Press, New York (2006)

    Google Scholar 

  11. de Alfaro, L., Henzinger, T.A.: Concurrent omega-regular games. In: Proc. LICS 2000, pp. 141–154. IEEE Computer Society Press, Los Alamitos (2000)

    Google Scholar 

  12. de Alfaro, L., Henzinger, T.A., Kupferman, O.: Concurrent reachability games. In: Proc. FOCS 1998, pp. 564–575. IEEE Computer Society Press, Los Alamitos (1998)

    Google Scholar 

  13. Etessami, K., Kwiatkowska, M.Z., Vardi, M.Y., Yannakakis, M.: Multi-objective model checking of Markov decision processes. Logical Methods in Computer Science 4(4) (2008)

    Google Scholar 

  14. Etessami, K., Yannakakis, M.: On the complexity of Nash equilibria and other fixed points. In: Proc. FOCS 2007, pp. 113–123. IEEE Computer Society Press, Los Alamitos (2007)

    Google Scholar 

  15. Filar, J., Vrieze, K.: Competitive Markov decision processes. Springer, Heidelberg (1997)

    MATH  Google Scholar 

  16. Garey, M.R., Graham, R.L., Johnson, D.S.: Some NP-complete geometric problems. In: Proc. STOC 1976, pp. 10–22. ACM Press, New York (1976)

    Google Scholar 

  17. Nash Jr., J.F.: Equilibrium points in N-person games. Proc. National Academy of Sciences of the USA 36, 48–49 (1950)

    Article  MathSciNet  MATH  Google Scholar 

  18. Neyman, A., Sorin, S. (eds.): Stochastic Games and Applications. NATO Science Series C, vol. 570. Springer, Heidelberg (1999)

    MATH  Google Scholar 

  19. Renegar, J.: On the computational complexity and geometry of the first-order theory of the reals. Journal of Symbolic Computation 13(3), 255–352 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  20. Selten, R.: Spieltheoretische Behandlung eines Oligopolmodells mit Nachfrageträgheit. Zeitschrift für die gesamte Staatswissenschaft 121, 301–324, 667–689 (1965)

    Google Scholar 

  21. Ummels, M.: Rational behaviour and strategy construction in infinite multiplayer games. In: Arun-Kumar, S., Garg, N. (eds.) FSTTCS 2006. LNCS, vol. 4337, pp. 212–223. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  22. Ummels, M.: The complexity of Nash equilibria in infinite multiplayer games. In: Amadio, R.M. (ed.) FOSSACS 2008. LNCS, vol. 4962, pp. 20–34. Springer, Heidelberg (2008)

    Chapter  Google Scholar 

  23. Ummels, M., Wojtczak, D.: The complexity of Nash equilibria in simple stochastic multiplayer games. Technical report, University of Edinburgh (2009)

    Google Scholar 

  24. Zielonka, W.: Perfect-information stochastic parity games. In: Walukiewicz, I. (ed.) FOSSACS 2004. LNCS, vol. 2987, pp. 499–513. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Editor information

Editors and Affiliations

Rights and permissions

Reprints and permissions

Copyright information

© 2009 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Ummels, M., Wojtczak, D. (2009). The Complexity of Nash Equilibria in Simple Stochastic Multiplayer Games. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds) Automata, Languages and Programming. ICALP 2009. Lecture Notes in Computer Science, vol 5556. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-02930-1_25

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-02930-1_25

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-02929-5

  • Online ISBN: 978-3-642-02930-1

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics