License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2017.57
URN: urn:nbn:de:0030-drops-81636
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/8163/
Go to the corresponding LIPIcs Volume Portal

Chen, Xi ; Cheng, Yu ; Tang, Bo

Well-Supported vs. Approximate Nash Equilibria: Query Complexity of Large Games

pdf-format:
LIPIcs-ITCS-2017-57.pdf (0.5 MB)

Abstract

In this paper we present a generic reduction from the problem of finding an \epsilon-well-supported Nash equilibrium (WSNE) to that of finding an \Theta(\epsilon)-approximate Nash equilibrium (ANE), in large games with n players and a bounded number of strategies for each player.
Our reduction complements the existing literature on relations between WSNE and ANE, and can be applied to extend hardness results on WSNE to similar results on ANE.
This allows one to focus on WSNE first, which is in general easier to analyze and control in hardness constructions.

As an application we prove a 2^{\Omega(n/\log n)} lower bound on the randomized query complexity of finding an \epsilon-ANE in binary-action n-player games, for some constant \epsilon>0.
This answers an open problem posed by Hart and Nisan and Babichenko, and is very close to the trivial upper bound of 2^n.
Previously for WSNE, Babichenko showed a 2^{\Omega(n)} lower bound on the randomized query complexity of finding an \epsilon-WSNE for some constant epsilon>0.
Our result follows directly from combining Babichenko's result and our new reduction from WSNE to ANE.

BibTeX - Entry

@InProceedings{chen_et_al:LIPIcs:2017:8163,
  author =	{Xi Chen and Yu Cheng and Bo Tang},
  title =	{{Well-Supported vs. Approximate Nash Equilibria: Query Complexity of Large Games}},
  booktitle =	{8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
  pages =	{57:1--57:9},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-029-3},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{67},
  editor =	{Christos H. Papadimitriou},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/8163},
  URN =		{urn:nbn:de:0030-drops-81636},
  doi =		{10.4230/LIPIcs.ITCS.2017.57},
  annote =	{Keywords: Equilibrium Computation, Query Complexity, Large Games}
}

Keywords: Equilibrium Computation, Query Complexity, Large Games
Collection: 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)
Issue Date: 2017
Date of publication: 28.11.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI