The Weihrauch degree of finding Nash equilibria in multiplayer games
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2021
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866908422636568576 |
|---|---|
| author | Crook, Tonicha Pauly, Arno |
| author_facet | Crook, Tonicha Pauly, Arno |
| contents | Is there an algorithm that takes a game in normal form as input, and outputs a Nash equilibrium? If the payoffs are integers, the answer is yes, and lot of work has been done in its computational complexity. If the payoffs are permitted to be real numbers, the answer is no, for continuity reasons. It is worthwhile to investigate the precise degree of non-computability (the Weihrauch degree), since knowing the degree entails what other approaches are available (eg, is there a randomized algorithm with positive success change?). The two player case has already been fully classified, but the multiplayer case remains open and is addressed here. Our approach involves classifying the degree of finding roots of polynomials, and lifting this to systems of polynomial inequalities via cylindrical algebraic decomposition. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2109_00972 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | The Weihrauch degree of finding Nash equilibria in multiplayer games Crook, Tonicha Pauly, Arno Logic in Computer Science Computer Science and Game Theory 03B30, 03D30, 91A06, 12Y05 F.2 Is there an algorithm that takes a game in normal form as input, and outputs a Nash equilibrium? If the payoffs are integers, the answer is yes, and lot of work has been done in its computational complexity. If the payoffs are permitted to be real numbers, the answer is no, for continuity reasons. It is worthwhile to investigate the precise degree of non-computability (the Weihrauch degree), since knowing the degree entails what other approaches are available (eg, is there a randomized algorithm with positive success change?). The two player case has already been fully classified, but the multiplayer case remains open and is addressed here. Our approach involves classifying the degree of finding roots of polynomials, and lifting this to systems of polynomial inequalities via cylindrical algebraic decomposition. |
| title | The Weihrauch degree of finding Nash equilibria in multiplayer games |
| topic | Logic in Computer Science Computer Science and Game Theory 03B30, 03D30, 91A06, 12Y05 F.2 |
| url | https://arxiv.org/abs/2109.00972 |