Reducibility among equilibrium problems

Abstract

We address the fundamental question of whether the Nash equilibria of a game can be computed in polynomial time. We describe certain efficient reductions between this problem for normal form games with a fixed number of players and graphical games with fixed degree. Our main result is that the problem of solving a game for any constant number of players, is reducible to solving a 4-player game.

Cite this work

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

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

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