Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Coherence Spaces and Uniform Continuity Kapitel lesen Erstes Kapitel lesen

2017 | OriginalPaper | Buchkapitel

On the Existence of Weak Subgame Perfect Equilibria

verfasst von : Véronique Bruyère, Stéphane Le Roux, Arno Pauly, Jean-François Raskin

Erschienen in: Foundations of Software Science and Computation Structures

Verlag: Springer Berlin Heidelberg

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

We study multi-player turn-based games played on a directed graph, where the number of players and vertices can be infinite. An outcome is assigned to every play of the game. Each player has a preference relation on the set of outcomes which allows him to compare plays. We focus on the recently introduced notion of weak subgame perfect equilibrium (weak SPE), a variant of the classical notion of SPE, where players who deviate can only use strategies deviating from their initial strategy in a finite number of histories. We give general conditions on the structure of the game graph and the preference relations of the players that guarantee the existence of a weak SPE, which moreover is finite-memory.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Vorheriges Kapitel Nominal Automata with Name Binding
Nächstes Kapitel Optimal Reachability in Divergent Weighted Timed Games
Fußnoten
1
Indexing \(Plays_G\) or \(Hist_G\) with G allows to recall the related game G.
 
2
The limit inferior can be used instead of the limit superior.
 
3
Moore machines are usually defined for finite sets V. We here allow infinite sets V.
 
4
In this article, we will always use notation \(\mu (h\rho )\) instead of \({\mu }_{|{h}}(\rho )\).
 
5
We suppose that \(o \prec _v \top \) for all \(o \in O_L\).
 
6
Ordinal 0 and each limit ordinal are even, and each successor ordinal \(\alpha + 1\) is even (resp. odd) if \(\alpha \) is odd (resp. even).
 
7
When V is finite, it is reached after at most \(2 |O_L| \cdot |V|\) steps.
 
8
The existence of leaves l with a unique outgoing edge (l, l) is abusive since the graph is a tree: it should be understood as a unique infinite play from l.
 
9
\(L\) is the prefix-free subset of \(L'\).
 
Literatur
1.
Berwanger, D.: Admissibility in infinite games. In: Thomas, W., Weil, P. (eds.) STACS 2007. LNCS, vol. 4393. Springer, Heidelberg (2007)CrossRef
2.
Brenguier, R., Clemente, L., Hunter, P., Pérez, G.A., Randour, M., Raskin, J.-F., Sankur, O., Sassolas, M.: Non-zero sum games for reactive synthesis. In: Dediu, A.-H., Janoušek, J., Martín-Vide, C., Truthe, B. (eds.) LATA 2016. LNCS, vol. 9618, pp. 3–23. Springer, Cham (2016). doi:10.​1007/​978-3-319-30000-9_​1 CrossRef
3.
Brenguier, R., Raskin, J.-F., Sankur, O.: Assume-admissible synthesis. In: CONCUR, LIPIcs, vol. 42, pp. 100–113. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2015)
4.
Brenguier, R., Raskin, J.-F., Sassolas, M.: The complexity of admissibility in omega-regular games. In: CSL-LICS, pp. 23:1–23:10. ACM (2014)
5.
Brihaye, T., Bruyère, V., Meunier, N., Raskin, J.-F.: Weak subgame perfect equilibria and their application to quantitative reachability. In: CSL, LIPIcs, vol. 41, pp. 504–518. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2015)
6.
Bruyère, V., Meunier, N., Raskin, J.-F.: Secure equilibria in weighted games. In: CSL-LICS, pp. 26:1–26:26. ACM (2014)
7.
8.
Chatterjee, K., Doyen, L., Filiot, E., Raskin, J.-F.: Doomsday equilibria for omega-regular games. In: McMillan, K.L., Rival, X. (eds.) VMCAI 2014. LNCS, vol. 8318, pp. 78–97. Springer, Heidelberg (2014). doi:10.​1007/​978-3-642-54013-4_​5 CrossRef
9.
10.
11.
Pril, J., Flesch, J., Kuipers, J., Schoenmakers, G., Vrieze, K.: Existence of secure equilibrium in multi-player games with perfect information. In: Csuhaj-Varjú, E., Dietzfelbinger, M., Ésik, Z. (eds.) MFCS 2014. LNCS, vol. 8635, pp. 213–225. Springer, Heidelberg (2014). doi:10.​1007/​978-3-662-44465-8_​19
12.
Flesch, J., Kuipers, J., Mashiah-Yaakovi, A., Schoenmakers, G., Solan, E., Vrieze, K.: Perfect-information games with lower-semicontinuous payoffs. Math. Oper. Res. 35, 742–755 (2010)MathSciNetCrossRefMATH
13.
Flesch, J., Predtetchinski, A.: A characterization of subgame perfect equilibrium plays in borel games of perfect information. Math. Oper. Res. (2017, to appear)
14.
Fudenberg, D., Levine, D.: Subgame-perfect equilibria of finite- and infinite-horizon games. J. Econ. Theor. 31, 251–268 (1983)MathSciNetCrossRefMATH
15.
Grädel, E., Ummels, M.: Solution concepts and algorithms for infinite multiplayer games. In: New Perspectives on Games and Interaction, vol. 4, pp. 151–178. University Press, Amsterdam (2008)
16.
Kuhn, H.W.: Extensive games and the problem of information, pp. 46–68. Classics in Game Theory (1953)
17.
Kupferman, O., Perelli, G., Vardi, M.Y.: Synthesis with rational environments. Ann. Math. Artif. Intell. 78(1), 3–20 (2016)MathSciNetCrossRefMATH
18.
Le Roux, S.: Infinite subgame perfect equilibrium in the Hausdorff difference. In: Hajiaghayi, M.T., Mousavi, M.R. (eds.) TTCS 2015. LNCS, vol. 9541, pp. 147–163. Springer, Cham (2016)CrossRef
19.
Le Roux, S., Pauly, A.: Infinite sequential games with real-valued payoffs. In: CSL-LICS, pp. 62:1–62:10. ACM (2014)
20.
Nash, J.F.: Equilibrium points in \(n\)-person games. In: PNAS, vol. 36, pp. 48–49. National Academy of Sciences (1950)
21.
Pnueli, A., Rosner, R.: On the synthesis of a reactive module. In: POPL, pp. 179–190. ACM Press (1989)
22.
Purves, R.A., Sudderth, W.D.: Perfect information games with upper semicontinuous payoffs. Math. Oper. Res. 36(3), 468–473 (2011)MathSciNetCrossRefMATH
23.
Rubinstein, A.: Comments on the interpretation of game theory. Econometrica 59, 909–924 (1991)CrossRef
24.
Selten, R.: Spieltheoretische Behandlung eines Oligopolmodells mit Nachfrageträgheit. Zeitschrift für die gesamte Staatswissenschaft 121, 301–324, 667–689 (1965)
25.
Shen, X.S., Yu, H., Buford, J., Akon, M.: Handbook of Peer-to-Peer Networking. Springer, Heidelberg (2010)CrossRefMATH
26.
27.
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). doi:10.​1007/​11944836_​21 CrossRef
Metadaten
Titel
On the Existence of Weak Subgame Perfect Equilibria
verfasst von
Véronique Bruyère
Stéphane Le Roux
Arno Pauly
Jean-François Raskin
Copyright-Jahr
2017
Verlag
Springer Berlin Heidelberg
Buch
Foundations of Software Science and Computation Structures

Print ISBN: 978-3-662-54457-0

Electronic ISBN: 978-3-662-54458-7

Copyright-Jahr: 2017

DOI
https://doi.org/10.1007/978-3-662-54458-7_9