Approximating nash equilibria using small-support strategies

Tomás Feder · Hamid Nazerzadeh · Amin Saberi

83 citations0/0 files storedACM Conference on Electronic Commerce (EC)

No readable copy stored yet — this record is metadata only.

No open-access location is known for this record yet.

Literature note Cite in a project Citation map

Game Theory and Applications Complexity and Algorithms in Graphs Game Theory and Voting Systems

Abstract

We study the problem of finding approximate Nash equilibria of two player games. We show that for any 0<ε<1, there is no 1 1 + ε - approximate equilibrium with strategies of support O(log n ε2).

Paper brief

Loading…

Cite this work

Citation unavailable for this work.

BibTeX RIS CSL-JSON

No public copy is stored for this record, so only the metadata is cited.

Citations in this library

Citation map →

Stored only when both papers are in the corpus — 83 citations exist upstream.

References

1951Non-Cooperative Games 1989Non-cooperative games 2006Settling the Complexity of Two-Player Nash Equilibrium 2006The complexity of computing a Nash equilibrium 2003Playing large games using simple strategies 2007Progress in approximate nash equilibria 1994On sparse approximations to randomized strategies and convex combinations 2006A Note on Approximate Nash Equilibria

Cited by

2016Hardness Results for Signaling in Bayesian Zero-Sum and Network Routing Games 2009New algorithms for approximate Nash equilibria in bimatrix games 2007New Algorithms for Approximate Nash Equilibria in Bimatrix Games 2008Well Supported Approximate Equilibria in Bimatrix Games 2007Gradient-Based Algorithms for Finding Nash Equilibria in Extensive Form Games 2008Discretized multinomial distributions and Nash equilibria in anonymous games

Explore the map →

Papers that cite the same references — the relational fallback while embeddings are still backfilling.

Imported from OpenAlex (CC0) — nothing here is generated.