Bi-SP Conjecture on common shortest paths in positive two-person games

From papers

Let G=(V,E)G=(V,E) be a finite two-person shortest path game with initial position ss, terminal set VTV_T, and positive local costs ri(e)>0r_i(e)>0 for i\bin{1,2}i\bin\{1,2\} and eEe\in E. For a stationary strategy σ1\sigma_1 of player 1, let G(σ1)G(\sigma_1) be the digraph obtained by retaining only the arc selected by σ1\sigma_1 at each player-1 position. Let P2(σ1)P_2(\sigma_1) be the set of paths from ss to VTV_T minimizing player 2's effective cost in G(σ1)G(\sigma_1), and let P2=σ1S1P2(σ1)P_2=\bigcup_{\sigma_1\in S_1}P_2(\sigma_1). Define P1P_1 symmetrically. An (s,VT)(s,V_T)-path is a directed path from ss to a vertex in VTV_T.

Bi-SP Conjecture. If GG has an (s,VT)(s,V_T)-path, then P1P_1 and P2P_2 have such a path in common, that is,

(P1P2){}.(P_1\cap P_2)\setminus\{\overline\infty\}\neq\emptyset.

This is the graph-theoretic reformulation of the conjectured existence of a terminal Nash equilibrium. The paper proves that P1P2P_1\cap P_2 is always nonempty, but the common element may be the infinite-cost symbol \overline\infty; 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

No solutions have been posted yet.