From winning strategy to Nash equilibrium

Mathematical Logic Quarterly 60 (4-5):354-371 (2014)
  Copy   BIBTEX

Abstract

Game theory is usually considered applied mathematics, but a few game‐theoretic results, such as Borel determinacy, were developed by mathematicians for mathematics in a broad sense. These results usually state determinacy, i.e., the existence of a winning strategy in games that involve two players and two outcomes saying who wins. In a multi‐outcome setting, the notion of winning strategy is irrelevant yet usually replaced faithfully with the notion of (pure) Nash equilibrium. This article shows that every determinacy result over an arbitrary game structure, e.g., a tree, is transferable into existence of multi‐outcome (pure) Nash equilibrium over the same game structure. The equilibrium‐transfer theorem requires cardinal or order‐theoretic conditions on the strategy sets and the preferences, respectively, whereas counter‐examples show that every requirement is relevant, albeit possibly improvable. When the outcomes are finitely many, the proof provides an algorithm computing a Nash equilibrium without significant complexity loss compared to the two‐outcome case. As examples of application, this article generalises Borel determinacy, positional determinacy of parity games, and finite‐memory determinacy of Muller games.

Other Versions

No versions found

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 100,290

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Games with Unknown Past.Bakhadyr Khoussainov, Alexander Yakhnis & Vladimir Yakhnis - 1998 - Mathematical Logic Quarterly 44 (2):185-204.
The Determinacy of Context-Free Games.Olivier Finkel - 2013 - Journal of Symbolic Logic 78 (4):1115-1134.

Analytics

Added to PP
2015-09-03

Downloads
20 (#1,027,515)

6 months
8 (#549,811)

Historical graph of downloads
How can I increase my downloads?