NDLI: Finding Approximate Nash Equilibria of Bimatrix Games via Payoff Queries

Please wait, while we are loading the content...

Finding Approximate Nash Equilibria of Bimatrix Games via Payoff Queries

Content Provider	ACM Digital Library
Author	Savani, Rahul Fearnley, John
Copyright Year	2016
Abstract	We study the deterministic and randomized query complexity of finding approximate equilibria in a $\textit{k}$ × $\textit{k}$ bimatrix game. We show that the deterministic query complexity of finding an ε-Nash equilibrium when &epsilon < ½ 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™&sqrt;5/2 + ε)-Nash equilibrium using $\textit{O}(\textit{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 $\textit{O}(\textit{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 $\textit{O}(\textit{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\textit{k},$ even in zero-one constant-sum games. In particular, this rules out query-efficient randomized algorithms for finding exact Nash equilibria.
Starting Page	1
Ending Page	19
Page Count	19
File Format	PDF
ISSN	21678375
e-ISSN	21678383
DOI	10.1145/2956579
Volume Number	4
Issue Number	4
Journal	ACM Transactions on Economics and Computation (TEAC)
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2016-08-26
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Payoff query complexity Approximate Nash equilibrium Bimatrix game Randomized algorithms
Content Type	Text
Resource Type	Article
Subject	Economics and Econometrics Marketing Computational Mathematics Statistics and Probability Computer Science

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Finding approximate nash equilibria of bimatrix games via payoff queries

X Finding Approximate Nash Equilibria of Bimatrix Games via Payoff Queries

Learning equilibria of games via payoff queries

Bounds for the Query Complexity of Approximate Equilibria

Finding Approximate Nash Equilibria of Bimatrix Games via Payoff Queries

Approximate Pure Nash Equilibria in Weighted Congestion Games: Existence, Efficient Computation, and Structure

Approximate and well-supported approximate Nash equilibria of random bimatrix games (2007)

On the computational complexity of Nash equilibria for (0, 1) bimatrix games

On the Computational Complexity of Nash Equilibria for (0, 1) Bimatrix Games

Finding Approximate Nash Equilibria of Bimatrix Games via Payoff Queries

Similar Documents

Finding approximate nash equilibria of bimatrix games via payoff queries

X Finding Approximate Nash Equilibria of Bimatrix Games via Payoff Queries

Learning equilibria of games via payoff queries

Bounds for the Query Complexity of Approximate Equilibria

Finding Approximate Nash Equilibria of Bimatrix Games via Payoff Queries

Approximate Pure Nash Equilibria in Weighted Congestion Games: Existence, Efficient Computation, and Structure

Approximate and well-supported approximate Nash equilibria of random bimatrix games (2007)

On the computational complexity of Nash equilibria for (0, 1) bimatrix games

On the Computational Complexity of Nash Equilibria for (0, 1) Bimatrix Games

Finding Approximate Nash Equilibria of Bimatrix Games via Payoff Queries