1. Two-person positive shortest path games have Nash equlibria in pure stationary strategies
- Author
-
Boros, Endre, Elbassioni, Khaled, Gurvich, Vladimir, and Vyalyi, Mikhail
- Subjects
Computer Science - Discrete Mathematics ,Computer Science - Multiagent Systems ,Mathematics - Optimization and Control ,91A05 - Abstract
We prove that every finite two-person positive shortest path game has a Nash equilibrium (NE) in pure stationary strategies, which can be computed in polynomial time. The existence result holds also for graphs with finite out-degrees. Moreover, we prove that a terminal NE exists provided at least one of two players can guarantee reaching a terminal. If no one can do it, in other words, if each of two players can cut all terminals from the initial position $s$, then, obviously, a cyclic NE exists, although its cost is infinite for both players, since we restrict ourselves to positive games. We conjecture that a terminal NE exists too, provided there exists a directed path from $s$ to a terminal. However, this is open.
- Published
- 2024