We prove that a deterministic n-person shortest path game has a Nash equlibrium in pure and stationary strategies if it is edge-symmetric (that is (u, v) is a move whenever (v, u) is, apart from moves entering terminal vertices) and the length of every move is positive for each player. Both conditions are essential, though it remains an open problem whether there exists a NE-free 2-person non-edge-symmetric game with positive lengths. We provide examples for NE-free 2-person edge-symmetric games that are not positive. We also consider the special case of terminal games (shortest path games in which only terminal moves have nonzero length, possibly negative) and prove that edge-symmetric n-person terminal games always have Nash equilibria in pure and stationary strategies. Furthermore, we prove that an edge- symmetric 2-person terminal game has a uniform (subgame perfect) Nash equilibrium, provided any infinite play is worse than any of the terminals for both players
Deterministic n-person shortest path and terminal games on symmetric digraphs have Nash equilibria in pure stationary strategies / Boros, Endre; Franciosa, Paolo Giulio; Gurvich, Vladimir; Vyalyi, Michael. - In: INTERNATIONAL JOURNAL OF GAME THEORY. - ISSN 0020-7276. - (2023), pp. 1-25. [10.1007/s00182-023-00875-y]
Deterministic n-person shortest path and terminal games on symmetric digraphs have Nash equilibria in pure stationary strategies
Paolo Giulio Franciosa
;
2023
Abstract
We prove that a deterministic n-person shortest path game has a Nash equlibrium in pure and stationary strategies if it is edge-symmetric (that is (u, v) is a move whenever (v, u) is, apart from moves entering terminal vertices) and the length of every move is positive for each player. Both conditions are essential, though it remains an open problem whether there exists a NE-free 2-person non-edge-symmetric game with positive lengths. We provide examples for NE-free 2-person edge-symmetric games that are not positive. We also consider the special case of terminal games (shortest path games in which only terminal moves have nonzero length, possibly negative) and prove that edge-symmetric n-person terminal games always have Nash equilibria in pure and stationary strategies. Furthermore, we prove that an edge- symmetric 2-person terminal game has a uniform (subgame perfect) Nash equilibrium, provided any infinite play is worse than any of the terminals for both playersFile | Dimensione | Formato | |
---|---|---|---|
boros-deterministic n‑person_2023.pdf
accesso aperto
Tipologia:
Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza:
Creative commons
Dimensione
1.94 MB
Formato
Adobe PDF
|
1.94 MB | Adobe PDF |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.