Equilibria in Quantitative Reachability Games

[en] In this paper, we study turn-based quantitative multiplayer non zero-sum games played on finite graphs with reachability objectives. In this framework each player aims at reaching his own goal as soon as possible. We prove existence of finite-memory Nash (resp. secure) equilibria in multiplayer (resp. two-player) games.

Research center :

CREMMI - Modélisation mathématique et informatique

Disciplines :

Electrical & electronics engineering

Author, co-author :

Brihaye, Thomas ; Université de Mons > Faculté des Sciences > Mathématiques effectives

Bruyère, Véronique ; Université de Mons > Faculté des Sciences > Service d'Informatique théorique

De Pril, Julie ; Université de Mons > Faculté des Sciences > Mathématiques effectives

Language :

English

Title :

Equilibria in Quantitative Reachability Games

Publication date :

01 June 2010

Event name :

Computer Science Symposium in Russia

Event place :

Kazan, Russia

Event date :

2010

Research unit :

S820 - Mathématiques effectives
S829 - Informatique théorique

Research institute :

R300 - Institut de Recherche en Technologies de l'Information et Sciences de l'Informatique
R150 - Institut de Recherche sur les Systèmes Complexes

Available on ORBi UMONS :

since 10 July 2010

Statistics

Number of views

1 (0 by UMONS)

Number of downloads

0 (0 by UMONS)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

OpenCitations

Bibliography

Alur, R., Kanade, A., Weiss, G.: Ranking automata and games for prioritized requirements. In: Gupta, A., Malik, S. (eds.) CAV 2008. LNCS, vol. 5123, pp. 240-253. Springer, Heidelberg (2008)
Bloem, R., Chatterjee, K., Henzinger, T., Jobstmann, B.: Better quality in synthesis through quantitative objectives. In: Bouajjani, A., Maler, O. (eds.) CAV 2009. LNCS, vol. 5643, pp. 140-156. Springer, Heidelberg (2009)
Boros, E., Gurvich, V.:Why chess and back gammon can be solved in pure positional uniformly optimal strategies. Rutcor Research Report 21-2009, Rutgers University (2009)
Brihaye, T., Bruyère, V., De Pril, J.: Equilibria in Quantitative Reachability Games. Technical Report 122 (2010), http://www.ulb.ac.be/di/ssd/ cfv/TechReps/TechRep-CFV-2010-122.pdf
Chatterjee, K., Henzinger, T., Jurdziński, M.: Games with secure equilibria. Theoretical Computer Science 365(1-2), 67-82 (2006)
Chatterjee, K., Henzinger, T.A.: Finitary winning in omega-regular games. In: Hermanns, H., Palsberg, J. (eds.) TACAS 2006. LNCS, vol. 3920, pp. 257-271. Springer, Heidelberg (2006)
Clarke, E., Grumberg, O., Peled, D.:Model Checking.MIT Press, Cambridge (2000)
Grädel, E., Thomas, W., Wilke, T.: Automata, Logics, and Infinite Games. LNCS, vol. 2500. Springer, Heidelberg (2002)
Grädel, E., Ummels, M.: Solution concepts and algorithms for infinite multiplayer games. In: Apt,K., van Rooij, R. (eds.) New Perspectives on Games and Interaction, Texts in Logic and Games, vol. 4, pp. 151-178. Amsterdam University Press (2008)
Hopcroft, J.E., Ullman, J.D.: Introduction to automata theory, languages, and computation. Addison-Wesley Series in Computer Science. Addison-Wesley Publishing Co., Reading (1979)
Horn, F., Thomas, W., Wallmeier, N.: Optimal strategy synthesis in request-response games. In: Cha, S(S.), Choi, J.-Y., Kim,M., Lee, I., Viswanathan,M. (eds.) ATVA 2008. LNCS, vol. 5311, pp. 361-373. Springer, Heidelberg (2008)
Kuhn, H.: Extensive games and the problem of information. Classics in Game Theory, 46-68 (1953)
Nash, J.: Equilibrium points in n-person games. Proceedings of the National Academy of Sciences of the United States of America 36(1), 48-49 (1950)
Osborne, M., Rubinstein, A.: A course in game theory. MIT Press, Cambridge (1994)
Thomas, W.: On the synthesis of strategies in infinite games. In: Mayr, E.W., Puech, C. (eds.) STACS 1995. LNCS, vol. 900, pp. 1-13. Springer, Heidelberg (1995)
Zimmermann, M.: Time-optimal winning strategies for poset games. In: Maneth, S. (ed.) CIAA 2009. LNCS, vol. 5642, pp. 217-226. Springer, Heidelberg (2009)