Subgame-perfect equilibrium in concurrent reachability games

To verify against an arbitrary multistage deviation, condition on the next state. By the induction hypothesis, replacing the prescribed continuation after that state cannot improve the deviator's payoff, even if the deviator planned a sequence of changes rather than one change. Once continuations are bounded this way, the current mixed Nash inequality bounds the current action change as well. This proves the continuation inequality at $h$ for every behavioral deviation. There are finitely many histories through depth $H$, so backwards induction completes the construction, including every feasible off-path history. ∎

Conversely, if the elimination sequence stabilizes at nonempty $C$, choose one witnessing pure joint action at each of its states. These pure joint choices factor into the two players' pure actions and keep the process in $C$ with probability one. Thus universal almost-sure hitting fails from those states. This proves the equivalence. Correlated joint control was allowed in the upper-bound argument only to make it stronger; the witnessing nonstopping policy already factors into independent pure choices. ∎

Choose finite-horizon SPE profiles for horizons $H=1,2,\ldots$, and extend them arbitrarily after their horizons. Extract a coordinatewise convergent subsequence $\sigma^{H_j}\to\sigma$. Fix a feasible history $h$ of depth $m$. A continuation payoff truncated $K$ steps after $h$ depends polynomially on finitely many strategy coordinates, so it is continuous for coordinatewise convergence. Its difference from the full payoff is at most the probability that $D$ has not been reached by those $K$ steps, bounded by $(1-\delta)^{\lfloor K/L\rfloor}$ uniformly over all profiles and deviations. Hence the full continuation payoff is a uniform limit of continuous functions and is continuous.

Now fix any player and any behavioral continuation deviation $\tau_i$. For all $H_j\geq m$, the finite-horizon SPE inequality at $h$ holds for the restriction of $\tau_i$. Replacing both payoffs there by their full-horizon counterparts changes the inequality by at most $2(1-\delta)^{\lfloor(H_j-m)/L\rfloor}$. The latter tends to zero. By the just-proved continuity, both full payoffs converge along $\sigma^{H_j}\to\sigma$, including when one component is replaced by the fixed $\tau_i$. Passing to the limit gives the required SPE inequality.

The extracted subsequence did not depend on $h,i,\tau_i$. The argument can therefore be applied to every such choice; no diagonalization over the uncountable set of deviations is being asserted or needed. Past target flags were included throughout, proving the exact continuation convention in the input. ∎

At each fixed finite history at $s$, the prescribed action is eventually wait as $n\to\infty$. The coordinatewise limit is therefore always wait, with payoff zero from $s$. Deviating to immediate stop gives payoff one. This limit is not even a Nash equilibrium. Immediate stop itself is an SPE, so the example does not show nonexistence in this game; it disproves closedness of the equilibrium set under the proposed compactness argument. ∎

At any history, the conditional probability of decreasing rank at each of the next at most $m$ transitions until reaching $D$ is at least $p_*^m$. Subsequent transitions stay in $D$. This proves (3), uniformly over histories and strategies. Applying the conditional bound successively in blocks proves the geometric tail. Summing ${\mathbb{P}}(\tau_D>t)$ over integer $t\geq0$ gives ${\mathbb{E}}\tau_D\leq L\sum_{k\geq0}(1-\delta)^k=L/\delta$.

If (2) fails, select at each state in its nonempty set a support-preserving joint action and let both players follow their components. From that set $D$ is never reached. This contradicts (3), proving the converse. ∎

Fix any history-dependent deviation. Iterating the inequalities $v_i^x(q)\geq Q_i^x(q,a_i)$ until $D$ or date $N$ bounds its expected discounted terminal payoff received by $N$ by $v_i^x(q_0)$. The omitted residual is bounded by $\lambda^N$, since $0\leq v_i^x\leq1$. Letting $N\to\infty$ proves the deviation inequality. Following $x_i$ gives equality by the defining value equation. This holds from every state. ∎

The product of stationary simplexes is compact, so take $x^{\lambda_k}\to x$. For any fixed history-dependent deviation, its probability of hitting $D$ by a fixed finite date is a finite sum of continuous expressions in the opponents' stationary probabilities. The remaining payoff is bounded uniformly by $(1-\delta)^{\lfloor N/L\rfloor}$. First letting $k\to\infty$ at fixed $N$, then $N\to\infty$, proves convergence of its undiscounted payoff. The same argument applies to the prescribed profiles. Pass to the limit in the approximate equilibrium inequalities for each fixed deviation and each augmented initial state. Their error tends to zero.

At any feasible original history, including a history of probability zero under $x$, the continuation has the corresponding augmented state and the same stationary continuation profile. A player's credited previous success is its flag. The all-state deviation inequalities therefore prove precisely subgame perfection as defined in the target. ∎

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