Bi-SP Conjecture on common shortest paths in positive two-person games
Bi-SP Conjecture on common shortest paths in positive two-person games
Let be a finite two-person shortest path game with initial position , terminal set , and positive local costs for and . For a stationary strategy of player 1, let be the digraph obtained by retaining only the arc selected by at each player-1 position. Let be the set of paths from to minimizing player 2's effective cost in , and let . Define symmetrically. An -path is a directed path from to a vertex in .
Bi-SP Conjecture. If has an -path, then and have such a path in common, that is,
This is the graph-theoretic reformulation of the conjectured existence of a terminal Nash equilibrium. The paper proves that is always nonempty, but the common element may be the infinite-cost symbol ; the asserted terminal-path conclusion remains open.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Endre Boros, Khaled Elbassioni, Vladimir Gurvich and Mikhail Vyalyi, “Two-person Positive Shortest Path Games Have Nash Equilibria in Pure Stationary Strategies”, arXiv:2410.09257 (2025).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.