Approximate Well-supported Nash Equilibria Below Two-thirds

Fearnley, John, Goldberg, Paul W, Savani, Rahul ORCID: 0000-0003-1262-7831 and Sørensen, Troels Bjerre (2016) Approximate Well-supported Nash Equilibria Below Two-thirds Algorithmica, 76 (2). pp. 297-319. ISSN 0178-4617, 1432-0541

Text note.pdf - Author Accepted Manuscript Download (382kB) | Preview

Abstract

In an ϵ-Nash equilibrium, a player can gain at most ϵ by changing his behaviour. Recent work has addressed the question of how best to compute ϵ-Nash equilibria, and for what values of ϵ a polynomial-time algorithm exists. An ϵ-well-supported Nash equilibrium (ϵ-WSNE) has the additional requirement that any strategy that is used with non-zero probability by a player must have payoff at most ϵ less than a best response. A recent algorithm of Kontogiannis and Spirakis shows how to compute a 2/3-WSNE in polynomial time, for bimatrix games. Here we introduce a new technique that leads to an improvement to the worst-case approximation guarantee.

Item Type:	Article
Uncontrolled Keywords:	Bimatrix games, Nash equilibria, Well-supported approximate equilibria
Depositing User:	Symplectic Admin
Date Deposited:	09 Dec 2019 11:31
Last Modified:	01 Mar 2026 06:16
DOI:	10.1007/s00453-015-0029-3
Related Websites:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3065575
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.