Partial results on exact equilibria in concurrent reachability games

Let $v$ be the optimal value vector and let $z$ be the stated convex combination. The Bellman equality $v=g_z+K_zv$ holds because it holds for every component policy. Any closed unresolved recurrent class $C$ of $z$ is closed under each component of positive weight: a nonnegative transition out of $C$ cannot cancel in a convex combination. Each such component earns zero on $C$, so its optimal value $v$ is zero there. Iterating the equality gives \[ v=\sum_{k=0}^{n-1}K_z^k g_z+K_z^n v. \] In a finite chain, the probability of avoiding both termination and the closed unresolved recurrent classes tends to zero. Since $v=0$ on those classes, $K_z^n v\to0$. The sum converges to the actual terminal reward of $z$, proving optimality. ∎

Put $N=\max_i|\Pi_i|$, fix $0<\delta<1$, and restrict each policy probability to be at least $\eta=\delta^N/N$. Against $w_{-i}$, prescribe the correspondence of all such $w_i$ satisfying \begin{equation}\label{wsref-0-65-71-3a-70-72-6f-70-65-72} w_i(\pi)\leq\delta w_i(\pi') \quad\text{whenever }L_i(\pi,T_{-i}(w_{-i})) <L_i(\pi',T_{-i}(w_{-i})). \end{equation} It has nonempty compact convex values. To see nonemptiness, order the $m=|\Pi_i|$ policies from best to worst and assign probabilities proportional to $1,\delta,\ldots,\delta^{m-1}$, breaking ties arbitrarily. The smallest is at least $\delta^{m-1}/m\geq\eta$. The graph is closed: every strict payoff inequality at a limit persists near that limit. Kakutani's theorem [Kakutani, p. 458] applies to the product of the two restricted simplices and gives a fixed point. This is a finite-policy version of the proper-pair construction in [FTV, Definition 2.3 and Theorem 2.4].

Take $\delta_n\downarrow0$ and a convergent subsequence $w_i^n\to w_i^0$. If $w_i^0(\pi)>0$, then eventually $w_i^n(\pi)$ is bounded below by a positive constant. Equation (eq:proper) rules out a strictly better pure policy, since it would force $w_i^n(\pi)\leq\delta_n$. Thus every policy in $\operatorname{supp}(w_i^0)$ maximizes $L_i$ against $T_{-i}(w_{-i}^n)$ for all large $n$. By Lemma Lemma, one pure policy attains the optimum in every state. Positive weights $\mu(s)$ imply that any scalar maximizer also attains that optimum in every state. The convexity assertion of the same lemma proves the crossing property for $x_n=T_1(w_1^n)$ and $y_n=T_2(w_2^n)$.

If the limit profile terminates almost surely, $I-K_{x_0,y_0}$ is invertible, so compliance values are continuous in a neighborhood of it. For each fixed pure stationary deviation $\pi$, nonnegative rewards make its actual value lower semicontinuous in the opponent's policy: it is the increasing supremum of the finite-horizon values, which are continuous polynomials. Consequently, coordinatewise, \[ V_1^{\pi,y_0}\leq\liminf_n V_1^{\pi,y_n} \leq\lim_n V_1^{x_0,y_n}=V_1^{x_0,y_0}. \] The argument for player 2 uses the other crossing inequality. Lemma Lemma bounds every behavioral deviation by a pure stationary optimum. Hence neither player can gain after any feasible history. ∎

Replace first entry into $z\in Z$ by termination with the equilibrium reward just obtained. In every remaining state both cooperative values are strictly positive. Indeed, a finite path to a positive terminal reward either remains outside $Z$ until termination or first reaches a state of $Z$ where the relevant cooperative maximum was preserved. Against any fully mixed stationary opponent, either player therefore has a strictly positive optimal reward in every remaining state: it can prescribe its actions along such a finite positive-probability path. No bound uniform over fully mixed policies is needed.

If no state remains, we are done. If $s_*$ has been removed or player 1 has only one action there, a pure stationary optimum for player 2 solves the remaining MDP. Otherwise apply Lemma Lemma (Crossing stationary policies). For large $n$, the crossed pair $(x_n,y_0)$ terminates almost surely from every state. Player 2 is an exact best response to the fully mixed $x_n$, so its actual value is strictly positive everywhere. A closed unresolved recurrent class, whose actual reward is zero, is impossible.

If $(x_0,y_0)$ is also terminating, Lemma Lemma (Crossing stationary policies) finishes the proof. Otherwise every closed unresolved recurrent class of this limit must contain $s_*$. A class avoiding $s_*$ would remain closed under $(x_n,y_0)$, since player 1 has no choices within it. Thus there is just one such class $C$. Moreover, $x_0$ uses a single action $A$ at $s_*$: if both actions had positive probability, $C$ would again remain closed under the crossed pair. Call the other action $B$.

Fix $y_0$. Outside $s_*$ the chain has no unresolved closed class avoiding $s_*$. Hence an excursion starting with either action at $s_*$ reaches termination or returns to $s_*$ almost surely. An $A$-excursion stays in $C$ and returns almost surely without any terminal reward. For a $B$-excursion, let $p$ be the probability of termination before return and $b_i$ its expected terminal $i$-reward. Here $p>0$: otherwise neither action could cause termination from $s_*$, contradicting termination under $(x_n,y_0)$.

Any stationary policy using $B$ with probability $t>0$ on each visit terminates almost surely from $s_*$. Its value there is $b_i/p$, since \[ v_i=t b_i+(1-tp)v_i. \] An arbitrary player-1 deviation cannot exceed $b_1/p$ there. To verify this without a finite-horizon assumption, enumerate its successive $B$-excursions and let $q_k$ be the probability that its $k$th such excursion is started. Conditional on any starting history, that excursion has termination probability $p$ and expected reward $b_1$. The terminating excursions are disjoint, so \[ \mathbb E[\text{terminal reward}]=b_1\sum_{k\geq1}q_k =\frac{b_1}{p}\,\Pr(\text{termination})\leq\frac{b_1}{p}. \] The identities follow by summing nonnegative quantities and also cover policies that eventually wait forever. Before the first visit to $s_*$ or termination, a path from another state has no player-1 choice. Thus every stationary policy with $t>0$ is an all-state best response to $y_0$. In particular $x_n$ is one. Player 2 was already a best response to $x_n$, proving that $(x_n,y_0)$ is an exact stationary SPE.

Finally restore the solved policies on $Z$. No deviation can return from $Z$ to its complement, or improve its prescribed boundary reward. The remaining game's best-response inequalities therefore extend to the full game from every state and after every feasible prefix. ∎

Before either target is reached, replace first entry into the solved region by its actual equilibrium payoff vector, of the form $(1,v)$, $(v,1)$, or $(1,1)$. This is a nonnegative terminal-reward game; paths never reaching either target give $(0,0)$. It has the decision-state restriction of Theorem Theorem. Its stationary SPE, combined with the solved continuations, satisfies (eq:spe). The bits retain earlier target visits at every prefix, including off-path ones. ∎

In fact $u_n>1/2$. If $u_n=1/2$, move past any initial Wait/Wait stages to the first positive-quitting stage and write its probabilities as $p,q$ and its next unresolved value as $v\geq1/2$. The Bellman identity gives \[ \tfrac12=pq+\tfrac12[p(1-q)+(1-p)q]+(1-p)(1-q)v \geq\tfrac12+\tfrac12pq. \] Thus exactly one of $p,q$ is positive. The other player could Quit immediately and gain half that positive probability, a contradiction.

At any positive-quitting stage both probabilities must be positive: if one were zero, the other's supported Quit action would yield $1/2$, less than its value. A supported action must have the equilibrium one-step return, because changing just that action is an admissible deviation. If either probability is one, both are one: against certain Quit, Quit gives one and Wait gives $1/2$.

At a stage with $0<p,q<1$, indifference gives \[ u=\frac{1+q}{2}=\frac{1+p}{2},\qquad \frac{1+p}{2}=\frac p2+(1-p)v. \] Hence $p=q$, $v=1/[2(1-p)]$, and $p\leq1/2$ because $v\leq1$. Wait/Wait stages preserve the value. If $p'$ is the Quit probability at the next positive-quitting stage, then \begin{equation}\label{wsref-0-65-71-3a-72-65-63-69-70} p'=\frac p{1-p},\qquad \frac1{p'}=\frac1p-1. \end{equation} This includes $p=1/2$, followed by $p'=1$. At any positive-quitting stage the reciprocal is either one or at least two. Repeated subtraction of one can stay in this set only if its initial value is an integer $m$. Otherwise it eventually lies strictly between one and two. Thus the positive Quit probabilities are forced to be $1/m,1/(m-1),\ldots,1$, separated only by finite Wait/Wait intervals. The initial payoff is necessarily $u_m$.

For attainment, use modes $k=m,m-1,\ldots,1$. In mode $k$ each player independently Quits with probability $1/k$. Every unresolved transition updates $k$ to $\max(k-1,1)$; this also defines behavior at off-path prefixes following mode one. For $k\geq2$, the actual Bellman return is \[ \frac1k+\left(\frac{k-1}{k}\right)^2u_{k-1}=u_k. \] Quit gives $(1+1/k)/2=u_k$, and Wait gives $1/(2k)+(k-1)u_{k-1}/k=u_k$. In mode one, Quit gives one and Wait gives $1/2$. Under any unilateral deviation, the other player still Quits surely by mode one. Termination therefore occurs within $m$ stages, and backward induction proves optimality against every behavioral deviation after every feasible prefix.

A deterministic public finite controller assigns an action distribution to its current mode and physical state. Equation (eq:recip) forces $m$ distinct positive Quit probabilities along the surviving histories of any SPE with payoff $u_m$; these require at least $m$ modes. The construction attains the bound. In that construction survival after $k<m$ stages has probability $((m-k)/m)^2$. Summing these survival probabilities gives \[ \mathbb E\tau=\sum_{k=0}^{m-1}\left(\frac{m-k}{m}\right)^2 =\frac{(m+1)(2m+1)}{6m}. \] Every other SPE with the same payoff can only insert Wait/Wait stages between the forced quitting stages. Such delays cannot reduce the mean termination time. This proves (eq:time). ∎