The complexity of uniform Nash equilibria and related regular subgraph problems (Q935157)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 5306537
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | The complexity of uniform Nash equilibria and related regular subgraph problems |
scientific article; zbMATH DE number 5306537 |
Statements
The complexity of uniform Nash equilibria and related regular subgraph problems (English)
0 references
31 July 2008
0 references
The complexity of finding uniform Nash equilibria is investigated. A Nash equilibrium is uniform if, for each player, all the strategies played with non-zero probability are assigned the same probability. It is shown that, even for a restricted class of win-lose bimatrix games, deciding the existence of such uniform equilibria is an NP-complete problem. The proof is graph-theoretical. As a related result it is shown that it is NP-complete to decide if a graph has an induced regular subgraph of large size or regularity.
0 references
computational complexity
0 references
NP-completeness
0 references
uniform Nash equilibrium
0 references
regular induced subgraph
0 references
0.9451002478599548
0 references
0.8217737674713135
0 references
0.8154184818267822
0 references
0.8110490441322327
0 references
