Approximate well supported nash equilibria in win-lose bimatrix games
Yogesh Anbalagan · container not stated · 2014
Not cached yet. This record was fetched live for this request and is stored after the lookup. Reopening the page should serve the cached copy.
· OpenAlex · dissertation · 2014
Abstract
In this thesis, we study ε-well supported Nash equilibria (ε-WSNE) in two player normal-form games. In an ε-WSNE, every pure strategy that is played with positive probability must have an expected payoff within ε of the best response payoff. These can be viewed as combinatorial relaxations of exact Nash equilibria, and this thesis examines the structure of ε-WSNE via the use of a graphical representation of win-lose games. Our main result states that to obtain ε-WSNE with an approximation guarantee better than ⅔ the players must use mixed strategies whose supports have polylogarithmic cardinality.
In addition, we show that, to obtain any non-trivial approximation guarantee requires supports of cardinality at least three. Finally, we use the graphical representation to provide a characterization of when a win-lose game has an ε-WSNE with both good approximation guarantee and small cardinality supports.
Open the resolved locator · 10.82308/44331
Metadata licence: OpenAlex metadata (CC0)