go-v.orgdoi

Approximate well supported nash equilibria in win-lose bimatrix games

Yogesh Anbalagan · container not stated · 2014

  • DOI 10.82308/44331
  • Publisher OpenAlex
  • Type dissertation
  • Issued 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)

Registry
OpenAlex DOI index + API
Fetched
2026-11-20 03:23 UTC
Cache state
not cached yet (bulk-index+openalex)
Locator
https://hdl.handle.net/20.500.14905/104547
Metadata licence
OpenAlex metadata (CC0)
Scope
Metadata as returned by the resolver; abstracts are never generated here.