betaFeedback

WorksComputer Science

Payoff-Based Certificates for Convergence to Pure Nash Equilibria under Replicator Dynamics

Abstract

For finite bimatrix games, we give a payoff-based sufficient condition E>0E>0 for an interior initial state to converge to a specified strict pure Nash equilibrium under replicator dynamics. The construction combines lower bounds on the growth rates of log probability ratios between target and alternative actions with a first integral of a two-dimensional comparison system. It allows one player's payoff advantage to compensate for the other's disadvantage, certifying convergence even when a target action initially loses probability. For rational inputs and integration base points with algebraic exponentials, we give a finite exact test. We obtain closed-form box probabilities and, when all nontarget actions are included, closed-form upper bounds on convergence time. In two-action coordination games, choosing the base points at the sign thresholds recovers the full basin of attraction. Experiments on random games show that basin coverage shrinks rapidly with the number of actions. For n=4,5,6n=4,5,6, median entry times are approximately 70% of median box-entry times without shifts and 40% for a union over 16 shift choices. Extensions cover multiplayer games through cooperative comparison systems and explicit boxes, and discrete-time exponential-weights learning under explicit step-size conditions.

Introduction

Local stability and a basin of attraction answer different questions. Local stability guarantees convergence to an equilibrium from some neighbourhood [5 Theorem 5.2], but it does not determine whether a specified initial state converges to that equilibrium. The certificate developed here supplies such a test. For example, the payoffs determine how close one player must be to the target to ensure convergence even when the other is far away. They also allow convergence to a particular equilibrium to be certified while learning is still in progress.

Contributions.

  1. A certificate with compensation. For any finite bimatrix game and any strict pure target equilibrium, we construct a payoff-based certificate EE. The set where E>0E > 0, which we call the capture region, is an open inner approximation of the target basin (Theorem 2.2). It extends beyond the box in which both players’ lower envelopes are positive; § 3 gives an example outside the class of potential games. The test requires neither an enumeration of Nash equilibria nor global convergence.

  1. Exact computation and closed-form expressions. For rational data, membership can be decided by a finite exact computation (Propositions 5.1 and 5.2). Box probabilities have closed-form expressions (Theorem 4.1), and when the selected sets include every alternative action, convergence times admit closed-form upper bounds (Theorem 4.2).

3. Basin coverage. In two-action coordination games, threshold base points give a capture region equal to the basin (Proposition 7.1). Every target-convergent initial state enters the capture region in finite time (Remark 7.2). In numerical experiments, the capture region shrinks rapidly as the number of actions increases, but for n=4,5,6n = 4, 5, 6 its median entry time remains approximately 40–70% of the median box-entry time (§ 7).

4. Extensions. For multiplayer games, we obtain capture regions defined by a comparison system and explicit boxes (Theorem 6.1 and Proposition 6.2). The results extend to discrete-time exponential-weights learning under explicit step-size conditions (Proposition A.1).

Related work. Explicit basin geometry and volume estimates have an extensive literature. Panageas and Piliouras [7 Sections 4.3 and 5] derive cross-entropy invariants, exact Stag Hunt basins and upper and lower bounds from invariant polytopes in potential and network coordination games. Zhang and Hofbauer [8] study basin dominance, centroid dominance and risk dominance in two-action bimatrix coordination games. An invariant of replicator dynamics, expressed as a constant of integration, implicitly describes the boundary between the two basins, which is the stable manifold of the saddle. The basin areas are given by integrals [8 Eqs. (10)–(12), (17)]. They also note that even centroid dominance should not be expected to have a simple formula in three-action symmetric coordination games. For two-action coordination games, the capture region constructed here coincides with the basin delimited by this boundary (Proposition 7.1). The construction can be viewed as extending the known two-action invariant to games with more actions through a lower comparison system. Castro [1 Theorems 3.1 and 3.4] shows that, in one-population matrix games, the basins of replicator and best-response dynamics overlap or coincide under invariance conditions on sectors bounded by indifference sets. Dal Bó and Pujals [2 Theorem 9] give an explicit, payoff-dependent subset of the basin around a strict equilibrium vertex in one-population replicator dynamics, defined by an upper bound on the total probability of alternative actions. Here the same type of guarantee is obtained for two-population games, with compensation between players enlarging the region.

The contribution is to construct lower envelopes that can be evaluated by a finite computation for each game and combine them with a first integral of a separable comparison system, thereby certifying initial states that benefit from compensation. The multiplayer comparison uses standard order-comparison arguments [4 Section 3.1]. The cited theorem, section and equation numbers refer to the author versions listed in the bibliography, including the specified arXiv versions.

Payoff-based convergence certificates

This section constructs two one-dimensional integrals from the payoff matrices and uses the sign of their sum EE to give a sufficient condition for an initial state to lie in the basin of the target equilibrium (Theorem 2.2).

Let I={0,…,n−1}I = \{0,\ldots,n-1\} and J={0,…,m−1}J = \{0,\ldots,m-1\}, with n,m≥2n,m \ge2. Write ΔI={p∈R+I:∑ipi=1}\Delta_I = \{p \in\mathbb{R}_{+}^{I} : \sum_i p_i = 1\} and define ΔJ\Delta_J analogously. The domain of initial states is D∘=int⁡ΔI×int⁡ΔJD^\circ= \operatorname{int}\Delta_I \times\operatorname{int}\Delta_J, where interiors are taken relative to the affine hulls. Throughout, the measure of initial states is the usual relative Lebesgue measure on D∘D^\circ. For real payoff matrices A,B∈RI×JA,B \in\mathbb{R}^{I \times J}, consider

p˙i=pi((Aq)i−pTAq),q˙j=qj((BTp)j−pTBq).(1)\dot{p}_i = p_i\left((Aq)_i - p^{\mathsf{T}}Aq\right), \qquad\dot{q}_j = q_j\left((B^{\mathsf{T}}p)_j - p^{\mathsf{T}}Bq\right). \tag*{(1)}

Time is denoted by τ\tau. The flow ϕτ\phi_\tau exists at every finite positive and negative time and preserves D∘D^\circ. Fix a strict pure Nash equilibrium (t,u)∈I×J(t,u) \in I \times J and set

ak=Atu−Aku>0,ckl=Atl−Akl(k≠t,l∈J),a_k = A_{tu} - A_{ku} > 0, \qquad c_{kl} = A_{tl} - A_{kl} \qquad(k \ne t, l \in J),
bl=Btu−Btl>0,dlk=Bku−Bkl(l≠u,k∈I)b_l = B_{tu} - B_{tl} > 0,\qquad d_{lk} = B_{ku} - B_{kl}\quad(l \ne u, k \in I)

so that cku=akc_{ku}=a_k and dlt=bld_{lt}=b_l.

Admissible action sets. Choose nonempty sets Dr⊆I∖{t}D_r \subseteq I \setminus\{t\} and Dc⊆J∖{u}D_c \subseteq J \setminus\{u\}, and write Nr=I∖DrN_r=I\setminus D_r and Nc=J∖DcN_c=J\setminus D_c. The actions in Dr,DcD_r,D_c will be called dangerous actions. We require:

  1. For every k∈Drk \in D_r and l∈Ncl \in N_c, we have ckl>0c_{kl}>0.

  1. For every l∈Dcl \in D_c and k∈Nrk \in N_r, we have dlk>0d_{lk}>0.

  1. In the subgame on Nr×NcN_r \times N_c, there exists a finite sequence of eliminations by pure strict dominance that leaves only (t,u)(t,u).

In the third condition, each eliminated action is strictly dominated by a pure strategy that is still present; the dominating strategy has a strictly positive payoff advantage against every remaining opposing action. The full sets Dr=I∖{t}D_r=I\setminus\{t\} and Dc=J∖{u}D_c=J\setminus\{u\} are always admissible. Fix shifts κ∈RDr\kappa\in\mathbb{R}^{D_r} and μ∈RDc\mu\in\mathbb{R}^{D_c}, and define

ξk=log⁡(pt/pk),ηl=log⁡(qu/ql),X=min⁡k∈Dr(ξk−κk),Y=min⁡l∈Dc(ηl−μl).\xi_k=\log(p_t/p_k),\qquad\eta_l=\log(q_u/q_l),\qquad X=\min_{k\in D_r}(\xi_k-\kappa_k),\qquad Y=\min_{l\in D_c}(\eta_l-\mu_l).

Lower envelopes of payoff differences. For y∈Ry\in\mathbb{R}, let

R(y)={ρ∈(0,∞)J∖{u}:ρl≤e−μl−y (l∈Dc)}R(y)=\left\{\rho\in(0,\infty)^{J\setminus\{u\}}:\rho_l\le e^{-\mu_l-y}\ (l\in D_c)\right\}

and define

F(y)=min⁡k∈Drinf⁡ρ∈R(y)ak+∑l≠ucklρl1+∑l≠uρl.(2)F(y)=\min_{k\in D_r}\inf_{\rho\in R(y)} \frac{a_k+\sum_{l\ne u}c_{kl}\rho_l}{1+\sum_{l\ne u}\rho_l}. \tag*{(2)}

Similarly, set

Q(x)={σ∈(0,∞)I∖{t}:σk≤e−κk−x (k∈Dr)},Q(x)=\left\{\sigma\in(0,\infty)^{I\setminus\{t\}}:\sigma_k\le e^{-\kappa_k-x}\ (k\in D_r)\right\},
G(x)=min⁡l∈Dcinf⁡σ∈Q(x)bl+∑k≠tdlkσk1+∑k≠tσk.G(x)=\min_{l\in D_c}\inf_{\sigma\in Q(x)} \frac{b_l+\sum_{k\ne t}d_{lk}\sigma_k}{1+\sum_{k\ne t}\sigma_k}.

Throughout, we use the conventions min⁡∅=+∞\min\varnothing=+\infty and sup⁡∅=−∞\sup\varnothing=-\infty.

Lemma 2.1. The envelope has the following finite representation:

F(y)=min⁡k∈Drmin⁡{min⁡T⊆Dcak+∑l∈Tckle−μl−y1+∑l∈Te−μl−y,min⁡l∈Nc∖{u}ckl}.(3)F(y)=\min_{k\in D_r}\min\left\{ \min_{T\subseteq D_c} \frac{a_k+\sum_{l\in T}c_{kl}e^{-\mu_l-y}}{1+\sum_{l\in T}e^{-\mu_l-y}}, \min_{l\in N_c\setminus\{u\}}c_{kl} \right\}. \tag*{(3)}

It is continuous, locally Lipschitz, and nondecreasing, and

F(+∞)=min⁡k∈Drmin⁡{ak,min⁡l∈Nc∖{u}ckl}>0.F(+\infty)=\min_{k\in D_r}\min\left\{a_k,\min_{l\in N_c\setminus\{u\}}c_{kl}\right\}>0.

The analogous statements hold for GG after interchanging the players.

Proof. The fraction in (2) is a linear-fractional function of ρ\rho, so its infimum is given by vertex values or by limits as unconstrained coordinates tend to infinity. The limit as an unconstrained coordinate ρl\rho_l (l∈Nc∖{u}l \in N_c \setminus\{u\}) tends to infinity is cklc_{kl}. The other candidates are obtained by setting the unconstrained coordinates to 00 and each bounded coordinate to either 00 or its upper endpoint. All these candidates are limits of admissible positive vectors, which proves equality in (3). Continuity and local Lipschitz continuity follow from the finite formula. For y2≥y1y_2 \ge y_1, the inclusion R(y2)⊆R(y1)R(y_2) \subseteq R(y_1) gives monotonicity. Taking limits in the finite formula gives the stated positive limit by admissibility. □\square

Define the sign thresholds of the envelopes by

X‾0=sup⁡{x:G(x)<0},Y‾0=sup⁡{y:F(y)<0}.\overline{X}_0 = \sup\{x : G(x) < 0\}, \qquad\overline{Y}_0 = \sup\{y : F(y) < 0\}.

and choose finite base points X0≥X‾0X_0 \ge\overline{X}_0 and Y0≥Y‾0Y_0 \ge\overline{Y}_0. Such choices exist by Lemma 2.1. Define the oriented integrals

Γ(x)=∫X0x∣G(s)∣ ds,Λ(y)=∫Y0y∣F(s)∣ ds,E(p,q)=Γ(X)+Λ(Y),(4)\Gamma(x) = \int_{X_0}^{x} |G(s)|\,\mathrm{d}s, \qquad\Lambda(y) = \int_{Y_0}^{y} |F(s)|\,\mathrm{d}s, \qquad E(p,q) = \Gamma(X) + \Lambda(Y), \tag*{(4)}

and the capture region S={(p,q)∈D∘:E(p,q)>0}\mathcal{S} = \{(p,q) \in D^\circ: E(p,q) > 0\}. Smaller admissible finite base points give a larger capture region. When both thresholds X‾0,Y‾0\overline{X}_0,\overline{Y}_0 are finite, choosing them as the base points maximizes the capture region.

Idea of the construction. As shown in the proof below, the growth rates of X,YX,Y are bounded below by F(Y)F(Y) and G(X)G(X), respectively (equation (5)). Replacing the inequalities with equalities gives the comparison system x˙=F(y), y˙=G(x)\dot{x} = F(y),\ \dot{y} = G(x). This system is separable and preserves ∫G dx−∫F dy\int G\,\mathrm{d}x - \int F\,\mathrm{d}y. The function EE aligns the signs in this first integral in favor of the target. Indeed, in a region where exactly one envelope is negative (for example, G(x)<0<F(y)G(x) < 0 < F(y)), the comparison system satisfies E˙=∣G(x)∣F(y)+∣F(y)∣G(x)=0\dot{E} = |G(x)|F(y) + |F(y)|G(x) = 0. Thus, even if one coordinate lies below its threshold, E>0E > 0 can hold when the other integral is sufficiently large. This is the compensation between the two players.

Theorem 2.2. For any admissible pair of action sets, shifts, and finite base points as above, S\mathcal{S} is a nonempty open forward-invariant subset of D∘D^\circ. Along its trajectories, EE is nondecreasing and pt(τ)→1p_t(\tau) \to1, qu(τ)→1q_u(\tau) \to1. In particular, S\mathcal{S} has positive relative Lebesgue measure and is contained in the basin of attraction of (t,u)(t,u) under (1).

Proof. Taking differences of logarithmic derivatives gives

ξ˙k=(Aq)t−(Aq)k,η˙l=(BTp)u−(BTp)l.\dot{\xi}_k = (Aq)_t - (Aq)_k, \qquad\dot{\eta}_l = (B^{\mathsf T}p)_u - (B^{\mathsf T}p)_l.

Substituting ρl=ql/qu\rho_l = q_l/q_u gives the fraction in (2). Since ρ∈R(Y)\rho\in R(Y), every log ratio associated with a dangerous row action has derivative at least F(Y)F(Y). Similarly, every log ratio associated with a dangerous column action has derivative at least G(X)G(X). These derivatives are bounded by the finite payoff differences. Hence X,YX,Y are Lipschitz functions of time. The right derivative of the minimum of finitely many C1C^1 functions equals the smallest derivative among the active indices. Therefore,

D+X≥F(Y),D+Y≥G(X),(5)D_+X \ge F(Y), \qquad D_+Y \ge G(X), \tag*{(5)}

where D+D_+ denotes the lower right Dini derivative. In particular, these inequalities hold for the ordinary derivatives almost everywhere.

The functions Γ,Λ\Gamma,\Lambda are C1C^1 and nondecreasing. The base point conditions and monotonicity imply

F(y)<0⟹Λ(y)<0,Λ(y)>0⟹F(y)>0,F(y) < 0 \Longrightarrow\Lambda(y) < 0, \qquad\Lambda(y) > 0 \Longrightarrow F(y) > 0,

together with the corresponding implications for G,ΓG,\Gamma. Moreover, Λ(y)→∞\Lambda(y)\to\infty, Γ(x)→∞\Gamma(x)\to\infty as their arguments tend to infinity. Along any trajectory, EE is locally absolutely continuous, and the chain rule gives

E˙≥∣G(X)∣F(Y)+∣F(Y)∣G(X)\dot{E}\ge|G(X)|F(Y)+|F(Y)|G(X)

almost everywhere. The right-hand side can be negative only when both F(Y)F(Y) and G(X)G(X) are negative. In that case, both oriented integrals are negative, so E<0E<0. Thus, on every interval on which E≥0E\ge0, we have E˙≥0\dot{E}\ge0 almost everywhere. If E(0)=e0>0E(0)=e_0>0, integration up to the first possible exit from {E>0}\{E>0\} shows that E(τ)≥e0E(\tau)\ge e_0 up to that time. Continuity rules out an exit in finite time. This proves forward invariance and monotonicity on S\mathcal{S}.

We next show that both minimum log ratios tend to infinity. Set

y∗=min⁡{y:Λ(y)≥e0},x∗=min⁡{x:Γ(x)≥e0},δ=min⁡{F(y∗),G(x∗)}>0.y_*=\min\{y:\Lambda(y)\ge e_0\},\quad x_*=\min\{x:\Gamma(x)\ge e_0\},\quad\delta=\min\{F(y_*),G(x_*)\}>0.

These minima exist because the integrals are nonpositive below their finite base points and tend to infinity above them. If X<X0X<X_0, then Γ(X)≤0\Gamma(X)\le0, so Λ(Y)≥e0\Lambda(Y)\ge e_0 and D+X≥δD_+X\ge\delta. Similarly, whenever Y<Y0Y<Y_0, we have D+Y≥δD_+Y\ge\delta. If a coordinate were to fall below its base point after reaching it, it would have to increase throughout that excursion, a contradiction. Thus each base point is reached in finite time and is never crossed downward thereafter. At some finite time T0T_0, both X≥X0X\ge X_0 and Y≥Y0Y\ge Y_0 hold. Both coordinates are subsequently nondecreasing by (5). Since E(T0)>0E(T_0)>0, at least one of the integrals is positive. For example, if Λ(Y(T0))>0\Lambda(Y(T_0))>0, then D+X≥F(Y(T0))>0D_+X\ge F(Y(T_0))>0 thereafter. Hence X→∞X\to\infty, and eventually D+Y≥G(+∞)/2>0D_+Y\ge G(+\infty)/2>0. The other case follows by interchanging the players. Thus, after a finite time, both coordinates grow at least linearly. The bounds pk≤e−κk−Xp_k\le e^{-\kappa k-X} and ql≤e−μl−Yq_l\le e^{-\mu l-Y} then imply that the probabilities of all dangerous actions decay exponentially.

Follow a finite elimination sequence witnessing admissibility of the remaining subgame. Inductively, suppose that, for some C,γ>0C,\gamma>0, the total probability of the actions already eliminated, including the dangerous actions, is bounded by Ce−γτCe^{-\gamma\tau}. When a row action kk is next eliminated because it is dominated by a remaining action jj, let the minimum of Ajl−AklA_{jl}-A_{kl} over the remaining columns be h>0h>0, and set M=2max⁡i,l∣Ail∣M=2\max_{i,l}|A_{il}|. Then

ddτlog⁡pjpk≥h−(h+M)Ce−γτ≥h/2\frac{d}{d\tau}\log\frac{p_j}{p_k}\ge h-(h+M)Ce^{-\gamma\tau}\ge h/2

for all sufficiently large τ\tau. Since pj≤1p_j\le1, this yields an exponential upper bound on pkp_k. The column step is identical. Adjusting the constants at each of the finitely many steps proves the decay of all nontarget actions and hence convergence to (t,u)(t,u). Finally, EE is continuous on the original domain. Taking pt,pup_t,p_u sufficiently close to 11 makes both integrals positive. Thus S\mathcal{S} is nonempty and open and has positive relative measure. □\square

Remark 2.3 (Order relative to the comparison system). By Lemma 2.1, F,GF,G are locally Lipschitz and nondecreasing, so the comparison system x˙=F(y), y˙=G(x)\dot{x}=F(y),\ \dot{y}=G(x) is cooperative: the growth rate of each component is nondecreasing in the other component. For the solution of the comparison system starting at (x(0),y(0))=(X(0),Y(0))(x(0),y(0))=(X(0),Y(0)), we have X(τ)≥x(τ), Y(τ)≥y(τ)X(\tau)\ge x(\tau),\ Y(\tau)\ge y(\tau) for all τ≥0\tau\ge0. Indeed, lower each component of the comparison vector field by ε>0\varepsilon>0, where xε,yεx_\varepsilon,y_\varepsilon solve the resulting system. By (5) and the monotonicity of F,GF,G, the right Dini derivatives of X−xεX-x_\varepsilon and Y−yεY-y_\varepsilon are at least ε\varepsilon as long as both differences are nonnegative. A continuous function with positive right Dini derivative is increasing, so both differences remain positive at positive times. Letting ε→0\varepsilon\to0 gives the claim. This is the same argument used to prove order preservation for cooperative systems [4 Theorem 3.2]. The proof of Theorem 2.2 uses only the monotonicity of EE, without invoking this order relation.

Example: convergence with compensation in rock–paper–scissors with coordination

This section gives an example in which the compensation in Theorem 2.2 is effective. The certificate establishes convergence from an initial state at which the probability of the target action initially decreases.

Add a coordination action 0 to a three-action constant-sum rock–paper–scissors game. We refer to actions 1, 2, 3 as the rock–paper–scissors actions. When both players choose coordination, each receives 2; when one chooses coordination and the other does not, each receives 0. The payoff matrices are

A=(2000010202100021),B=(2000012000120201).(6)A = \begin{pmatrix} 2 & 0 & 0 & 0 \\ 0 & 1 & 0 & 2 \\ 0 & 2 & 1 & 0 \\ 0 & 0 & 2 & 1 \end{pmatrix}, \qquad B = \begin{pmatrix} 2 & 0 & 0 & 0 \\ 0 & 1 & 2 & 0 \\ 0 & 0 & 1 & 2 \\ 0 & 2 & 0 & 1 \end{pmatrix}. \tag*{(6)}

Equivalently, the rock–paper–scissors blocks are 1+K\mathbf{1}+K and 1−K\mathbf{1}-K, where K=(0−1110−1−110)K = \begin{pmatrix} 0 & -1 & 1 \\ 1 & 0 & -1 \\ -1 & 1 & 0 \end{pmatrix}. The target (0,0)(0,0) is a strict pure Nash equilibrium, with unilateral payoff gaps equal to 2 for both players. Take Dr=Dc={1,2,3}D_r=D_c=\{1,2,3\} and set all shifts to 0. These sets are admissible because their complements contain only the target action.

For every dangerous action, the payoff differences between the target and that action against the opponent’s rock–paper–scissors actions are a permutation of (−2,−1,0)(-2,-1,0). Both envelopes therefore equal ff, where, writing s=e−ys=e^{-y},

f(y)={2−2s1+s,s≥3,2−3s1+2s,2/3≤s≤3,2−3s1+3s,0<s≤2/3.(7)f(y)= \begin{cases} \frac{2-2s}{1+s}, & s \ge3,\\ \frac{2-3s}{1+2s}, & 2/3 \le s \le3,\\ \frac{2-3s}{1+3s}, & 0 < s \le2/3. \end{cases} \tag*{(7)}

Its unique zero is ζ=log⁡(3/2)\zeta=\log(3/2). Use this minimal base point in both integrals in (4). This gives E=H(X)+H(Y)E=H(X)+H(Y), with H(z)=∫ζz∣f(v)∣ dvH(z)=\int_{\zeta}^{z}|f(v)|\,dv. Figure 1 shows the capture region and the comparison system. As explained in Remark 2.3, the original trajectory never lies below the comparison trajectory in either coordinate.

Figure 1. Capture region and comparison system for the example in § 3, in minimum log-ratio coordinates. The green shading and dashed lines show the invariant box {F(Y)>0, G(X)>0}\{F(Y)>0,\ G(X)>0\}; the orange shading shows the region where compensation gives E>0E>0; the black curve is E=0E=0; and the gray arrows show the vector field of the comparison system. The purple dashed curve is the comparison trajectory from the marked initial state, and the orange solid curve is the original trajectory from the same initial state mapped to (X,Y)(X,Y). Thin lines connect the positions at the same times τ=0.5,1,1.5,2\tau=0.5,1,1.5,2. Both trajectories are obtained by numerical integration.

Proposition 3.1. For the matrices in (6), the interior initial state

p=(2,1,3,14)20,q=(512,16,2,1)531(8)p=\frac{(2,1,3,14)}{20}, \qquad q=\frac{(512,16,2,1)}{531} \tag*{(8)}

converges to (0,0)(0,0). At this initial state, the probability of the column player’s target action initially decreases, and action 0 is not a best response for the column player. These conclusions hold throughout an open neighbourhood of this initial state in the original six-dimensional positive state space.

Proof. In the finite representation of Lemma 2.1, all weights are equal, so the denominator depends only on ∣T∣|T|. For each ∣T∣|T|, it therefore suffices to choose the smallest payoff differences (a special case of Proposition 5.1). Thus the envelope reduces to the minimum of

g0=2,g1=2−2s1+s,g2=2−3s1+2s,g3=2−3s1+3s.g_0=2,\qquad g_1=\frac{2-2s}{1+s},\qquad g_2=\frac{2-3s}{1+2s},\qquad g_3=\frac{2-3s}{1+3s}.

After multiplication by the positive denominators, the numerators of g1−g2g_1-g_2, g2−g3g_2-g_3, and g1−g3g_1-g_3 are s(3−s)s(3-s), s(2−3s)s(2-3s), and s(5−3s)s(5-3s), respectively. This proves (7). At (8), the active minimizers are unique, and

X=log⁡(p0/p3)=−log⁡7<ζ<log⁡32=log⁡(q0/q1)=Y.X=\log(p_0/p_3)=-\log7<\zeta<\log32=\log(q_0/q_1)=Y.

To evaluate EE exactly, set β=−log⁡3\beta=-\log3 at the branch boundary and define the primitives

J1(y)=2y+4log⁡(1+e−y),J2(y)=2y+72log⁡(1+2e−y),J3(y)=2y+3log⁡(1+3e−y).\begin{aligned} J_1(y)&=2y+4\log(1+e^{-y}),\\ J_2(y)&=2y+\frac{7}{2}\log(1+2e^{-y}),\\ J_3(y)&=2y+3\log(1+3e^{-y}). \end{aligned}

Each derivative is the corresponding branch of ff. Since ff is negative below ζ\zeta and positive above ζ\zeta,

E=J1(β)−J1(X)+J2(ζ)−J2(β)+J3(Y)−J3(ζ).E=J_1(\beta)-J_1(X)+J_2(\zeta)-J_2(\beta)+J_3(Y)-J_3(\zeta).

Substituting e−X=7e^{-X}=7, e−β=3e^{-\beta}=3, e−ζ=2/3e^{-\zeta}=2/3, and e−Y=1/32e^{-Y}=1/32 gives the following exact comparison, an instance of the procedure in Proposition 5.2:

e2E=56710218313=4413675765625417942208512>1.e^{2E}=\frac{5^6 7^{10}}{2^{18}3^{13}}=\frac{4413675765625}{417942208512}>1.

Hence E>0E>0, and Theorem 2.2 gives convergence to the target.

At this initial state, the row fitnesses are (1024/531,2/59,34/531,5/531)(1024/531,2/59,34/531,5/531), and the column fitnesses are (1/5,29/20,1/4,1)(1/5,29/20,1/4,1). Therefore,

X˙=1019531>F(Y)=6135,X˙−F(Y)=327418585,Y˙=−54>G(X)=−32,Y˙−G(X)=14.\begin{aligned} \dot{X}&=\frac{1019}{531}>F(Y)=\frac{61}{35},& \dot{X}-F(Y)&=\frac{3274}{18585},\\ \dot{Y}&=-\frac{5}{4}>G(X)=-\frac{3}{2},& \dot{Y}-G(X)&=\frac{1}{4}. \end{aligned}

In particular, for the column player, action 0 has lower fitness than every rock–paper–scissors action, and

q˙0=−535041409805<0.\dot{q}_0=-\frac{53504}{1409805}<0.

The inequalities E>0E>0 and q˙0<0\dot{q}_0<0, together with the strict payoff inequalities excluding the target action as a best response, persist on an open neighbourhood by continuity. □

Comparison with other regions. This initial state lies outside the box {X>ζ,Y>ζ}\{X>\zeta,Y>\zeta\} where both envelopes are positive. It also lies outside the elementary rectangle {p0>1/2,q0>1/2}\{p_0>1/2,q_0>1/2\} in the two target-action probabilities (here p0=1/10p_0=1/10). Against any mixed strategy of the opponent, the payoff differences between the target and a rock–paper–scissors action are at least 4q0−24q_0-2 and 4p0−24p_0-2, respectively, so this rectangle is a forward-invariant subset of the basin. The certificate predicts that q0q_0, which initially decreases, eventually reverses direction.

Absence of a potential. This game lies outside the class of potential games [6 Section 2, Lemma 2.3]. Among the rock–paper–scissors action profiles,

(2,1)→(2,3)→(1,3)→(1,2)→(3,2)→(3,1)→(2,1)(2,1)\to(2,3)\to(1,3)\to(1,2)\to(3,2)\to(3,1)\to(2,1)

is a cycle of unilateral strict improvements, with the deviating player receiving payoff 2 at every step. An ordinal potential that strictly increases along this cycle cannot return to its initial value. Hence no ordinal potential exists, and therefore no exact potential exists.

Convergence to the target is not global. At the strategy profile in which both players mix uniformly over the rock–paper–scissors actions, e=(0,1/3,1/3,1/3)e=(0,1/3,1/3,1/3), the fitness of each rock–paper–scissors action is 1, whereas that of the absent target action is 0. In fact, the curve

p=q=(α,1−α3,1−α3,1−α3),0<α<1/3,p=q=\left(\alpha,\frac{1-\alpha}{3},\frac{1-\alpha}{3},\frac{1-\alpha}{3}\right), \qquad0<\alpha<1/3,

is invariant. Along this curve, α˙=α(1−α)(3α−1)<0\dot{\alpha}=\alpha(1-\alpha)(3\alpha-1)<0, so every trajectory on it converges to ee. Thus not every interior initial state converges to the target.

Explicit boxes, volumes, and time bounds

We now construct boxes inside the capture region, derive closed-form expressions for their probabilities, and obtain upper bounds on convergence times. These boxes give coarser certificates than the capture region, but all quantities can be computed directly from the payoffs.

For a real number zz, write z−=max⁡{−z,0}z^{-}=\max\{-z,0\} and [z]+=max⁡{z,0}[z]_{+}=\max\{z,0\}. The thresholds in § 2 have the closed forms

Xˉ0=log⁡max⁡l∈Dc∑k∈Dre−κkdlkbl,Yˉ0=log⁡max⁡k∈Dr∑l∈Dce−μlcklak.(9)\bar{X}_{0}=\log\max_{l\in D_{c}}\frac{\sum_{k\in D_{r}}e^{-\kappa_{k}}d_{lk}}{b_{l}},\qquad\bar{Y}_{0}=\log\max_{k\in D_{r}}\frac{\sum_{l\in D_{c}}e^{-\mu_{l}}c_{kl}}{a_{k}}. \tag*{(9)}

where log⁡0=−∞\log0=-\infty. Indeed, minimizing each numerator over its bounded coordinates selects exactly the negative coefficients. All such numerators are positive above the largest root, whereas at least one is negative below it. The constants associated with unconstrained coordinates are positive. Thus G(x)>0G(x)>0 for x>Xˉ0x>\bar{X}_{0} and G(x)<0G(x)<0 for x<Xˉ0x<\bar{X}_{0}; the analogous statements hold for FF.

Let νD\nu_{D} be the product of the uniform probability measures on the two simplices. This is the normalized relative Lebesgue measure on the ambient product space, rather than volume on a lower-dimensional invariant face. For finite xˉ>Xˉ0\bar{x}>\bar{X}_{0} and yˉ>Yˉ0\bar{y}>\bar{Y}_{0}, define the following subset of D∘D^{\circ}, which is a box in the selected log-ratio coordinates:

B(xˉ,yˉ)={ξk≥κk+xˉ (k∈Dr),ηl≥μl+yˉ (l∈Dc)}.B(\bar{x},\bar{y})=\{\xi_{k}\ge\kappa_{k}+\bar{x}\ (k\in D_{r}),\quad\eta_{l}\ge\mu_{l}+\bar{y}\ (l\in D_{c})\}.

Theorem 4.1. Every point in B(xˉ,yˉ)B(\bar{x},\bar{y}) converges to (t,u)(t,u), and

νD(B(xˉ,yˉ))=Vr(xˉ)Vc(yˉ),Vr(x)=∑T⊆Dr(−1)∣T∣1+∑k∈Te−κk−x,\nu_{D}(B(\bar{x},\bar{y}))=V_{r}(\bar{x})V_{c}(\bar{y}),\qquad V_{r}(x)=\sum_{T\subseteq D_{r}}\frac{(-1)^{|T|}}{1+\sum_{k\in T}e^{-\kappa_{k}-x}},

where VcV_{c} is defined by replacing (Dr,κ,x)(D_{r},\kappa,x) with (Dc,μ,y)(D_{c},\mu,y). Consequently, the probability of the target basin is at least Vr(Xˉ0)Vc(Yˉ0)V_{r}(\bar{X}_{0})V_{c}(\bar{Y}_{0}), where Vr(−∞)=Vc(−∞)=1V_{r}(-\infty)=V_{c}(-\infty)=1 is interpreted as a limit. Moreover, if xˉ≥X0\bar{x}\ge X_{0} and yˉ≥Y0\bar{y}\ge Y_{0}, with at least one strict inequality, then B(xˉ,yˉ)⊆SB(\bar{x},\bar{y})\subseteq S (within the range xˉ>Xˉ0\bar{x}>\bar{X}_{0}, yˉ>Yˉ0\bar{y}>\bar{Y}_{0} in which the box is defined).

Proof. As long as X≥xˉX\ge\bar{x} and Y≥yˉY\ge\bar{y}, their derivatives are bounded below by F(yˉ)>0F(\bar{y})>0 and G(xˉ)>0G(\bar{x})>0, respectively. The box is therefore invariant, both minima grow linearly, and convergence follows from the elimination argument in the proof of Theorem 2.2. For the probability formula, represent a uniformly distributed point on a simplex by independent unit-rate exponential random variables ZiZ_i normalized by their sum. Writing hk=eκk+xh_k=e^{\kappa_k+x} and conditioning on ZtZ_t gives

Pr⁡(Zk≤Zt/hk ∀k∈Dr)=E∏k∈Dr(1−e−Zt/hk)=Vr(x).\Pr\left(Z_k\le Z_t/h_k\ \forall k\in D_r\right)=\mathbb{E}\prod_{k\in D_r}\left(1-e^{-Z_t/h_k}\right)=V_r(x).

Independence across players gives the product. Lowering the bounds xˉ,yˉ\bar{x},\bar{y} to the thresholds yields the basin bound by continuity from below. Under the additional base point conditions, both integrals are nonnegative and one is positive.

Theorem 4.2. Let Dr=I∖{t}D_r = I \setminus\{t\} and Dc=J∖{u}D_c = J \setminus\{u\}, and suppose that the initial point lies in B(xˉ,yˉ)\mathcal{B}(\bar{x},\bar{y}). Write Cr=∑k≠te−κˉkC_r = \sum_{k\ne t} e^{-\bar{\kappa}_k} and Cc=∑l≠ue−μˉlC_c = \sum_{l\ne u} e^{-\bar{\mu}_l}. For every τ≥0\tau\ge0,

1−pt(τ)≤Cre−xˉ−F(yˉ)τ,1−qu(τ)≤Cce−yˉ−G(xˉ)τ.1-p_t(\tau) \le C_r e^{-\bar{x}-F(\bar{y})\tau}, \qquad1-q_u(\tau) \le C_c e^{-\bar{y}-G(\bar{x})\tau}.

For 0<ε<10 < \varepsilon< 1, the earliest time after which both errors remain at most ε\varepsilon is bounded above by

max⁡{[log⁡(Cr/ε)−xˉ]+F(yˉ),[log⁡(Cc/ε)−yˉ]+G(xˉ)}.\max\left\{\frac{[\log(C_r/\varepsilon)-\bar{x}]_+}{F(\bar{y})},\frac{[\log(C_c/\varepsilon)-\bar{y}]_+}{G(\bar{x})}\right\}.

Proof. Invariance of the box gives X(τ)≥xˉ+F(yˉ)τX(\tau) \ge\bar{x}+F(\bar{y})\tau and Y(τ)≥yˉ+G(xˉ)τY(\tau) \ge\bar{y}+G(\bar{x})\tau. Sum the individual ratio bounds over all nontarget actions and solve the exponential inequalities.

Finite evaluation and exact membership tests

We show that the envelopes F,GF,G can be evaluated using a number of candidates proportional to the number of actions, rather than the number of action subsets (Proposition 5.1), and that, for rational data, the sign of EE can be determined by a finite exact computation (Proposition 5.2).

Fix a row k∈Drk \in D_r, abbreviate a=aka=a_k and cl=cklc_l=c_{kl}, and set s=e−y>0s=e^{-y}>0 and wl=e−μl>0w_l=e^{-\mu_l}>0. Write

RT(s)=a+sCT1+sDT,CT=∑l∈Twlcl,DT=∑l∈Twl.R_T(s)=\frac{a+sC_T}{1+sD_T}, \qquad C_T=\sum_{l\in T}w_lc_l,\qquad D_T=\sum_{l\in T}w_l.

The remaining candidates in the envelope are the constants associated with the unconstrained coordinates.

Proposition 5.1 (Prefix representation). Sort the coefficients as c(1)≤⋯≤c(d)c_{(1)}\le\cdots\le c_{(d)}, breaking ties in any fixed order. Let Cj,DjC_j,D_j be the corresponding prefix sums, including C0=D0=0C_0=D_0=0. Then, for every s>0s>0,

min⁡T⊆{1,…,d}RT(s)=min⁡0≤j≤da+sCj1+sDj.\min_{T\subseteq\{1,\ldots,d\}}R_T(s)=\min_{0\le j\le d}\frac{a+sC_j}{1+sD_j}.

This order depends on neither ss nor the positive weights.

Proof. Choose a minimizing subset TT and write r=RT(s)r=R_T(s). For l∉Tl\notin T and l∈Tl\in T, respectively,

RT∪{l}(s)−r=swl(cl−r)1+s(DT+wl),RT∖{l}(s)−r=swl(r−cl)1+s(DT−wl).R_{T\cup\{l\}}(s)-r=\frac{sw_l(c_l-r)}{1+s(D_T+w_l)}, \qquad R_{T\setminus\{l\}}(s)-r=\frac{sw_l(r-c_l)}{1+s(D_T-w_l)}.

Both denominators are positive. Optimality therefore requires that TT contain every ll with cl<rc_l<r and that TT contain no ll with cl>rc_l>r. Removing terms with cl=rc_l=r leaves the value unchanged. The remaining set is a sorted prefix, possibly empty.

For rr rows and dd dangerous actions of the opponent, preprocessing sorts each row and computes its prefix sums. This requires O(rdlog⁡d)O(rd\log d) comparisons and arithmetic operations when d≥2d\ge2; the cases d≤1d\le1 are handled directly. Reducing the unconstrained-coordinate constants to one minimum per row requires one additional pass through those entries. Evaluation at a fixed yy then uses the unconstrained-coordinate constants and r(d+1)r(d+1) fractional candidates. A constant arising from an unconstrained coordinate remains a candidate for the infimum even if no positive vector attains it. The same procedure evaluates GG.

Proposition 5.2 (Exact sign determination). Assume that all payoff entries are rational, the weights e−μle^{-\mu_l} and e−κke^{-\kappa_k} are positive rational numbers, and all coordinates of the initial point are positive rational numbers. Suppose further that the given admissible base points satisfy e−X0,e−Y0∈Q>0e^{-X_0},e^{-Y_0}\in\mathbb{Q}_{>0}, with these exponentials specified by defining polynomials and rational isolating intervals. Then the sign of the quantity EE in (4), including the case E=0E=0, can be determined by finitely many exact real algebraic operations.

Proof. Each prefix branch or constant branch, expressed in the variable s=e−ys=e^{-y}, has the form

g(s)=a+Cs1+Ds,a,C,D∈Q,D≥0.g(s)=\frac{a+Cs}{1+Ds},\qquad a,C,D\in\mathbb{Q},\quad D\geq0.

Here D=0D=0 implies C=0C=0: a prefix with positive weights must then be empty, and an unconstrained-coordinate branch is constant. The equation determining intersections of two branches is

(a1+C1s)(1+D2s)−(a2+C2s)(1+D1s)=0.(a_1+C_1s)(1+D_2s)-(a_2+C_2s)(1+D_1s)=0.

Its left-hand side is a polynomial of degree at most two. Identical branches are merged, and linear and constant cases are handled according to their actual degree. Also include the positive roots of a+Cs=0a+Cs=0 for nonzero numerators. These finitely many algebraic breakpoints partition any compact positive ss interval into cells on which the minimizing branch and its sign can be selected exactly by sampling rational interior points. Ties do not change the value, and an identically zero branch contributes 0.

For D>0D>0, an antiderivative with respect to yy is

J(y)=ay+(a−C/D)log⁡(1+De−y),J′(y)=a+Ce−y1+De−y.J(y)=ay+(a-C/D)\log(1+De^{-y}),\qquad J'(y)=\frac{a+Ce^{-y}}{1+De^{-y}}.

For D=0D=0, an antiderivative is ayay. Integrate ∣F∣|F| and ∣G∣|G| using the sign of the branch on each cell, preserving the orientation when the endpoint coordinate lies below its base point. The transformed endpoints corresponding to the initial point are rational; for example,

e−X=max⁡k(eκkpkpt)∈Q>0.e^{-X}=\max_k\left(e^{\kappa_k}\frac{p_k}{p_t}\right)\in\mathbb{Q}_{>0}.

Thus all interval endpoints are positive algebraic numbers, and y=−log⁡sy=-\log s gives

E=∑jθjlog⁡αj,θj∈Q,αj∈Q‾>0.E=\sum_j\theta_j\log\alpha_j,\qquad\theta_j\in\mathbb{Q},\quad\alpha_j\in\overline{\mathbb{Q}}_{>0}.

Choose a positive integer MM that clears the denominators of all θj\theta_j. Then P=∏jαjMθjP=\prod_j\alpha_j^{M\theta_j} is a positive real algebraic number, and P>1P>1, P=1P=1, and P<1P<1 correspond to E>0E>0, E=0E=0, and E<0E<0, respectively. Exact algebraic arithmetic and order comparisons complete the test. □

Thresholds for rational data. Under the assumptions of Proposition 5.2, formula (9) shows that finite thresholds X‾0,Y‾0\overline{X}_0,\overline{Y}_0 have positive rational exponentials e−X‾0,e−Y‾0e^{-\overline{X}_0},e^{-\overline{Y}_0}. They can therefore be used as the minimal base points. When a threshold is −∞-\infty (the set where the envelope is negative is empty), supply a separate finite admissible base point with an algebraic exponential.

Extension to multiplayer games

We extend the two-player comparison argument to NN players. In place of a closed-form integral test, we define the capture region by whether the flow of a cooperative comparison system enters the positive region.

Consider a finite NN-player game (N≥2N \ge2, ∣Si∣≥2|S_i| \ge2) with multilinear payoffs uiu_i, under replicator dynamics applied to each player’s mixed strategy on the product space DN∘=∏iΔ(Si)∘D_N^\circ= \prod_i \Delta(S_i)^\circ. Fix a strict pure Nash equilibrium s∗s^* and nonempty sets Di⊆Si∖{s∗}D_i \subseteq S_i \setminus\{s^*\}, and write Ni=Si∖DiN_i = S_i \setminus D_i. Assume that si∗s_i^* strictly outperforms each k∈Dik \in D_i against every pure profile in ∏j≠iNj\prod_{j \ne i} N_j, and that iterated elimination by strictly dominating pure strategies reduces ∏iNi\prod_i N_i to s∗s^*. These conditions always hold when all alternative actions are included in the selected sets.

Define the ratio coordinates and constrained opponent polytopes by

Xi(x)=min⁡k∈Dilog⁡xi,si∗xi,k,Cj(yj)={zj∈Δ(Sj):zj,l≤e−yjzj,sj∗ (l∈Dj)}.X_i(x) = \min_{k \in D_i} \log\frac{x_{i,s_i^*}}{x_{i,k}}, \qquad C_j(y_j) = \{z_j \in\Delta(S_j) : z_{j,l} \le e^{-y_j}z_{j,s_j^*}\ (l \in D_j)\}.

The cooperative lower envelopes are

Fi(y)=min⁡k∈Dimin⁡zj∈Cj(yj), j≠i[ui(si∗,z−i)−ui(k,z−i)].F_i(y) = \min_{k \in D_i}\min_{z_j \in C_j(y_j),\,j \ne i} [u_i(s_i^*,z_{-i}) - u_i(k,z_{-i})].

Each minimum can be taken over tuples of vertices. The vertices of Cj(yj)C_j(y_j) are ebe_b for b∈Nj∖{sj∗}b \in N_j \setminus\{s_j^*\} and

esj∗+e−yj∑l∈Tel1+∣T∣e−yj,T⊆Dj.\frac{e_{s_j^*} + e^{-y_j}\sum_{l \in T} e_l}{1+|T|e^{-y_j}}, \qquad T \subseteq D_j.

Thus FiF_i is locally Lipschitz, independent of yiy_i, and nondecreasing in every other coordinate. Because FiF_i is bounded by the game’s payoff differences, y˙=F(y)\dot y = F(y) has a unique global solution, denoted by Ψτ(y)\Psi_\tau(y). Set

P+={y:Fi(y)>0 for all i},U={y:Ψτ0(y)∈P+ for some τ0≥0},SN={x:X(x)∈U}.P^+ = \{y : F_i(y) > 0\ \text{for all }i\}, \quad U = \{y : \Psi_{\tau_0}(y) \in P^+\ \text{for some }\tau_0 \ge0\}, \quad S_N = \{x : X(x) \in U\}.

Theorem 6.1. The set SNS_N is nonempty, open, and forward invariant in the original product of simplex interiors. Every trajectory starting in SNS_N converges to s∗s^*.

Proof. Multilinearity allows successive minimization over the opponents’ vertices. Their finitely many smooth parametrizations imply local Lipschitz regularity, and the nested polytopes imply monotonicity. Along an actual trajectory, the ratio identity and differentiation of finite minima give D+Xi≥Fi(X)D^+X_i \ge F_i(X). The same comparison argument as in Remark 2.3 [4 Theorem 3.2] therefore yields X(τ)≥Ψτ(X(0))X(\tau) \ge\Psi_\tau(X(0)). Within P+P^+, every coordinate of the comparison system increases, so its envelope values cannot decrease. After entry at time τ0\tau_0, every coordinate increases at a rate of at least min⁡iFi(Ψτ0(y))>0\min_i F_i(\Psi_{\tau_0}(y)) > 0. The probabilities of dangerous actions therefore decay exponentially. At each subsequent strict-dominance elimination step, the positive payoff gap on the surviving opponent profiles is perturbed by the exponentially vanishing mass on previously deleted actions. The corresponding log ratio eventually increases at a positive rate. Induction eliminates every action other than si∗s_i^*.

As all opponent coordinates tend to infinity, the envelope limit is positive by the assumed payoff inequalities. Hence P+P^+ contains a sufficiently large upper orthant, and SNS_N contains the points of a relative neighbourhood of the target that lie in the original positive domain. Continuous dependence and continuity of XX imply openness. Order preservation makes UU an upper set; comparison and forward invariance of UU then imply forward invariance of SNS_N. ∎

Proposition 6.2 (Explicit multiplayer boxes). For a vector of box lower bounds θ∈RN\theta\in\mathbb{R}^{N}, write r−=max⁡{−r,0}r^{-}=\max\{-r,0\} and set

mik=min⁡s−i∈∏j≠iNj[ui(si∗,s−i)−ui(k,s−i)]>0,m_{ik}=\min_{s_{-i}\in\prod_{j\ne i}N_j}\left[u_i(s_i^*,s_{-i})-u_i(k,s_{-i})\right]>0,
Mik=max⁡s−i∈∏j≠iSj[ui(si∗,s−i)−ui(k,s−i)]−,εj=∣Dj∣e−θj1+∣Dj∣e−θj.M_{ik}=\max_{s_{-i}\in\prod_{j\ne i}S_j}\left[u_i(s_i^*,s_{-i})-u_i(k,s_{-i})\right]^{-},\qquad\varepsilon_j=\frac{|D_j|e^{-\theta_j}}{1+|D_j|e^{-\theta_j}}.

If every γi:=min⁡k∈Di{mik−(mik+Mik)∑j≠iεj}\gamma_i:=\min_{k\in D_i}\{m_{ik}-(m_{ik}+M_{ik})\sum_{j\ne i}\varepsilon_j\} is positive, then {x:Xi(x)≥θi ∀i}⊆SN\{x:X_i(x)\ge\theta_i\ \forall i\}\subseteq S_N. Its normalized uniform product measure is

∏i∑T⊆Di(−1)∣T∣1+∣T∣e−θi.\prod_i\sum_{T\subseteq D_i}\frac{(-1)^{|T|}}{1+|T|e^{-\theta_i}}.

Moreover, if the selected sets include all alternative actions, every initial point in this box satisfies 1−xi,si∗(τ)≤∣Di∣e−θi−γiτ1-x_{i,s_i^*}(\tau)\le|D_i|e^{-\theta_i-\gamma_i\tau}.

Proof. If Xj≥θjX_j\ge\theta_j, opponent jj assigns at most εj\varepsilon_j probability to dangerous actions. By the union bound, the probability that at least one opponent chooses a dangerous action is at most ∑j≠iεj\sum_{j\ne i}\varepsilon_j. The payoff gap is at least mikm_{ik} outside this event and at least −Mik-M_{ik} on it. Hence Fi≥γi>0F_i\ge\gamma_i>0 throughout the box, which is mapped into P+P^+. The measure follows by normalizing independent exponential random variables, as in Theorem 4.1. The time bound follows as in Theorem 4.2. □

Differences from the two-player case. Having NN comparison coordinates does not make vertex evaluation independent of the number of actions. Entry into P+P^+ provides a certificate verifiable in finite time, but no finite stopping test is obtained for points outside UU. Numerical verification requires error control for both the comparison trajectory and FF.

How much of the basin does the capture region cover?

This section examines how much of the target’s basin is covered by the capture region. In two-action coordination games, the two sets coincide. In general, the capture region is a subset of the basin, but every point in the basin enters the capture region in finite time. Finally, numerical experiments on random games measure the gap between the two sets.

Two-action coordination games.

Proposition 7.1 (Equality in two-action coordination games). Let n=m=2n=m=2, and write I={t,k}I=\{t,k\}, J={u,l}J=\{u,l\}. Suppose that both (t,u)(t,u) and (k,l)(k,l) are strict pure Nash equilibria. For any shifts, choosing the thresholds X0=Xˉ0X_0=\bar{X}_0, Y0=Yˉ0Y_0=\bar{Y}_0 as the base points gives

S={E>0}=basin⁡(t,u),{E<0}=basin⁡(k,l).S=\{E>0\}=\operatorname{basin}(t,u),\qquad\{E<0\}=\operatorname{basin}(k,l).

The set {E=0}\{E=0\} consists of the interior mixed equilibrium and the trajectories converging to it.

Proof. We have Dr={k}D_r=\{k\}, Dc={l}D_c=\{l\}, and a=ak>0a=a_k>0, b=bl>0b=b_l>0. Since (k,l)(k,l) is strict, c=ckl<0c=c_{kl}<0, d=dlk<0d=d_{lk}<0. The fraction in (2) is strictly decreasing in ρ\rho, so its infimum is attained at the upper endpoint ρ=e−μ−y\rho=e^{-\mu-y}, giving

F(y)=a+ce−μ−y1+e−μ−y,G(x)=b+de−κ−x1+e−κ−x.F(y)=\frac{a+ce^{-\mu-y}}{1+e^{-\mu-y}},\qquad G(x)=\frac{b+de^{-\kappa-x}}{1+e^{-\kappa-x}}.

Moreover, ql/qu=e−μ−Yq_l/q_u=e^{-\mu-Y}, pk/pt=e−κ−Xp_k/p_t=e^{-\kappa-X}, so the comparison inequalities become equalities: X˙=F(Y)\dot{X}=F(Y), Y˙=G(X)\dot{Y}=G(X). The functions F,GF,G are strictly increasing, with zeros Yˉ0=log⁡(−c/a)−μ\bar{Y}_0=\log(-c/a)-\mu, Xˉ0=log⁡(−d/b)−κ\bar{X}_0=\log(-d/b)-\kappa, and (Xˉ0,Yˉ0)(\bar{X}_0,\bar{Y}_0) corresponds to the interior mixed equilibrium. When X>Xˉ0X>\bar{X}_0, Y>Yˉ0Y>\bar{Y}_0, both integrals are positive and E>0E>0, so Theorem 2.2 implies convergence to (t,u)(t,u). When X≤Xˉ0X\leq\bar{X}_0, Y≤Yˉ0Y\leq\bar{Y}_0 and (X,Y)≠(Xˉ0,Yˉ0)(X,Y)\ne(\bar{X}_0,\bar{Y}_0), we have E<0E<0. Both X,YX,Y are nonincreasing and, after any positive time, decrease at rates bounded away from zero, so the trajectory converges to (k,l)(k,l). In the region X<Xˉ0X<\bar{X}_0, Y>Yˉ0Y>\bar{Y}_0, we have E˙=∣G(X)∣F(Y)+∣F(Y)∣G(X)=0\dot{E}=|G(X)|F(Y)+|F(Y)|G(X)=0, while XX increases and YY decreases. A trajectory that remains in this region is monotone and bounded, so it converges to a stationary point. The only stationary point in the closure is (Xˉ0,Yˉ0)(\bar{X}_0,\bar{Y}_0), where E=0E=0. Thus, a trajectory with E>0E>0 passes through X=Xˉ0X=\bar{X}_0, Y>Yˉ0Y>\bar{Y}_0 in finite time and enters {X>Xˉ0,Y>Yˉ0}\{X>\bar{X}_0,Y>\bar{Y}_0\}; a trajectory with E<0E<0 passes through Y=Yˉ0Y=\bar{Y}_0, X<Xˉ0X<\bar{X}_0 and enters {X≤Xˉ0,Y≤Yˉ0}\{X\leq\bar{X}_0,Y\leq\bar{Y}_0\}; and a trajectory with E=0E=0 converges to the mixed equilibrium. The remaining region {X>Xˉ0,Y<Yˉ0}\{X>\bar{X}_0,Y<\bar{Y}_0\} is treated in the same way by interchanging the players.

This proposition recovers, from the present construction, the description of basin boundaries through a conserved quantity by Zhang and Hofbauer [8 Eqs. (10)–(12)] and the exact description of the Stag Hunt basin by Panageas and Piliouras [7 Theorem 5.1]. With three or more actions, the comparison generally gives inequalities, and the capture region is a proper subset of the basin.

Pullback

Remark 7.2 (Relation to the full basin). Any single capture region satisfies basin⁡(t,u)=⋃τ≥0ϕ−τ(S)\operatorname{basin}(t,u)=\bigcup_{\tau\geq0}\phi^{-\tau}(\mathcal{S}). Indeed, a convergent trajectory eventually enters a neighbourhood of the target, and S\mathcal{S} contains a relative neighbourhood of the target. These preimages are nested, so their probabilities increase to the probability of the basin.

Numerical setup. For each number of actions n=2,…,6n=2,\ldots,6, we generate 100 n×nn\times n bimatrix games with payoffs drawn independently and uniformly from [0,1][0,1], conditional on the existence of a strict pure Nash equilibrium, and select one such equilibrium uniformly as the target. For each game, we draw 2000 initial states from the uniform prior. The selected sets include all nontarget actions, and the base points are the thresholds Xˉ0,Yˉ0\bar{X}_0,\bar{Y}_0 (when a threshold is −∞-\infty, we use the union of the capture regions over finite base points). The certificate integrals are evaluated numerically, branch by branch, using the primitives in § 5. We compare the following four fractions (Table 1).

Actions nnBasinBoxCapture regionShiftedUnresolved
292.3%62.6%92.3%92.3%0.0%
383.2%13.1%47.5%55.4%8.0%
468.1%1.7%7.2%14.0%15.3%
555.9%0.1%0.6%2.7%28.2%
656.9%0.0%0.1%0.7%30.2%

Table 1. Mean fractions across 100 random n×nn \times n games, with 2000 initial states per game. “Unresolved” denotes the fraction of initial states that neither entered the box of any strict pure equilibrium by the cutoff nor were classified as satisfying E>0E > 0.

  • Basin: the fraction of initial states whose numerically integrated trajectories converge to the target. A trajectory is classified as converging to a strict pure equilibrium as soon as it enters that equilibrium’s invariant box (Theorem 4.1); integration stops at time 1000.

  • Box: the fraction lying in the invariant box {X>Xˉ0, Y>Yˉ0}\{X>\bar{X}_0,\ Y>\bar{Y}_0\} with zero shifts.

  • Capture region: the fraction satisfying E>0E>0 with zero shifts.

  • Shifted capture region: the fraction satisfying E>0E>0 for at least one of 16 choices of shifts for the dangerous actions. To choose the shifts, let hl=max⁡kckl/akh_l=\max_k c_{kl}/a_k measure how unfavorable the column action ll is to the row player’s target, and set e−μl=(hl+0.05)−γe^{-\mu_l}=(h_l+0.05)^{-\gamma}, γ∈{0,12,1,2}\gamma\in\{0,\frac{1}{2},1,2\}; the row shifts are chosen analogously. This choice constrains more unfavorable actions more tightly. The certificate is valid for every choice of shifts, so the union is also valid.

Observations.

  • Among the 10610^{6} initial states in total, none classified as satisfying E>0E > 0 converged to a different equilibrium under numerical integration. Conversely, some initial states satisfied E>0E > 0 but remained unresolved by numerical integration at the cutoff (122 for n=2n = 2 and 784 for n=3n = 3). These are counted in the basin column.

  • For n=2n = 2, the capture-region fraction equals the basin fraction, consistent with Proposition 7.1.

  • The effect of compensation is clear. The capture region covers approximately 3.6 to 4.2 times as many initial states as the box (n=3,4,5n = 3, 4, 5). Shifts expand this further by a factor ranging from 1.2 (n=3n = 3) to 4.4 (n=5n = 5).

  • As the number of actions increases, however, the fraction covered by the capture region decreases rapidly. The ratio of the shifted capture-region fraction to the basin fraction is approximately two-thirds for n=3n = 3, one-fifth for n=4n = 4, and one-twentieth for n=5n = 5.

  • The unresolved fraction increases with the number of actions (approximately 30% for n=6n = 6). These cases may correspond to cycling trajectories or trajectories with very slow convergence.

Entry times. By Remark 7.2, every trajectory converging to the target enters the capture region in finite time. The same holds for any forward-invariant set containing a relative neighbourhood of the target. Thus, when trajectories are integrated to certify convergence along the way, the value of the capture region lies in how much earlier it is entered than a coarser set. To measure this, we use 40 games for each n=3,…,6n = 3, \ldots, 6, with 1000 initial states per game, and integrate to time 400 using the fourth-order Runge–Kutta method with step size 0.05. For trajectories that enter the target’s invariant box during this interval, we record the first entry time into each of the following four sets, checking membership every 0.1 time units: the capture region with zero shifts, the union of the capture regions for the 16 shift choices above, the invariant box, and the rectangle {pt>θr, qu>θc}\{p_t > \theta_r,\ q_u > \theta_c\}, where θc=max⁡kmk/(ak+mk)\theta_c = \max_k m_k/(a_k + m_k), mk=max⁡lcklm_k = \max_l c_{kl}, and θr\theta_r is defined analogously. Within this rectangle, the target action is a strict best response for each player, regardless of the opponent’s mixture.

As Table 2 shows, for each of n=4,5,6n = 4, 5, 6, the median entry time into the unshifted capture region is approximately 70% of the median box-entry time. For the union over the 16 shift choices, it is approximately 40%. Entry times into the rectangle are close to those into the box. Although the fraction of initial states already in the capture region decreases rapidly with the number of actions, its advantage in certifying convergence earlier along trajectories persists to a similar degree as the number of actions increases. To turn certification based on numerically integrated trajectories into a rigorous proof, integration with certified error bounds is required.

nnTrajectoriesBoxRectangleCapture regionShiftedBoxRectangleCapture regionShifted
33068919.6%16.1%51.6%62.5%6.16.90.00.0
4246181.6%0.8%9.5%18.2%17.117.512.16.0
5211010.3%0.1%1.0%4.2%30.629.221.411.5
6227430.2%0.0%0.5%2.6%49.046.034.819.8

Table 2. First entry times into each set for trajectories that entered the target’s invariant box by time 400. “Rectangle” denotes the set defined by the target-probability bounds above; “Shifted” denotes the union of the capture regions for 16 choices of shifts.

Limitations

  • The certificate gives a sufficient condition. The fraction of the basin covered by the capture region decreases rapidly with the number of actions (§ 7).

  • As the example in § 3 shows, convergence to the target is not global in general.

  • Exact membership decisions are limited to rational data and base points with algebraic exponentials. § 5 counts arithmetic operations; it does not give a polynomial upper bound on bit complexity.

  • The time bound (Theorem 4.2) applies when the selected sets include all nontarget actions.

  • In discrete time, we treat exponential-weights learning with exact payoff observations (Appendix § 10). The noisy case is discussed only in Remark A.2; learning in which players observe only the payoff of their own sampled action is not treated.

  • The size of the set of initial states converging to mixed equilibria is not addressed.

Discrete-time exponential-weights learning

This appendix shows that the certificate extends to discrete-time exponential-weights learning (Hedge [3]) under explicit step-size conditions, without taking a continuous-time limit. For the continuous-time limit yielding replicator dynamics, see [5]. Here, n,mn,m denote iteration indices. The noisy case is discussed in Remark A.2.

Fix a step size ϵ>0\epsilon> 0 and consider the simultaneous updates

pi(n+1)=pi(n)eϵ(Aq(n))i∑i′pi′(n)eϵ(Aq(n))i′,qj(n+1)=qj(n)eϵ(B⊤p(n))j∑j′qj′(n)eϵ(B⊤p(n))j′.p_i(n+1)=\frac{p_i(n)e^{\epsilon(Aq(n))_i}}{\sum_{i'}p_{i'}(n)e^{\epsilon(Aq(n))_{i'}}},\qquad q_j(n+1)=\frac{q_j(n)e^{\epsilon(B^\top p(n))_j}}{\sum_{j'}q_{j'}(n)e^{\epsilon(B^\top p(n))_{j'}}}.

Fix an admissible pair of action sets, shifts, and finite base points X0,Y0X_0,Y_0 as in § 2, and denote the coordinate and certificate values at iteration nn by X(n),Y(n),E(n)X(n),Y(n),E(n). Since F,GF,G are minima of finitely many branches with bounded derivatives, they are bounded and globally Lipschitz. Let M‾\overline{M} be a common upper bound on ∣F∣,∣G∣|F|,|G|, and let LL be a common Lipschitz constant.

Proposition A.1 (Convergence under exponential-weights learning). Suppose that E(0)=e0>0E(0)=e_0>0, and set

y∗=min⁡{y:Λ(y)≥e0/2},x∗=min⁡{x:Γ(x)≥e0/2},δ=min⁡{F(y∗),G(x∗)}>0,y_*=\min\{y:\Lambda(y)\ge e_0/2\},\qquad x_*=\min\{x:\Gamma(x)\ge e_0/2\},\qquad\delta=\min\{F(y_*),G(x_*)\}>0,
d0=max⁡{X0−X(0),Y0−Y(0),0}.d_0=\max\{X_0-X(0),Y_0-Y(0),0\}.

If the step size satisfies

ϵM‾≤min⁡{x∗−X0,y∗−Y0},LM‾2ϵ(d0δ+ϵ)≤e02,\epsilon\overline{M}\leq\min\{x_* -X_0,y_* -Y_0\},\qquad L\overline{M}^{2}\epsilon\left(\frac{d_0}{\delta}+\epsilon\right)\leq\frac{e_0}{2},

then E(n)≥e0/2E(n)\geq e_0/2 for every nn, and pt(n)→1p_t(n)\to1, qu(n)→1q_u(n)\to1.

Proof. The update rule gives the exact log-ratio increment ξk(n+1)−ξk(n)=ϵ((Aq(n))t−(Aq(n))k)\xi_k(n+1)-\xi_k(n)=\epsilon\left((Aq(n))_t-(Aq(n))_k\right). The right-hand side is ϵ\epsilon times the fraction in (2) and, as in the proof of Theorem 2.2, is at least ϵF(Y(n))\epsilon F(Y(n)). The same argument for the column player gives

X(n+1)≥X(n)+ϵF(Y(n)),Y(n+1)≥Y(n)+ϵG(X(n)).(10)X(n+1)\geq X(n)+\epsilon F(Y(n)),\qquad Y(n+1)\geq Y(n)+\epsilon G(X(n)). \tag*{(10)}

Since Γ,Λ\Gamma,\Lambda are nondecreasing, E(n+1)≥Γ(X(n)+ϵF(Y(n)))+Λ(Y(n)+ϵG(X(n)))E(n+1)\geq\Gamma(X(n)+\epsilon F(Y(n)))+\Lambda(Y(n)+\epsilon G(X(n))). Suppose that E(m)≥e0/2E(m)\geq e_0/2 for m≤nm\leq n. At iteration mm, there are three cases.

(i) X(m)≥X0X(m)\geq X_0 and Y(m)≥Y0Y(m)\geq Y_0. Since F(Y(m))≥0F(Y(m))\geq0, G(X(m))≥0G(X(m))\geq0, (10) implies that neither coordinate decreases, and E(m+1)≥E(m)E(m+1)\geq E(m). Once this case is reached, it persists.

(ii) X(m)<X0X(m)<X_0. Since Γ(X(m))≤0\Gamma(X(m))\leq0, we have Λ(Y(m))≥e0/2\Lambda(Y(m))\geq e_0/2, and hence Y(m)≥y∗Y(m)\geq y_* and F(Y(m))≥δF(Y(m))\geq\delta. The Lipschitz continuity of ∣G∣|G| and ∣F∣|F| gives

Γ(X(m)+ϵF)−Γ(X(m))≥ϵF∣G∣−12Lϵ2F2,Λ(Y(m)+ϵG)−Λ(Y(m))≥−ϵ∣G∣F−12Lϵ2G2,\Gamma(X(m)+\epsilon F)-\Gamma(X(m))\geq\epsilon F|G|-\frac{1}{2}L\epsilon^2F^2,\qquad\Lambda(Y(m)+\epsilon G)-\Lambda(Y(m))\geq-\epsilon|G|F-\frac{1}{2}L\epsilon^2G^2,

where F=F(Y(m))F=F(Y(m)), G=G(X(m))G=G(X(m)). The second inequality is for G<0G<0; if G≥0G\geq0, its left-hand side is nonnegative. Thus E(m+1)≥E(m)−LM‾2ϵ2E(m+1)\geq E(m)-L\overline{M}^{2}\epsilon^2. Also, X(m+1)≥X(m)+ϵδX(m+1)\geq X(m)+\epsilon\delta, and the first step-size condition gives Y(m+1)≥y∗−ϵM‾≥Y0Y(m+1)\geq y_*-\epsilon\overline{M}\geq Y_0. Thus the next iteration is in case (i) or (ii).

(iii) Y(m)<Y0Y(m)<Y_0. Interchanging the players gives the same argument as in (ii), and the next iteration is in case (i) or (iii).

Cases (ii) and (iii) cannot occur simultaneously, since that would imply E(m)≤0E(m)\leq0, so the three cases are exhaustive. Case (i) persists once reached; case (ii) cannot be followed by case (iii), nor case (iii) by case (ii). Thus iterations outside case (i) form an initial consecutive block, all of type (ii) or all of type (iii). In case (ii), XX increases by at least ϵδ\epsilon\delta at each iteration, so the number of such iterations is at most d0/(ϵδ)+1d_0/(\epsilon\delta)+1; the same holds in case (iii). The total decrease in EE is therefore at most LM‾2ϵ(d0/δ+ϵ)≤e0/2L\overline{M}^{2}\epsilon(d_0/\delta+\epsilon)\leq e_0/2, giving E(n+1)≥e0/2E(n+1)\geq e_0/2. Induction shows that E(n)≥e0/2E(n)\geq e_0/2 for every nn, and case (i) is reached after finitely many iterations.

After case (i) is reached, neither coordinate decreases, and at least one of the integrals is at least e0/4e_0/4. For example, if Λ(Y(m1))≥e0/4\Lambda(Y(m_1))\geq e_0/4, then F(Y(m))≥F(Y(m1))>0F(Y(m))\geq F(Y(m_1))>0 thereafter, so X(m)→∞X(m)\to\infty. Eventually G(X(m))≥G(+∞)/2>0G(X(m))\geq G(+\infty)/2>0, implying Y(m)→∞Y(m)\to\infty as well. The probabilities of dangerous actions decay geometrically. The remaining actions are eliminated by the same induction as in the proof of Theorem 2.2, using the exact log-ratio increment identity. □

The step-size conditions are always satisfied as ϵ→0\epsilon\to0. Thus exponential-weights learning converges to the target from every point in the capture region when the step size is sufficiently small. The conditions can be imposed uniformly on compact subsets of SS. Indeed, continuity of EE gives a positive lower bound on e0e_0 there; x∗,y∗x_*,y_* are nondecreasing in e0e_0, and F,GF,G are nondecreasing, so x∗−X0x_*-X_0, y∗−Y0y_*-Y_0, δ\delta have positive lower bounds, while d0d_0 is bounded. For the initial state in the example of § 3 (e0≈1.18e_0\approx1.18), the proposition’s conditions require approximately ϵ≤0.06\epsilon\leq0.06. In numerical calculations, no decrease in EE was observed for ϵ≤1/2\epsilon\leq1/2; for ϵ=1,2\epsilon=1,2, the decreases were only about 0.08,0.270.08, 0.27, respectively.

Remark A.2 (The noisy case). Suppose that the observation noise has conditional mean zero given the two players’ shared history before the update, and that the absolute noise difference between the target and each competing action is uniformly bounded by a constant c>0c > 0. When the selected sets include all nontarget actions, the same argument extends to the stochastic setting. One example is when each player updates using the payoff vector against the opponent’s actually sampled action. Fix a sufficiently small r>0r > 0, and consider the event that, over finitely many iterations, the absolute log-ratio fluctuations due to accumulated noise remain at most rr. Subtract the cumulative noise contribution from each shifted log ratio, subtract a further rr, and take the minimum for each player. The resulting coordinates lie below the actual X,YX,Y and satisfy (10) on this event. The probability of the complementary event is bounded by the Azuma–Hoeffding inequality. After entry into a box near the target, each log ratio is a random walk with positive drift; an exponential supermartingale and Ville’s maximal inequality bound the probability of leaving the box. Consequently, for a fixed initial state satisfying E(0)>0E(0) > 0 and a sufficiently small step size ϵ\epsilon, the probability of failing to converge to the target is at most Cexp⁡(−c′/ϵ)C\exp(-c'/\epsilon). The constants C,c′>0C,c' > 0 depend on the game, the choice of capture region, the initial state, and cc. In 4000 numerical runs at each step size, using the learning rule in the example above and the initial state in § 3, the fraction reaching a neighbourhood of the target by time ϵn=60\epsilon n = 60 was 94.5% for ϵ=1\epsilon= 1, 98.3% for ϵ=0.5\epsilon= 0.5, and 99.9% for ϵ=0.2\epsilon= 0.2; every run reached it for ϵ≤0.1\epsilon\le0.1.

References

  1. [1]S. B. S. D. Castro. Learning by replicator and best-response: the importance of being indifferent. Journal of Evolutionary Economics, 28(4):985–999, 2018. doi:10.1007/s00191-017-0547-z. Author version: arXiv:1602.00906v6.DOI
  2. [2]P. Dal Bó and E. R. Pujals. The evolutionary robustness of forgiveness and cooperation. arXiv:1205.0958v3, 2020.
  3. [3]Y. Freund and R. E. Schapire. A decision-theoretic generalization of on-line learning and an application to boosting. Journal of Computer and System Sciences, 55(1):119–139, 1997. doi:10.1006/jcss.1997.1504.DOI
  4. [4]M. W. Hirsch and H. L. Smith. Monotone dynamical systems. In Handbook of Differential Equations: Ordinary Differential Equations, volume 2, chapter 4, pages 239–357. Elsevier, 2006. doi:10.1016/S1874-5725(05)80006-9. Author version dated November 22, 2004: https://escholarship.org/uc/item/3nz137nw.
  5. [5]P. Mertikopoulos and W. H. Sandholm. Learning in games via reinforcement and regularization. Mathematics of Operations Research, 41(4):1297–1324, 2016. doi:10.1287/moor.2016.0778.DOI
  6. [6]D. Monderer and L. S. Shapley. Potential games. Games and Economic Behavior, 14(1):124–143, 1996. doi:10.1006/game.1996.0044.DOI
  7. [7]I. Panageas and G. Piliouras. Average case performance of replicator dynamics in potential games via computing regions of attraction. In Proceedings of the 2016 ACM Conference on Economics and Computation, pages 703–720, 2016. doi:10.1145/2940716.2940784. Full author version: arXiv:1403.3885v6.DOI
  8. [8]B. Zhang and J. Hofbauer. Equilibrium selection via replicator dynamics in 2 × 2 coordination games. International Journal of Game Theory, 44(2):433–448, 2015. doi:10.1007/s00182-014-0437-7.DOI

Paper details

vlnc:W_vehqwjhr
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 4

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents