Finding Approximate Nash Equilibria of Bimatrix Games via Payoff Queries



Fearnley, J and Savani, R ORCID: 0000-0003-1262-7831
(2016) Finding Approximate Nash Equilibria of Bimatrix Games via Payoff Queries. ACM Transactions on Economics and Computation (TEAC), 4 (4).

[img] Text
note.pdf - Accepted Version

Download (367kB)

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 Ω(k2), 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 Ω(k2) payoff queries in order to find an ϵ-Nash equilibrium with ϵ < 1/4k, even in zero-one constant-sum games. In particular, this rules out query-efficient randomized algorithms for finding exact Nash equilibria.

Item Type: Article
Additional Information: ## TULIP Type: Articles/Papers (Journal) ##
Uncontrolled Keywords: theory of computation, design and analysis of algorithms
Depositing User: Symplectic Admin
Date Deposited: 05 Jun 2017 06:22
Last Modified: 13 Sep 2021 23:10
DOI: 10.1145/2956579
Related URLs:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3007823