Abstract
In his dissertation of 1950, Nash based his concept of the solution to a game on the assumption that “a rational prediction should be unique, that the players should be able to deduce and make use of it”. We study when such definitive solutions exist for strategic games with ordinal payoffs. We offer a new, syntactic approach: instead of reasoning about the specific model of a game, we deduce properties of interest directly from the description of the game itself. This captures Nash’s deductive assumptions and helps to bridge a well-known gap between syntactic game descriptions and specific models which could require unwarranted additional epistemic assumptions, e.g., common knowledge of a model. We show that games without Nash equilibria do not have definitive solutions under any notion of rationality, but each Nash equilibrium can be a definitive solution for an appropriate refinement of Aumann rationality. With respect to Aumann rationality itself, games with multiple Nash equilibria cannot have definitive solutions. Some games with a unique Nash equilibrium have definitive solutions, others don’t, and the criterion for a definitive solution is provided by the iterated deletion of strictly dominated strategies.
To Johan.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
This phenomenon is well known to logicians as ‘non-categoricity’.
- 2.
cf. Sect. 17.7.4.
- 3.
This observation does not concern so-called computer knowledge when the programmer can program specific models to each computer.
- 4.
By the same token, we use rigorous yet informal reasoning to establish the Pythagorean theorem, though such a proof could be completely formalized and derived in an axiomatic geometry.
- 5.
We continue our analogy with the Pythagorean theorem: one could try to formalize its proof completely only as a challenge or an exercise. A normal mathematically rigorous proof of it is not formal.
- 6.
Such as reflexivity and positive and negative introspection.
- 7.
This obvious observation, technically speaking, follows from Theorem 17.3.
- 8.
If player 1 knows that player 2 defects, then 1 knows that 2 is rational.
- 9.
Which is equivalent to the knowledge-based rationality studied in [3].
- 10.
Following Harsanyi’s principle from [18] Sects. 6.2 and 6.3, Postulate A1.
- 11.
Otherwise, \(B\) would know that \(S\) is rational.
- 12.
Note that a default assumption that GAME is consistent is necessary since for inconsistent games, vacuously, each profile is a definitive solution.
- 13.
The name is analogous to “bullet voting”, in which the voter can vote for multiple candidates but votes for only one.
- 14.
This is the standard requirement of “measurability,” cf. [8].
References
Apt K, Zvesper J (2010) Proof-theoretic analysis of rationality for strategic games with arbitrary strategy sets. In: Dix J, Leite J, Governatori G, Jamroga W (eds) Computational logic in multi-agent systems. Proceedings of the 11th international workshop, CLIMA XI, Lisbon, Portugal, August 16–17, 2010. Lecture Notes in Artificial Intelligence, vol 6245, pp 186–199
Artemov S (2001) Explicit provability and constructive semantics. Bull Symb Log 7(1):1–36
Artemov S (2009) Knowledge-based rational decisions. Technical Report TR-2009011, CUNY Ph.D. Program in Computer Science
Artemov S (2010) The impossibility of definitive solutions in some games. Technical Report TR-2010003, CUNY Ph.D. Program in Computer Science
Artemov S, Kuznets R (2006) Logical omniscience via proof complexity. In: Ésik Z (ed) Proceedings of the 20th international workshop on computer science logic, CSL 2006. Lecture notes in computer science, vol 4207, pp 135–149
Artemov S, Kuznets R (2009) Logical omniscience as a computational complexity problem. In: Heifetz A (ed) Proceedings of the twelfth conference theoretical aspects of rationality and knowledge, (TARK 2009), Stanford University, California, ACM, pp 14–23
Aumann R (1976) Agreeing to disagree. Ann Stat 4(6):1236–1239
Aumann R (1995) Backward induction and common knowledge of rationality. Games Econ Behav 8:6–19
Aumann R (2010) Interview. In: Hendricks VF, Roy O (eds) Epistemic logic: 5 questions. Automatic Press/VIP, New York, pp 21–33
Aumann R, Brandenburger A (1995) Epistemic conditions for Nash equilibrium. Econometrica: J Econom Soc 64(5):1161–1180
van Benthem J (2007) Rational dynamics and epistemic logic in games. Int Game Theory Rev 9(1):1345
van Benthem J, Pacuit E, Roy O (2011) Toward a theory of play: a logical perspective on games and interaction. Games 2:52–86
Bonanno G (2008) A syntactic approach to rationality in games with ordinal payoffs. In: Bonanno G, van der Hoek W, Wooldridge M (eds) Logic and the foundations of game and decision theory, texts in logic and games series. Amsterdam University Press, Amsterdam, pp 59–86
de Bruin B (2010) Explaining games: the epistemic programme in game theory. Springer, Berlin
Fagin R, Halpern JY (1988) Belief, awareness, and limited reasoning. Artif Intell 34:39–76
Fagin R, Halpern J, Moses Y, Vardi M (1995) Reasoning about knowledge. MIT Press, Cambridge
Fitting M (2005) The logic of proofs, semantically. Ann Pure Appl Log 132(1):1–25
Harsanyi JC (1986) Rational behaviour and bargaining equilibrium in games and social situations. Cambridge Books, Cambridge
Nash J (1950) Non-cooperative games. Ph.D. Thesis, Princeton University, Princeton
Osborne M, Rubinstein A (1994) A course in game theory. The MIT Press, Cambridge
Pearce D (1984) Rationalizable strategic behavior and the problem of perfection. Econometrica: J Econom Soc 52(4):1029–1050
Renne B (2009) Propositional games with explicit strategies. Inf Comput 207(10):1015–1043
Sedlár I (2013) Justifications, awareness and epistemic dynamics. In: Artemov S, Nerode A (eds) Proceedings of the logical foundations of computer science, LFCS 2013. Lecture notes in computer science, vol 7734, pp 307–318
Acknowledgments
The author is grateful to Adam Brandenburger for drawing attention to Nash’s argument and supportive discussions. The author is indebted to Mel Fitting, Vladimir Krupski, Elena Nogina, Çağıl Taşdemir, and Johan van Benthem for many principal comments and suggestions. Special thanks to Karen Kletter for editing this text.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this chapter
Cite this chapter
Artemov, S. (2014). On Definitive Solutions of Strategic Games. In: Baltag, A., Smets, S. (eds) Johan van Benthem on Logic and Information Dynamics. Outstanding Contributions to Logic, vol 5. Springer, Cham. https://doi.org/10.1007/978-3-319-06025-5_17
Download citation
DOI: https://doi.org/10.1007/978-3-319-06025-5_17
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-06024-8
Online ISBN: 978-3-319-06025-5
eBook Packages: Humanities, Social Sciences and LawPhilosophy and Religion (R0)