Polylogarithmic supports are required for approximate well-supported Nash equilibria below 2/3

Anbalagan, Y, Norin, S, Savani, R ORCID: 0000-0003-1262-7831 and Vetta, A (2013) Polylogarithmic supports are required for approximate well-supported Nash equilibria below 2/3 In: The 9th Conference on Web and Internet Economics (WINE), 2013-12-11 - 2013-12-14, Harvard.

Text 1309.7258v2.pdf - Unspecified Download (788kB)

Abstract

In an ε-approximate Nash equilibrium, a player can gain at most ε in expectation by unilateral deviation. An ε-well-supported approximate Nash equilibrium has the stronger requirement that every pure strategy used with positive probability must have payoff within ε of the best response payoff. Daskalakis, Mehta and Papadimitriou [8] conjectured that every win-lose bimatrix game has a 2/3-well-supported Nash equilibrium that uses supports of cardinality at most three. Indeed, they showed that such an equilibrium will exist subject to the correctness of a graph-theoretic conjecture. Regardless of the correctness of this conjecture, we show that the barrier of a 2/3 payoff guarantee cannot be broken with constant size supports; we construct win-lose games that require supports of cardinality at least Ω(3√log n) in any ε-well supported equilibrium with ε < 2/3. The key tool in showing the validity of the construction is a proof of a bipartite digraph variant of the well-known Caccetta-Häggkvist conjecture [4]. A probabilistic argument [13] shows that there exist ε-well-supported equilibria with supports of cardinality O(1/ε²·log n), for any ε > 0; thus, the polylogarithmic cardinality bound presented cannot be greatly improved. We also show that for any δ > 0, there exist win-lose games for which no pair of strategies with support sizes at most two is a (1 - δ)-well-supported Nash equilibrium. In contrast, every bimatrix game with payoffs in [0,1] has a 1/2-approximate Nash equilibrium where the supports of the players have cardinality at most two [8]. © 2013 Springer-Verlag.

Item Type:	Conference Item (Paper)
Additional Information:	Added details on related work (footnote 7 expanded)
Uncontrolled Keywords:	cs.GT, cs.GT
Depositing User:	Symplectic Admin
Date Deposited:	28 Jan 2015 10:00
Last Modified:	24 Jan 2026 00:31
DOI:	10.1007/978-3-642-45046-4_2
Related Websites:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/2005760
Disclaimer:	The University of Liverpool is not responsible for content contained on other websites from links within repository metadata. Please contact us if you notice anything that appears incorrect or inappropriate.