NDLI: Bounds for the Query Complexity of Approximate Equilibria

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

Bounds for the Query Complexity of Approximate Equilibria

Content Provider	ACM Digital Library
Author	Goldberg, Paul W. Roth, Aaron
Copyright Year	2016
Abstract	We analyze the number of payoff queries needed to compute approximate equilibria of multi-player games. We find that query complexity is an effective tool for distinguishing the computational difficulty of alternative solution concepts, and we develop new techniques for upper- and lower bounding the query complexity. For binary-choice games, we show logarithmic upper and lower bounds on the query complexity of approximate correlated equilibrium. For $\textit{well-supported}$ approximate correlated equilibrium (a restriction where a player’s behavior must always be approximately optimal, in the worst case over draws from the distribution) we show a linear lower bound, thus separating the query complexity of well supported approximate correlated equilibrium from the standard notion of approximate correlated equilibrium. Finally, we give a query-efficient reduction from the problem of $\textit{computing}$ an approximate well-supported Nash equilibrium to the problem of verifying a well supported Nash equilibrium, where the additional query overhead is proportional to the description length of the game. This gives a polynomial-query algorithm for computing well supported approximate Nash equilibria (and hence correlated equilibria) in concisely represented games. We identify a class of games (which includes congestion games) in which the reduction can be made not only query efficient, but also computationally efficient.
Starting Page	1
Ending Page	25
Page Count	25
File Format	PDF
ISSN	21678375
e-ISSN	21678383
DOI	10.1145/2956582
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 queries Correlated equilibrium
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

Bounds for the query complexity of approximate equilibria

Query Complexity of Correlated Equilibrium

The Complexity of the Homotopy Method, Equilibrium Selection, and Lemke-Howson Solutions

Ex-Post Equilibrium and VCG Mechanisms

The Query Complexity of Scoring Rules

On Nash Equilibria for a Network Creation Game

Finding approximate nash equilibria of bimatrix games via payoff queries

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

Bounds for the Query Complexity of Approximate Equilibria

Similar Documents

Finding Approximate Nash Equilibria of Bimatrix Games via Payoff Queries

Bounds for the query complexity of approximate equilibria

Query Complexity of Correlated Equilibrium

The Complexity of the Homotopy Method, Equilibrium Selection, and Lemke-Howson Solutions

Ex-Post Equilibrium and VCG Mechanisms

The Query Complexity of Scoring Rules

On Nash Equilibria for a Network Creation Game

Finding approximate nash equilibria of bimatrix games via payoff queries

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

Bounds for the Query Complexity of Approximate Equilibria