2026-07-25T14:07:06Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5295 2024-03-06T10:36:15Z ddc:004 open_access

Large Supports are Required for Well-Supported Nash Equilibria Anbalagan, Yogesh Huang, Hao Lovett, Shachar Norin, Sergey Vetta, Adrian Wu, Hehui bimatrix games well-supported Nash equilibria 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yogesh Anbalagan and Hao Huang and Shachar Lovett and Sergey Norin and Adrian Vetta and Hehui Wu 2015 Is Part Of LIPIcs, Volume 40, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2015.78 urn:nbn:de:0030-drops-52959 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.78 eng https://creativecommons.org/licenses/by/3.0/legalcode