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

At least 1 year old · documented by

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 e∈Ee\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=⋃σ1∈S1P2(σ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,

(P1∩P2)∖{∞‾}≠∅.(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 P1∩P2P_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.

References

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).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.