Abstract
We consider concurrent games played on graphs, in which each player has several qualitative (e.g. reachability or Büchi) objectives, and a preorder on these objectives (for instance the counting order, where the aim is to maximise the number of objectives that are fulfilled).
We study two fundamental problems in that setting: (1) the value problem, which aims at deciding the existence of a strategy that ensures a given payoff; (2) the Nash equilibrium problem, where we want to decide the existence of a Nash equilibrium (possibly with a condition on the payoffs). We characterise the exact complexities of these problems for several relevant preorders, and several kinds of objectives.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Alur, R., Henzinger, T.A., Kupferman, O.: Alternating-time temporal logic. J. ACM 49(5), 672–713 (2002)
Bouyer, P., Brenguier, R., Markey, N.: Nash Equilibria for Reachability Objectives in Multi-player Timed Games. In: Gastin, P., Laroussinie, F. (eds.) CONCUR 2010. LNCS, vol. 6269, pp. 192–206. Springer, Heidelberg (2010)
Bouyer, P., Brenguier, R., Markey, N., Ummels, M.: Concurrent games with ordered objectives. Research Report LSV-11-22, LSV, ENS Cachan, France (2011)
Bouyer, P., Brenguier, R., Markey, N., Ummels, M.: Nash equilibria in concurrent games with Büchi objectives. In: FSTTCS 2011. LIPIcs, vol. 13, pp. 375–386. Leibniz-Zentrum für Informatik, LZI (2011)
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)
Henzinger, T.A.: Games in system design and verification. In: TARK 2005, pp. 1–4 (2005)
Hunter, P., Dawar, A.: Complexity Bounds for Regular Games. In: Jedrzejowicz, J., Szepietowski, A. (eds.) MFCS 2005. LNCS, vol. 3618, pp. 495–506. Springer, Heidelberg (2005)
Jurdzinski, M.: Deciding the winner in parity games is in UP ∩ co-UP. Inf. Process. Lett. 68(3), 119–124 (1998)
Laroussinie, F., Markey, N., Oreiby, G.: On the expressiveness and complexity of ATL. Logicical Methods in Computer Science 4(2) (2008)
McNaughton, R.: Infinite games played on finite graphs. Annals of Pure and Applied Logic 65(2), 149–184 (1993)
Nash Jr., J.F.: Equilibrium points in n-person games. Proc. National Academy of Sciences of the USA 36(1), 48–49 (1950)
Neumann, J., Szepietowski, A., Walukiewicz, I.: Complexity of weak acceptance conditions in tree automata. Inf. Process. Lett. 84(4), 181–187 (2002)
Papadimitriou, C.H.: Complexity Theory. Addison-Wesley (1994)
Paul, S., Simon, S.: Nash equilibrium in generalised Muller games. In: FSTTCS 2009. LIPIcs, vol. 4, pp. 335–346. LZI (2010)
Thomas, W.: Infinite Games and Verification (Extended abstract of a tutorial). In: Brinksma, E., Larsen, K.G. (eds.) CAV 2002. LNCS, vol. 2404, pp. 58–64. Springer, Heidelberg (2002)
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)
Ummels, M., Wojtczak, D.: The Complexity of Nash Equilibria in Limit-Average Games. In: Katoen, J.-P., König, B. (eds.) CONCUR 2011 – Concurrency Theory. LNCS, vol. 6901, pp. 482–496. Springer, Heidelberg (2011)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bouyer, P., Brenguier, R., Markey, N., Ummels, M. (2012). Concurrent Games with Ordered Objectives. In: Birkedal, L. (eds) Foundations of Software Science and Computational Structures. FoSSaCS 2012. Lecture Notes in Computer Science, vol 7213. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-28729-9_20
Download citation
DOI: https://doi.org/10.1007/978-3-642-28729-9_20
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-28728-2
Online ISBN: 978-3-642-28729-9
eBook Packages: Computer ScienceComputer Science (R0)