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 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 , 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.
A certificate with compensation. For any finite bimatrix game and any strict pure target equilibrium, we construct a payoff-based certificate . The set where , 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.
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 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 to give a sufficient condition for an initial state to lie in the basin of the target equilibrium (Theorem 2.2).
Let and , with . Write and define analogously. The domain of initial states is , where interiors are taken relative to the affine hulls. Throughout, the measure of initial states is the usual relative Lebesgue measure on . For real payoff matrices , consider
Time is denoted by . The flow exists at every finite positive and negative time and preserves . Fix a strict pure Nash equilibrium and set
so that and .
Admissible action sets. Choose nonempty sets and , and write and . The actions in will be called dangerous actions. We require:
For every and , we have .
For every and , we have .
In the subgame on , there exists a finite sequence of eliminations by pure strict dominance that leaves only .
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 and are always admissible. Fix shifts and , and define
Lower envelopes of payoff differences. For , let
and define
Similarly, set
Throughout, we use the conventions and .
Lemma 2.1. The envelope has the following finite representation:
It is continuous, locally Lipschitz, and nondecreasing, and
The analogous statements hold for after interchanging the players.
Proof. The fraction in (2) is a linear-fractional function of , so its infimum is given by vertex values or by limits as unconstrained coordinates tend to infinity. The limit as an unconstrained coordinate () tends to infinity is . The other candidates are obtained by setting the unconstrained coordinates to and each bounded coordinate to either 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 , the inclusion gives monotonicity. Taking limits in the finite formula gives the stated positive limit by admissibility.
Define the sign thresholds of the envelopes by
and choose finite base points and . Such choices exist by Lemma 2.1. Define the oriented integrals
and the capture region . Smaller admissible finite base points give a larger capture region. When both thresholds 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 are bounded below by and , respectively (equation (5)). Replacing the inequalities with equalities gives the comparison system . This system is separable and preserves . The function aligns the signs in this first integral in favor of the target. Indeed, in a region where exactly one envelope is negative (for example, ), the comparison system satisfies . Thus, even if one coordinate lies below its threshold, 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, is a nonempty open forward-invariant subset of . Along its trajectories, is nondecreasing and , . In particular, has positive relative Lebesgue measure and is contained in the basin of attraction of under (1).
Proof. Taking differences of logarithmic derivatives gives
Substituting gives the fraction in (2). Since , every log ratio associated with a dangerous row action has derivative at least . Similarly, every log ratio associated with a dangerous column action has derivative at least . These derivatives are bounded by the finite payoff differences. Hence are Lipschitz functions of time. The right derivative of the minimum of finitely many functions equals the smallest derivative among the active indices. Therefore,
where denotes the lower right Dini derivative. In particular, these inequalities hold for the ordinary derivatives almost everywhere.
The functions are and nondecreasing. The base point conditions and monotonicity imply
together with the corresponding implications for . Moreover, , as their arguments tend to infinity. Along any trajectory, is locally absolutely continuous, and the chain rule gives
almost everywhere. The right-hand side can be negative only when both and are negative. In that case, both oriented integrals are negative, so . Thus, on every interval on which , we have almost everywhere. If , integration up to the first possible exit from shows that up to that time. Continuity rules out an exit in finite time. This proves forward invariance and monotonicity on .
We next show that both minimum log ratios tend to infinity. Set
These minima exist because the integrals are nonpositive below their finite base points and tend to infinity above them. If , then , so and . Similarly, whenever , we have . 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 , both and hold. Both coordinates are subsequently nondecreasing by (5). Since , at least one of the integrals is positive. For example, if , then thereafter. Hence , and eventually . The other case follows by interchanging the players. Thus, after a finite time, both coordinates grow at least linearly. The bounds and 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 , the total probability of the actions already eliminated, including the dangerous actions, is bounded by . When a row action is next eliminated because it is dominated by a remaining action , let the minimum of over the remaining columns be , and set . Then
for all sufficiently large . Since , this yields an exponential upper bound on . 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 . Finally, is continuous on the original domain. Taking sufficiently close to makes both integrals positive. Thus is nonempty and open and has positive relative measure.
Remark 2.3 (Order relative to the comparison system). By Lemma 2.1, are locally Lipschitz and nondecreasing, so the comparison system is cooperative: the growth rate of each component is nondecreasing in the other component. For the solution of the comparison system starting at , we have for all . Indeed, lower each component of the comparison vector field by , where solve the resulting system. By (5) and the monotonicity of , the right Dini derivatives of and are at least 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 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 , 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
Equivalently, the rock–paper–scissors blocks are and , where . The target is a strict pure Nash equilibrium, with unilateral payoff gaps equal to 2 for both players. Take 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 . Both envelopes therefore equal , where, writing ,
Its unique zero is . Use this minimal base point in both integrals in (4). This gives , with . 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 ; the orange shading shows the region where compensation gives ; the black curve is ; 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 . Thin lines connect the positions at the same times . Both trajectories are obtained by numerical integration.
Proposition 3.1. For the matrices in (6), the interior initial state
converges to . 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 . For each , it therefore suffices to choose the smallest payoff differences (a special case of Proposition 5.1). Thus the envelope reduces to the minimum of
After multiplication by the positive denominators, the numerators of , , and are , , and , respectively. This proves (7). At (8), the active minimizers are unique, and
To evaluate exactly, set at the branch boundary and define the primitives
Each derivative is the corresponding branch of . Since is negative below and positive above ,
Substituting , , , and gives the following exact comparison, an instance of the procedure in Proposition 5.2:
Hence , and Theorem 2.2 gives convergence to the target.
At this initial state, the row fitnesses are , and the column fitnesses are . Therefore,
In particular, for the column player, action 0 has lower fitness than every rock–paper–scissors action, and
The inequalities and , 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 where both envelopes are positive. It also lies outside the elementary rectangle in the two target-action probabilities (here ). Against any mixed strategy of the opponent, the payoff differences between the target and a rock–paper–scissors action are at least and , respectively, so this rectangle is a forward-invariant subset of the basin. The certificate predicts that , 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,
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, , the fitness of each rock–paper–scissors action is 1, whereas that of the absent target action is 0. In fact, the curve
is invariant. Along this curve, , so every trajectory on it converges to . 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 , write and . The thresholds in § 2 have the closed forms
where . 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 for and for ; the analogous statements hold for .
Let 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 and , define the following subset of , which is a box in the selected log-ratio coordinates:
Theorem 4.1. Every point in converges to , and
where is defined by replacing with . Consequently, the probability of the target basin is at least , where is interpreted as a limit. Moreover, if and , with at least one strict inequality, then (within the range , in which the box is defined).
Proof. As long as and , their derivatives are bounded below by and , 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 normalized by their sum. Writing and conditioning on gives
Independence across players gives the product. Lowering the bounds 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 and , and suppose that the initial point lies in . Write and . For every ,
For , the earliest time after which both errors remain at most is bounded above by
Proof. Invariance of the box gives and . 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 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 can be determined by a finite exact computation (Proposition 5.2).
Fix a row , abbreviate and , and set and . Write
The remaining candidates in the envelope are the constants associated with the unconstrained coordinates.
Proposition 5.1 (Prefix representation). Sort the coefficients as , breaking ties in any fixed order. Let be the corresponding prefix sums, including . Then, for every ,
This order depends on neither nor the positive weights.
Proof. Choose a minimizing subset and write . For and , respectively,
Both denominators are positive. Optimality therefore requires that contain every with and that contain no with . Removing terms with leaves the value unchanged. The remaining set is a sorted prefix, possibly empty.
For rows and dangerous actions of the opponent, preprocessing sorts each row and computes its prefix sums. This requires comparisons and arithmetic operations when ; the cases are handled directly. Reducing the unconstrained-coordinate constants to one minimum per row requires one additional pass through those entries. Evaluation at a fixed then uses the unconstrained-coordinate constants and 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 .
Proposition 5.2 (Exact sign determination). Assume that all payoff entries are rational, the weights and are positive rational numbers, and all coordinates of the initial point are positive rational numbers. Suppose further that the given admissible base points satisfy , with these exponentials specified by defining polynomials and rational isolating intervals. Then the sign of the quantity in (4), including the case , can be determined by finitely many exact real algebraic operations.
Proof. Each prefix branch or constant branch, expressed in the variable , has the form
Here implies : a prefix with positive weights must then be empty, and an unconstrained-coordinate branch is constant. The equation determining intersections of two branches is
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 for nonzero numerators. These finitely many algebraic breakpoints partition any compact positive 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 , an antiderivative with respect to is
For , an antiderivative is . Integrate and 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,
Thus all interval endpoints are positive algebraic numbers, and gives
Choose a positive integer that clears the denominators of all . Then is a positive real algebraic number, and , , and correspond to , , and , 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 have positive rational exponentials . They can therefore be used as the minimal base points. When a threshold is (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 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 -player game (, ) with multilinear payoffs , under replicator dynamics applied to each player’s mixed strategy on the product space . Fix a strict pure Nash equilibrium and nonempty sets , and write . Assume that strictly outperforms each against every pure profile in , and that iterated elimination by strictly dominating pure strategies reduces to . These conditions always hold when all alternative actions are included in the selected sets.
Define the ratio coordinates and constrained opponent polytopes by
The cooperative lower envelopes are
Each minimum can be taken over tuples of vertices. The vertices of are for and
Thus is locally Lipschitz, independent of , and nondecreasing in every other coordinate. Because is bounded by the game’s payoff differences, has a unique global solution, denoted by . Set
Theorem 6.1. The set is nonempty, open, and forward invariant in the original product of simplex interiors. Every trajectory starting in converges to .
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 . The same comparison argument as in Remark 2.3 [4 Theorem 3.2] therefore yields . Within , every coordinate of the comparison system increases, so its envelope values cannot decrease. After entry at time , every coordinate increases at a rate of at least . 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 .
As all opponent coordinates tend to infinity, the envelope limit is positive by the assumed payoff inequalities. Hence contains a sufficiently large upper orthant, and contains the points of a relative neighbourhood of the target that lie in the original positive domain. Continuous dependence and continuity of imply openness. Order preservation makes an upper set; comparison and forward invariance of then imply forward invariance of . ∎
Proposition 6.2 (Explicit multiplayer boxes). For a vector of box lower bounds , write and set
If every is positive, then . Its normalized uniform product measure is
Moreover, if the selected sets include all alternative actions, every initial point in this box satisfies .
Proof. If , opponent assigns at most probability to dangerous actions. By the union bound, the probability that at least one opponent chooses a dangerous action is at most . The payoff gap is at least outside this event and at least on it. Hence throughout the box, which is mapped into . 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 comparison coordinates does not make vertex evaluation independent of the number of actions. Entry into provides a certificate verifiable in finite time, but no finite stopping test is obtained for points outside . Numerical verification requires error control for both the comparison trajectory and .
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 , and write , . Suppose that both and are strict pure Nash equilibria. For any shifts, choosing the thresholds , as the base points gives
The set consists of the interior mixed equilibrium and the trajectories converging to it.
Proof. We have , , and , . Since is strict, , . The fraction in (2) is strictly decreasing in , so its infimum is attained at the upper endpoint , giving
Moreover, , , so the comparison inequalities become equalities: , . The functions are strictly increasing, with zeros , , and corresponds to the interior mixed equilibrium. When , , both integrals are positive and , so Theorem 2.2 implies convergence to . When , and , we have . Both are nonincreasing and, after any positive time, decrease at rates bounded away from zero, so the trajectory converges to . In the region , , we have , while increases and 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 , where . Thus, a trajectory with passes through , in finite time and enters ; a trajectory with passes through , and enters ; and a trajectory with converges to the mixed equilibrium. The remaining region 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 . Indeed, a convergent trajectory eventually enters a neighbourhood of the target, and 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 , we generate 100 bimatrix games with payoffs drawn independently and uniformly from , 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 (when a threshold is , 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 | Basin | Box | Capture region | Shifted | Unresolved |
| 2 | 92.3% | 62.6% | 92.3% | 92.3% | 0.0% |
| 3 | 83.2% | 13.1% | 47.5% | 55.4% | 8.0% |
| 4 | 68.1% | 1.7% | 7.2% | 14.0% | 15.3% |
| 5 | 55.9% | 0.1% | 0.6% | 2.7% | 28.2% |
| 6 | 56.9% | 0.0% | 0.1% | 0.7% | 30.2% |
Table 1. Mean fractions across 100 random 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 .
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 with zero shifts.
Capture region: the fraction satisfying with zero shifts.
Shifted capture region: the fraction satisfying for at least one of 16 choices of shifts for the dangerous actions. To choose the shifts, let measure how unfavorable the column action is to the row player’s target, and set , ; 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 initial states in total, none classified as satisfying converged to a different equilibrium under numerical integration. Conversely, some initial states satisfied but remained unresolved by numerical integration at the cutoff (122 for and 784 for ). These are counted in the basin column.
For , 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 (). Shifts expand this further by a factor ranging from 1.2 () to 4.4 ().
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 , one-fifth for , and one-twentieth for .
The unresolved fraction increases with the number of actions (approximately 30% for ). 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 , 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 , where , , and 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 , 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.
| Trajectories | Box | Rectangle | Capture region | Shifted | Box | Rectangle | Capture region | Shifted | |
| 3 | 30689 | 19.6% | 16.1% | 51.6% | 62.5% | 6.1 | 6.9 | 0.0 | 0.0 |
| 4 | 24618 | 1.6% | 0.8% | 9.5% | 18.2% | 17.1 | 17.5 | 12.1 | 6.0 |
| 5 | 21101 | 0.3% | 0.1% | 1.0% | 4.2% | 30.6 | 29.2 | 21.4 | 11.5 |
| 6 | 22743 | 0.2% | 0.0% | 0.5% | 2.6% | 49.0 | 46.0 | 34.8 | 19.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, denote iteration indices. The noisy case is discussed in Remark A.2.
Fix a step size and consider the simultaneous updates
Fix an admissible pair of action sets, shifts, and finite base points as in § 2, and denote the coordinate and certificate values at iteration by . Since are minima of finitely many branches with bounded derivatives, they are bounded and globally Lipschitz. Let be a common upper bound on , and let be a common Lipschitz constant.
Proposition A.1 (Convergence under exponential-weights learning). Suppose that , and set
If the step size satisfies
then for every , and , .
Proof. The update rule gives the exact log-ratio increment . The right-hand side is times the fraction in (2) and, as in the proof of Theorem 2.2, is at least . The same argument for the column player gives
Since are nondecreasing, . Suppose that for . At iteration , there are three cases.
(i) and . Since , , (10) implies that neither coordinate decreases, and . Once this case is reached, it persists.
(ii) . Since , we have , and hence and . The Lipschitz continuity of and gives
where , . The second inequality is for ; if , its left-hand side is nonnegative. Thus . Also, , and the first step-size condition gives . Thus the next iteration is in case (i) or (ii).
(iii) . 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 , 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), increases by at least at each iteration, so the number of such iterations is at most ; the same holds in case (iii). The total decrease in is therefore at most , giving . Induction shows that for every , 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 . For example, if , then thereafter, so . Eventually , implying 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 . 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 . Indeed, continuity of gives a positive lower bound on there; are nondecreasing in , and are nondecreasing, so , , have positive lower bounds, while is bounded. For the initial state in the example of § 3 (), the proposition’s conditions require approximately . In numerical calculations, no decrease in was observed for ; for , the decreases were only about , 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 . 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 , and consider the event that, over finitely many iterations, the absolute log-ratio fluctuations due to accumulated noise remain at most . Subtract the cumulative noise contribution from each shifted log ratio, subtract a further , and take the minimum for each player. The resulting coordinates lie below the actual 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 and a sufficiently small step size , the probability of failing to converge to the target is at most . The constants depend on the game, the choice of capture region, the initial state, and . 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 was 94.5% for , 98.3% for , and 99.9% for ; every run reached it for .
References
- [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]P. Dal Bó and E. R. Pujals. The evolutionary robustness of forgiveness and cooperation. arXiv:1205.0958v3, 2020.
- [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]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]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]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]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]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
