On the complexity of deciding bimatrix games similarity (Q955038): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/j.tcs.2008.07.021 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2062992879 / rank | |||
Normal rank |
Revision as of 00:15, 20 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the complexity of deciding bimatrix games similarity |
scientific article |
Statements
On the complexity of deciding bimatrix games similarity (English)
0 references
18 November 2008
0 references
The paper deals with computational aspects of finding Nash equilibria in bimatrix games. The attention is focused on specific situation of similarity between two games, namely whether they share a common Nash equilibrium (so called weak similarity) or if their sets of Nash equilibria are identical (strong similarity). It is shown that the decision about the weak similarity represents an NP-complete problem, meanwhile the complexity of the verification of the strong similarity is co-NP-hard.
0 references
Complexity
0 references
Game theory
0 references
Bimatrix game
0 references
Similarity
0 references
Nash equilibrium
0 references