Large Supports are Required for Well-Supported Nash Equilibria | Zendy

Yogesh Anbalagan | Zendy; Hao Huang | Zendy; Shachar Lovett | Zendy; Sergey Norin | Zendy; Adrian Vetta | Zendy; Hehui Wu | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Large Supports are Required for Well-Supported Nash Equilibria

Author(s) -

Yogesh Anbalagan,

Hao Huang,

Shachar Lovett,

Sergey Norin,

Adrian Vetta,

Hehui Wu

Publication year - 2015

Publication title -

cornell university

Language(s) - English

Resource type - Conference proceedings

DOI - 10.4230/lipics.approx-random.2015.78

Subject(s) - nash equilibrium , characterization (materials science) , cardinality (data modeling) , constant (computer programming) , graph , computer science , construct (python library) , game theory , mathematics , mathematical economics , combinatorics , discrete mathematics , theoretical computer science , data mining , materials science , programming language , nanotechnology

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.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research