Deterministic n-person shortest path and terminal games on symmetric digraphs have Nash equilibria in pure stationary strategies

Endre Boros (), Paolo Giulio Franciosa (), Vladimir Gurvich () and Michael Vyalyi ()
Additional contact information
Endre Boros: Rutgers University
Paolo Giulio Franciosa: Sapienza University
Vladimir Gurvich: Rutgers University
Michael Vyalyi: National Research University

International Journal of Game Theory, 2024, vol. 53, issue 2, No 7, 449-473

Abstract: 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 players.

Keywords: Nash equilibrium; n-Person deterministic graphical games; Shortest path games; Terminal games (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s00182-023-00875-y Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jogath:v:53:y:2024:i:2:d:10.1007_s00182-023-00875-y

Ordering information: This journal article can be ordered from
http://www.springer. ... eory/journal/182/PS2

DOI: 10.1007/s00182-023-00875-y

Access Statistics for this article

International Journal of Game Theory is currently edited by Shmuel Zamir, Vijay Krishna and Bernhard von Stengel

More articles in International Journal of Game Theory from Springer, Game Theory Society
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().