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

    This entry is not archived by us. If you are the author and have permission from the publisher, we recommend that you archive it. Many publishers automatically grant permission to authors to archive pre-prints. By uploading a copy of your work, you will enable us to better index it, making it easier to find.

    Upload a copy of this work     Papers currently archived: 105,859

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
26 (#943,550)

6 months
10 (#383,285)

Historical graph of downloads
How can I increase my downloads?