Finding Approximate Nash Equilibria of Bimatrix Games via Payoff Queries
Open Access
- 26 August 2016
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Economics and Computation
- Vol. 4 (4) , 1-19
Abstract
We study the deterministic and randomized query complexity of finding approximate equilibria in a k × k bimatrix game. We show that the deterministic query complexity of finding an ϵ-Nash equilibrium when ϵ < ½ is Ω( k 2 ), even in zero-one constant-sum games. In combination with previous results [Fearnley et al. 2013], this provides a complete characterization of the deterministic query complexity of approximate Nash equilibria. We also study randomized querying algorithms. We give a randomized algorithm for finding a (3-√5/2 + ϵ)-Nash equilibrium using O ( k .log k /ϵ 2 ) payoff queries, which shows that the ½ barrier for deterministic algorithms can be broken by randomization. For well-supported Nash equilibria (WSNE), we first give a randomized algorithm for finding an ϵ-WSNE of a zero-sum bimatrix game using O ( k .log k /ϵ 4 ) payoff queries, and we then use this to obtain a randomized algorithm for finding a (⅔ + ϵ)-WSNE in a general bimatrix game using O ( k .log k /ϵ 4 ) payoff queries. Finally, we initiate the study of lower bounds against randomized algorithms in the context of bimatrix games, by showing that randomized algorithms require Ω( k 2 ) payoff queries in order to find an ϵ-Nash equilibrium with ϵ < 1/4 k , even in zero-one constant-sum games. In particular, this rules out query-efficient randomized algorithms for finding exact Nash equilibria.Keywords
All Related Versions
This publication has 17 references indexed in Scilit:
- Query Complexity of Correlated EquilibriumACM Transactions on Economics and Computation, 2015
- Polylogarithmic Supports Are Required for Approximate Well-Supported Nash Equilibria below 2/32013
- Approximate Well-Supported Nash Equilibria Below Two-ThirdsLecture Notes in Computer Science, 2012
- New algorithms for approximate Nash equilibria in bimatrix gamesTheoretical Computer Science, 2010
- Settling the complexity of computing two-player Nash equilibriaJournal of the ACM, 2009
- Polynomial algorithms for approximating Nash equilibria of bimatrix gamesTheoretical Computer Science, 2009
- A note on approximate Nash equilibriaTheoretical Computer Science, 2009
- Well Supported Approximate Equilibria in Bimatrix GamesAlgorithmica, 2008
- An Optimization Approach for Approximate Nash EquilibriaInternet Mathematics, 2008
- Approximating nash equilibria using small-support strategies2007