We revisit the computational complexity of decision problems about existence of Nash equilibria in multi-player games satisfying certain natural properties. Such problems have generally been shown to be complete for the complexity class.R, that captures the complexity of the decision problem for the Existential Theory of the Reals. For most of these problems, we show that their complexity remains unchanged even when restricted to win-lose games, where all utilities are either 0 or 1.
Computational Complexity of Decision Problems about Nash Equilibria in Win-Lose Multi-Player Games
V. Bilo';
2023-01-01
Abstract
We revisit the computational complexity of decision problems about existence of Nash equilibria in multi-player games satisfying certain natural properties. Such problems have generally been shown to be complete for the complexity class.R, that captures the complexity of the decision problem for the Existential Theory of the Reals. For most of these problems, we show that their complexity remains unchanged even when restricted to win-lose games, where all utilities are either 0 or 1.File in questo prodotto:
| File | Dimensione | Formato | |
|---|---|---|---|
|
sagt 2023.pdf
non disponibili
Tipologia:
Versione editoriale
Licenza:
Copyright dell'editore
Dimensione
540.83 kB
Formato
Adobe PDF
|
540.83 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
