DROPS

Document

DOI: 10.4230/LIPIcs.APPROX-RANDOM.2015.78

Large Supports are Required for Well-Supported Nash Equilibria

Authors: Yogesh Anbalagan, Hao Huang, Shachar Lovett, Sergey Norin, Adrian Vetta, and Hehui Wu

Published in: LIPIcs, Volume 40, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)

Abstract

We prove that for any constant k and any epsilon < 1, there exist bimatrix win-lose games for which every epsilon-WSNE requires supports of cardinality greater than k. To do this, we provide a graph-theoretic characterization of win-lose games that possess epsilon-WSNE with constant cardinality supports. We then apply a result in additive number theory of Haight to construct win-lose games that do not satisfy the requirements of the characterization. These constructions disprove graph theoretic conjectures of Daskalakis, Mehta and Papadimitriou and Myers.

Cite as

Yogesh Anbalagan, Hao Huang, Shachar Lovett, Sergey Norin, Adrian Vetta, and Hehui Wu. Large Supports are Required for Well-Supported Nash Equilibria. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 78-84, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{anbalagan_et_al:LIPIcs.APPROX-RANDOM.2015.78,
  author =	{Anbalagan, Yogesh and Huang, Hao and Lovett, Shachar and Norin, Sergey and Vetta, Adrian and Wu, Hehui},
  title =	{{Large Supports are Required for Well-Supported Nash Equilibria}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)},
  pages =	{78--84},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-89-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{40},
  editor =	{Garg, Naveen and Jansen, Klaus and Rao, Anup and Rolim, Jos\'{e} D. P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.78},
  URN =		{urn:nbn:de:0030-drops-52959},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2015.78},
  annote =	{Keywords: bimatrix games, well-supported Nash equilibria}
}

@InProceedings{anbalagan_et_al:LIPIcs.APPROX-RANDOM.2015.78,
  author =	{Anbalagan, Yogesh and Huang, Hao and Lovett, Shachar and Norin, Sergey and Vetta, Adrian and Wu, Hehui},
  title =	{{Large Supports are Required for Well-Supported Nash Equilibria}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)},
  pages =	{78--84},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-89-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{40},
  editor =	{Garg, Naveen and Jansen, Klaus and Rao, Anup and Rolim, Jos\'{e} D. P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.78},
  URN =		{urn:nbn:de:0030-drops-52959},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2015.78},
  annote =	{Keywords: bimatrix games, well-supported Nash equilibria}
}

Search Results

Documents authored by Anbalagan, Yogesh

Large Supports are Required for Well-Supported Nash Equilibria

Abstract

Cite as

Thanks for your feedback!

Could not send message