A counterexample to conjecture "Catch 22"
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909438778015744 |
|---|---|
| author | Butyrin, Bogdan Gurvich, Vladimir Lutsenko, Anton Naumova, Mariya Peskin, Maxim |
| author_facet | Butyrin, Bogdan Gurvich, Vladimir Lutsenko, Anton Naumova, Mariya Peskin, Maxim |
| contents | We construct a finite deterministic graphical (DG) game without Nash equilibria in pure stationary strategies. This game has 3 players $I=\{1,2,3\}$ and 5 outcomes: 2 terminal $a_1$ and $a_2$ and 3 cyclic. Furthermore, for 2 players a terminal outcome is the best: $a_1$ for player 3 and $a_2$ for player 1. Hence, the rank vector $r$ is at most $(1,2,1)$. Here $r_i$ is the number of terminal outcomes that are worse than some cyclic outcome for the player $i \in I$. This is a counterexample to conjecture ``Catch 22" from the paper ``On Nash-solvability of finite $n$-person DG games, Catch 22" (2021) arXiv:2111.06278, according to which, at least 2 entries of $r$ are at least 2 for any NE-free game. However, Catch 22 remains still open for the games with a unique cyclic outcome, not to mention a weaker (and more important) conjecture claiming that an $n$-person finite DG game has a Nash equilibrium (in pure stationary strategies) when $r = (0^n)$, that is, all $n$ entries of $r$ are 0; in other words, when the following condition holds:
$\qquad\bullet$ ($C_0$) any terminal outcome is better than every cyclic one for each player.
A game is play-once if each player controls a unique position. It is known that any play-once game satisfying ($C_0$) has a Nash equilibrium. We give a new and very short proof of this statement. Yet, not only conjunction but already disjunction of the above two conditions may be sufficient for Nash-solvability. This is still open. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_14587 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A counterexample to conjecture "Catch 22" Butyrin, Bogdan Gurvich, Vladimir Lutsenko, Anton Naumova, Mariya Peskin, Maxim Combinatorics We construct a finite deterministic graphical (DG) game without Nash equilibria in pure stationary strategies. This game has 3 players $I=\{1,2,3\}$ and 5 outcomes: 2 terminal $a_1$ and $a_2$ and 3 cyclic. Furthermore, for 2 players a terminal outcome is the best: $a_1$ for player 3 and $a_2$ for player 1. Hence, the rank vector $r$ is at most $(1,2,1)$. Here $r_i$ is the number of terminal outcomes that are worse than some cyclic outcome for the player $i \in I$. This is a counterexample to conjecture ``Catch 22" from the paper ``On Nash-solvability of finite $n$-person DG games, Catch 22" (2021) arXiv:2111.06278, according to which, at least 2 entries of $r$ are at least 2 for any NE-free game. However, Catch 22 remains still open for the games with a unique cyclic outcome, not to mention a weaker (and more important) conjecture claiming that an $n$-person finite DG game has a Nash equilibrium (in pure stationary strategies) when $r = (0^n)$, that is, all $n$ entries of $r$ are 0; in other words, when the following condition holds: $\qquad\bullet$ ($C_0$) any terminal outcome is better than every cyclic one for each player. A game is play-once if each player controls a unique position. It is known that any play-once game satisfying ($C_0$) has a Nash equilibrium. We give a new and very short proof of this statement. Yet, not only conjunction but already disjunction of the above two conditions may be sufficient for Nash-solvability. This is still open. |
| title | A counterexample to conjecture "Catch 22" |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2406.14587 |