Theoretical Guarantees for the Retention of Strict Nash Equilibria by Coevolutionary Algorithms
Authors: Alistair Benford
Per Kristian Lehre
Venue: NeurIPS 2025 poster ()
Keywords: coevolution
adversarial optimisation
Nash equilibria
Primary area: theory

Abstract: Most methods for finding a Nash equilibrium rely on procedures that operate over the entire action space, making them infeasible for settings with too many actions to be searched exhaustively. Randomised search heuristics such as coevolutionary algorithms offer benefits in such settings, however they lack many of the theoretical guarantees established for exhaustive methods such as zero-regret learning. We address this by developing a method for proving necessary and sufficient conditions for a coevolutionary algorithm to be stable, in the sense that it reliably retains a Nash equilibrium following discovery. As the method provides bounds that are adapted to both application and algorithm instance, it can be used as a practical tool for parameter configuration. We additionally show how bounds on regret may be deduced from our results and undertake corresponding empirical analysis.

Theoretical Guarantees for the Retention of Strict Nash Equilibria by Coevolutionary Algorithms
Alistair Benford
Per Kristian Lehre School of Computer Science University of Birmingham p. k. wwwre@bhammmmmmmm ac. uk
School of Computer Science University of Birmingham ac. uk
a. s.
Abstract
Most methods for finding Nash equilibrium rely on procedures that operate over the entire action space, making them infeasible for settings with too many actions to be searched exhaustively. Randomised search heuristics such coevolutionary algorithms offer benefits in such settings, however they lack many of the theoretical guarantees established for exhaustive methods such as zero-regret learning. We address this by developing a method for proving necessary and sufficient conditions for coevolutionary algorithm be stable, in the sense that it reliably retains Nash equilibrium following discovery. As the method provides bounds that are adapted both application and algorithm instance, can be used as a practical tool for parameter configuration. We additionally show how bounds on regret may be deduced from our results and undertake corresponding empirical analysis.
Introduction
As many challenging problems characterised by the presence of competition between agents, the demand for efficient techniques for the determination of Nash equilibria has brought about a range of powerful machine learning techniques, including Q-Learning [10 20 33 Fictitious Self-
Play 77 (25), Counterfactual Regret Minimisation (8 9 64], and gradient-based approaches [4] [19
provide theoretical guarantees of convergence to Nash equilibrium in the zero-sum adversarial multi-armed bandit setting, however such algorithms rely on procedures operating over the entire strategy space (such as storing vector over all available actions). In many settings, such as those characterised by sequence of binary decisions, a combinatorial explosion in the number of actions quickly make any exhaustive approach infeasible. These many-action settings can only be addressed using procedures that exploit underlying topological features of the strategic representation and corresponding payoff landscape in order to guide a search towards Nash equilibrium. Coevolutionary algorithms (CoEAs), a form of evolutionary algorithms (EAs) employing two or more competing populations, are one such approach, and recent theoretical work proves that CoEAs can efficiently discover the Nash equilibrium of range of two-player many-action games defined over bitstrings [ 30 31
57 63
Analysis of regret for algorithms such as EXP3 3 and FTRL
The successful application of adversarial and self-play techniques is uniquely challenging due to the potential for pathologies such as cycling or instability, and such pathologies have been observed in range of such methods including GANs [53, 62), AlphaStar [60], SGA [4], as well as CoEAs in general [8] In the case of CoEAs, one major open problem is the question of when to terminate and extract output from the current populations. This is an important consideration even for standard evolutionary algorithms non-adversarial settings [46). and made even more challenging for CoEAs as the absence of unary fitness function makes the identification of best-so-far strategies both expensive and subjective. Thus, to maintain confidence in the output of a CoEA, one should ensure that the algorithm is designed and configured in such way that any discovered Nash equilibrium will
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

not be forgotten following discovery. Algorithms with this property are more amenable to maintain progress towards the Nash equilibrium even before discovery (as per conditions of the level-based theorem for CoEAs [40],, making its analysis even more essential.
The question of how CoEAs reach Nash equilibrium is addressed theoretically by runtime analysis, which is the subject of all existing theory for CoEAs. For an algorithm to have low runtime, it is often necessary for the strength of its mutation operator (i.e., its mutation rate) to be sufficiently low relative to selective pressure (although this alone is typically not sufficient) 38 40 50 However, there is gap in our understanding of algorithm behaviour following the time after which a Nash equilibrium first enters the populations. This paper presents theoretical basis for the determination of conditions for a CoEA to be 'stable' in the sense that it overwhelmingly likely to retain a Nash equilibrium following discovery. In particular, we quantify the link between the stability of a CoEA and the mutation rate, and this link will closely depend on the selection process being used (similar to runtime results that also impose necessary conditions on mutation rate). We will later see (Theorem 3.5) that a given algorithm will never be stable if mutation too strong. As a very low mutation rate can inhibit exploration, knowledge about how strong mutation can be while still ensuring stability is extremely valuable for practitioners. Our contributions are thus as follows.
1. An easily applicable theoretical technique (Lemmas 3.3 and 3.4) for ascertaining upper and lower bounds on the threshold between stability and instability for population-bus based CoEAs with unary variation.
2. Derivation of stability bounds using this technique for large classes of CoEAs (Theorems 3.5 and (.6) as well as two specific CoEAs (Theorems 3.7 and 3.8 We also confirm the predictions made by these derived bounds empirically.
3. A proof that stability guarantees can be combined with runtime analysis to additionally quantify the regret of CoEAs, akin to the regret guarantees established for learning algorithms on small action spaces.
1.1 Related work
CoEAs have been used in numerous applications to adversarial optimisation and multi-agent learning.
including generative adversarial networks [14), cybersecurity and defence [21] 26 29 59 65], and detecting tax evasion [27]. Coevolution has extensive use for the training of game- game-playing agents in studies on backgammon [54] poker 44), Atari games [30], and StarCraft II [ 60], to name just
few. Other applications of coevolution introduce competition to improve learning by coevolving a population of environments alongside agents 12 61]. For a general overview of fundamentals of CoEAs, their use cases, and challenges arising in their application, we refer the reader to (55).
CoEAs can be viewed as an extension of EAs, for which there has been a large amount of theoretical analysis (see survey [17) for example). Despite demand (see (55)) similar analysis for CoEAs is more limited. Nonetheless, a rigorous theory for competitive CoEAs was initiated by Lehre [39 40 who provided guarantees for the expected time for an algorithm called PDCoEA (which we consider later in Section 3.2) to discover the Nash equilibrium of bilinear game (which we consider in our empirical analysis in Section 4. Subsequent theoretical work analyses the impact of algorithm design on runtime 30 31 32 and the use of CoEAs for the discovery of optimal play for new games and problem classes, including symmetric zero-sum games [. combinatorial games 6). binary
test-based problems 42 43 and potential games (8
Some theoretical results for EAs establish an 'error threshold' expressed as a function of selective pressure. Configuring mutation rate above an error threshold makes it difficult to sustain a positive proportion of individuals inside a region of the search space containing the target. In previous analysis this is significant because it can lead to exponential runtime, however it is directly related to stability results here which establish thresholds on mutation rate, also expressed in terms of selection, above which a CoEA struggles to maintain populations on the solution concept. Error thresholds are standard analysis of EAs (see, for example, [38 50), and have also been proven to exist for CoEAs [40 The role that error thresholds play in coevolution has also been analysed empirically in [29 where was observed that the mutatation rate of self self-adaptive version of PDCoFA converged to value just below the error threshold without previous knowledge.

---

1.2 Notation
probability distribution over finite set S is a function p: S |0, 1] which satisfies Exes p(s) - and P(S) will be used denote the set of probability distributions over S. An S-valued random p). if P(( = s) = p(s) holds for every s E S. We use x= = argmaxyes (v) as a shorthand for saying that sampled uniformly from the set {y E S f(y) = mäxzes f'))). Given a set X' and natural number À E N. we will use X to denote the set of tuples of length À over X. Given a tuple P := (P(()...... P(A)) E X'',, we often multiset (that is a subset of X)) of cardinality A, and hence write statements such as x E P to mean x E (P(1)= : E [A]]. or use |P n A| to represent the quantity { E [A] : P(t) E A)|.
variable is distributed according to (written
regard P also
2 Setting
The setting we consider is conventional two-player game scenario, however it readily applies not only to game-playing applications, but also to real-world adversarial optimisation, scenario optimisation, multi-agent systems, and settings with competition added to enhance learning.
Definition 2.1. A problem (or game) is tuple (X fI, f2, A x B) where f1 X x y - R. fe: : X x + F. A S X, and B _ y. ft is called the payoff function for player i and A x B is called the solution concept. A problem class is simply collection of problems.
Let G represent the class of all problems. As Definition 2.1 imposes no conditions or restrictions on the sets and B, there is no assurance that a problem (in the strict sense of the definition) has an associated solution concept that is of meaningful or practical. In reality, we will restrict attention to classes of problems which have solution concepts that fit a common understanding of what means to be strategically optimal. In particular, we will use STRICTNASHI to denote the class of problems for which fi (ar, y) > Si (x', y) and f2(2, y) > f2(x, holds for all x E A, x' & A, y E B. y & B, and focus on this problem class as particular case of interest. Nonetheless, the high degree of generality in Definition 2.1 allows for results that potentially apply to alternative formulations of optimality. For example, some of our negative results general enough to apply to any solution concept that is a singleton set. Therefore, let SINGLETONSOLUTER
be the class of problems with |A| = [B| 1. It is also common to prove results for classes of problems with additional structure imposed on the payoff function or strategy spaces. Let ZEROSUM be the class of problems for which holds for all X and y E V. Given N. let BITSTRING, be the class
fi v) + f2(2, 3) of problems with X' = y = 13".
We consider CoEAs consisting of two populations P C X and Q C y (informally labelled the predator and prey populations) constructed using two fundamental randomised procedures: selection and mutation. Selection uses evaluations of the payoff function to determine which individuals are best suited to be parents for the next generation. Mutation randomly varies the genotype of those selected parents to produce offspring. Here we formalise these two components and characterise some key properties before stating the algorithmic model to which our results apply.
Definition 2.2. Given a search domain X, a mutation operator (or unary variation operator) over X is a function Mx X - P(xX) Given search domains X and y and subset R C [0. 11. we use MUTATION(X.) R) to denote the set of pairs (Mx.My) of mutation operators over X and y that satisfy the following statisticity condition.
Mx(x)(x)- My(v)()) E R for all (z.1) E X2.
(1)
In our results, the set R will characterise the strength of the mutation operators being discussed. For example, if
) E MUTATION(X', y²; (go. 1]), then (1) ensures the probability that mutation has no effect on a predator-prey pair greater than Toi in this context, go represents bound on the strength of the mutation operators being used. For blackbox optimisation problems over bitstrings, it standard use mutation operators which are unbiased. in the sense that the effect of mutation is preserved under permutations of the bit positions and applications of binary masks (see [44] for precise definition). Going further, with no a priori information about how the payoff landscape differs between players, it is natural when X = y to choose Mxx = .My. Thus we will often consider the following subclass of MUTATION (0, 13", [0, 13"; ; R) (where the final assumption in Definition 2.3 simply ensures the probability of mutating to the most distant searchpoint is small, as is standard).
3

---

Definition 2.3. Given E N and R C [0. we use UNBIASED(n: R) to denote the set of (Mx,My) E MUTATION((O, 1)", {0. 13"h R) for which Mx unbiased, My Mx, and (1²0")(1") & 1/nn.
Given populations (P,Q) E X² Jrx, the role of a selection operator to stochastically select individuals (here, one pair at time) from the populations that are suitable parents for the following generation. The defining property
selection operator is that its output must be an exact copy of a pair from the input populations [52] defined formally as follows.
Definition 2.4. A selection operator is a function Sx X x - - x Y) (defined for each N) such that for every (P, Q) E X VA,, (x. Q)), then P(x E PAA E Q) =.
Selection operators use the payoff functions fi and f2 (as well as the search domains X' and V) to make decisions about what select. Thus when say 'selection operator', we typically mean 'a description a selection operator for every possible problem instance G E g'. Algorithm Sratthmm@esoe describes model for non-elitist population-based CoEAs with unary variation. We note that this model is a coevolutionary analogue to the Population Selection- Variation Algorithm (PVSA) for standard and additionally fits the population-bast coevolutionary process model studied in (40)
EAs 38 52].
Algorithm 1 Population-basee CoEA with unary variation
Require: Population size
Require: Initial populations Po X' and Qo y
Require: Selection operator Sx
Require: Mutation operators Mx & P()) and My y P())
1: for t E N until termination criterion met do
2: for j E [X] do
4: Sample (xt, 1) (Pr.
3:
Sample 1j+ Mx(x)
5: Sample Q++1 (f) My(y)
6: end for
7: end for
Typically, search domains and mutation operators are application-speeific and population size is considered to be algorithmic parameter. Thus, will generally consider CoEAs to be defined solely by their selection operator Sx. In light of this, we will use As(Mx, My. A) to denote the population-based CoEA with unary variation corresponding selection operator Sx (where we drop the implicit X for brevity), mutation operators Mx and My, and population size X.
Stability analysis
Roughly, we will say CoEA is y-stable on problem if given it is initialised with at least proportion of Po x Qu on the solution concept, with overwhelmingly high probability it will continue to maintain proportion of P, x Qi the Nash for an overwhelmingly long period of time (where 'overwhelmingly' here denotes exponential with respect to population size). This notion is formalised using the following definitions.
Definition 3.1. Given an algorithu A running on a problem with solution concept S, we define the depaarue and h-hitting times to be
(A; min (1>11:00
Q < >>a},
Th (A: = min (t 1: I: x Q0)S) > 72²}.
That is, T2 (A;G) is the first time (excluding t = 0) for which the populations of A have at most than y proportion pairs the solution concept for G, and T (A; G) is the first time (excluding t = 0) for which the algorithm's 's populations have at least a proportion of pairs on the solution concept for G.
Definition 3.2. A population-based CoEA A with population size X is ststtal on a problem G with solution concept S if there exists 8 > 0 which does not depend on X such that, for all populations
P E X and Q E y satisfying [P x Q 2 7x2, it holds that
P (A: G) < E (Po. Qo) (P. <E -8
<E
(2)

---

Definition 3.2 is the strongest that can reasonably be adopted, in the sense if e were replaced by any function h N E that grows faster than exponential with respect to X, then it would be impossible for any non-trivial population-based CoFA with unary variation to satisfy the definition. This observation is proven formally in Appendix A
3.1 General tools
We now present the main tools used to derive stability bounds for population-bas CoEAs. The first of these is lemma that produces bound (0()) on the strength of the mutation operators that can be used while still ensuring y-stability. The resulting bound is dependent on the description of the algorithm's s selection operator Sx, more precisely it is dependent
two functions a [0, 1J2 + [0, 1] and :: [0, 1]2 - [0, 1] that can be straightforwardly derived from a description of the selection operator. Semantically, a(a, b) represents lower bound the probablity that selected predator lies on the Nash equilibrium, given an a-proportion of predators and I-proportion of preys in the present populations lie on the Nash (and similar for ((a, b) and selected prey). Later, will see that the application- specific expressions for a and / are typically polynomials and that deriving them is matter of routine computation. Obtaining expressions for and / is one of only two application-speeific steps required to apply this tool. The other is to compute the maximisation set out in (3): however, as a and are typically polynomials (and also often exhibit symmetries that simplify analysis) this is most often case of applying elementary calculus and otherwise relying on numerical solvers. The proof of Lemma B.3 is provided alongside more general version of the tool in Appendix [B.3]
y Lemma 3.3. Let Sx be a selection operator, let G == (X, y, f1. f2, A x B), and let E [o. 1].
Suppose there exist increasing functions a [0, 1|2 [0, and B [0, 112 + [0, 1] such that, for all
A LET N and populations P X² and Q E y',
[PO QQBB
[ A
QQB]
P(x E A)
and P(y > 3
A holds for (z. v) (x, Then, provided (M) E MUTATION(X,). (X,): (go(7), 11) where
A
7 aEhxa] ala, 1/a) 7/a)
go(?) = sup
(3)
ala,
A) is 7-stable on G.
We note that the assumptions in Lemma 3.3 imply condition (G2b) in the level-based theorem Theorem 3] used to derive bounds on the expected runtime of CoEAs. For details, see Appendix B33
40
As well as characterising regimes where stability is guaranteed, we must also assess when stability is not guaranteed (or more drastically, when instability guaranteed). This is possible using the second of our main tools, Lemma 3.4) Its first conclusion (A1) is a direct analogue to Lemma 3.3 and the outstanding ieliicatton-spcciffe steps are also the same (except that a and must be obtained as upper bounds on selection probabilities instead of lower). However, Lemma 3.4 is extended in two further ways. First, is stated with respect to bitstring problems and unbiased mutation operators. As the purpose of the tool is to identify unstable cireumstances, this is important that such circumstances are natural applications rather than unrealistic instances without wider significance, and a restriction to unbiased mutation over bitstrings is one well studied way to ensure this. Nonetheless, in order to have negative results with utility beyond bitstring games, we state a more general version of the result applicable to arbitrary domains in Appendix and use it to derive Lemma 3.4 Second, the additional conclusion A2 identifies circumstances where an algorithm is unstable in a very strong and critical sense in that the proportion of its populations the Nash drops to almost zero in small amount of time. The proof of Lemma (3.4 is found alongside its generatisation in Appendix B.4
Lemma 3.4. Let q, E [0, 1] and Sx be selection operator. Let (G,, joe be a sequence of problem classes with Gn C BITSTRING, n SINGLETONSOLUTION
Suppose E R {oo} is a constant and o [0, 1|2 + [0, 1] and 3 [0, 1J2 + [0, 1] are continuous increasing functions such that, for all X, E N. problems (X² y, f1, fz, (x", (e"")")) E Gn, and populations P E X² and Q E y*,
IP [a+ IQn H
P P [a H
IQ fv"}]
= P(===")<a a
Ply = (5)
X
X
Q) 12"" [,}} X²
F((x,y) = (x' KK
holds for (z. (P, Q). Then the following results hold.
5

---

A1 Provided
7
9 sup aEtx, ala, r/a) 3(a,
(4)
there is constant no E N such that for any 2 on. G E Gn. (Mx,My) E
UNBIASED(N; ; [0, q)), the algorithm As(Mx, My. X) is not y-stable on any G In.
A2 Provided K oc, a(a, b) = B(b, a) for all a. E [0. 11, and that
ab
inf (a.b)E(0,//1)) ala, b) a(b,a))
(5)
there is a constant å > such that the following holds for all functions T ;: + R For any n 2/(8 G Gn My),My) E
and E N E with s(n) 2 on
10
UNBIASED(N; [0, q]), À satisfying
K 2
A A max
log (6T(n))((n))
(6)
8" 82y
and populations P E X2 and Q VA with Pn fx H1 12 [4")) & vad, it holds that
3
P (A:G) 2 r(n) (Po. Qo) (P. (=(n)r(n)
where A := As
My, A). In particular, choosing e and T appropriately (e.g. s(n) 6. and T(n)= = n²)) shows that A is not --stable on any G E Gn for n sufficiently large.
5n
3.2 Applications
Here we showcase the utility of the tools from [ection[3.1jpr applying them to derive stability bounds for range of algorithms and problem classes. First, we show that it is immediate from Lemma 3.4 that stabbiilyty never possible MM) E UNBIASED(m, (n; [0,7]] 7])
Theorem 3.5. Let Sx be any selection operator: I E [0, 1] and q < %, then the conclusion A1
holds for Gn = BITSTRING, n SINGLETONSOLUTION
Proof. The prerequisites of Lemma 3.4 are satisfied with ar b) = ((a,b) b) = and K = oc.
Improvements over this universal bound arise from the introduction an additional weak assumption on the structure of the selection operator. A feature common many selection operators is to first sample several candidates from each population uniformly at random (with replacement), and then make informed selection from those candidates. We will say that ko-andidate selection operator one that makes the predator selection from predator candidates and the prey selection from l prey candidates. This informal description is sufficient for the sake of the material in this paper; however, for the sake of rigour a formal description may be found in Appendix B.5
Theorem 3.6. Let Sx be a k-candidate selection operator.
B1 Ifr E [0.1] and q < 7/(1 (1 (1)7))) then the conclusion of A1 holds for Gn. BITSTRING, n SINGLETONSOLUTION
B2 7 E [0, and < - then the conclusion of A2 holds for Gn BITSTRING,, n SINGLETONSOL.UTION
Proof. k-candidate selection operators satisfy the prerequisites of Lemma 3.4 with a(a,
a)*, b(a,b) = - bi*t and K = 222:; see Appendix B.5 for further details.
Theorems 3.5 and 3.6 characterise regimes where instability is inevitable (and hence should be avoided when parameterising algorithms) for highly general classes of selection operators. By considering specific selection operators, it is also possible to apply our main tools to derive not only stronger bounds on instability, but also practical guidelines of how to parameterise mutation to assure stability. We carry out these derivations for two specific population baased CoEAs: Pairwise

---

Dominance CoEA (PDCoEA) and Tournament Selection CoEA (TSCoEA The selection operators defining each algorithm are given below.
Algorithm 2 Selection operator for PDCoEA
Algorithm Selection operator for TSCoEA
1: Sample 21, 22 Unif( P)
1: Sample I 2.......
Un)((P;)
2: Sample y1, 1/2 ~ Unif(Q)
2: Sample vi...., V1 Uni
3: if Ji (I1, 311) >
(122
and
3: Set = argmax r[[4] min fi (Fr, V.))
[2(21,, 31) 2 f2(21, 82)
then
4: Sample yl..... V/- Uni((Q:)
4: Set (4, v) (21;
5: Sample 11 z2 ~ Un)
5: else
6: Set j argmax min f2(22), Ur)
6: Set (z. y) (z2. y/2
7: Set (zr v) ( 1/)
7:
end if
In each selection, PDCoEA decides between two sampled pairs (x1, yn) using pairwise dominance relation. PDCoEA has been studied empirically on game theoretic attacker-defender cyber security interactions 229 41). and theoretically on pseudoboolean payoff functions [40] 43). In Theorem 3.7 we apply Lemma 3.3 to derive conditions for the assured stability of PDCoEA for three increas- ingly specialised problem classes: STRICTNASH, STRICTNASH A
and STRICTNASH SINGLETONSOLUUTION n ZEROSUM. Going further, in the case of STRICTNASH SINGLETON we show that the proven bound is best possible using both conclusions of Lemma 3.4 Illustrations of the trade-off between mutation strength and y-stability for the latter two classes are given in Figure and proof of the theorem can be found in Appendix [.6
Theorem 3.7. Let Sx be the selection operator for PDCoEA (see Algorithm 2 and lety E (0, 1].
C1 Let 90(7)
(3v 377)- If G STRICTNASH and (Mx;My)
(/; 1)) then (MMMx,My, A) is y-sabble on G. C2 Let 90())) = 13/7-22
C2.1 If G E STRICTNASH N SINGLETONSOLUTION and (Mx,My) E MUTATION(X, J'; (go(1), 11) then As(Mx, My, A) is y-stable on G. STRICTNASH N
C2.2 There is sequence of problems (G with Gn SINGLETONSOLLUTION n BITSTRING, for every n E N such that if (Mx, E
UNRIASED(M; [0, (o(r))), then As(Mx, My, X) is not y-stable on Ga for suffi- ciently large.
C2.3 If E (0. 9/16/16 and E [0. qu)))), then the conclusion of A2 holds for Gn {Gn} (where (G the problem sequence arising in C2.2.
100
C3 Let ag (a, = a(a + (1 a3(b b² (1 -1--b)) -))o0 + })) and
?
20(7)= = sup
sup aETT. =0 (1 7/0) an - (1/a,
If G E STRICTNASH O SINGLETONSOLUTION n ZEROSUM and (Mx,My) e MUTATION(X, (10()) 1]) then As(Mx, My, A) 7-stable on G.
TSCoEA 31 is archetypical of a broad class of CoEAs which perform a k-tournament selection using some chosen metric calculated based payoffs against a number of opponents (see 22 35 58
for examples of similar such algorithms). While any desired metric may be chosen (such as best average payoff or membership of the mixed Nash equilibrium of the implied restricted game), we focus on best worst-case (or max-min) payoff for two good reasons. First, it can be computed in time (kk). whereas potential superior alternatives requiring determination of mixed Nash cquilibrium are PPAD-complete [5]. Second, the pure Nash equilibrium of a two-player zero-sum game corresponds to its max- min strategies (see [51 Proposition 22.21), making it apt for the class ZEROSUM. Accordingly, a restriction to ZeROSUm is made in the following stability bounds for TSCoEA, which are proven in Appendix B.7 and illustrated in Figure
Theorem 3.8. Let Sx be the selection operator for TSCoEA (see Algorithmm which uses parameters k, l E N, and let y E (0,
'TSCoEA appears in 31 as Archived Tournament Selection CoEA (ATS-CoEA) CoEA). As we forego the use of archive to fit the population
popula based CoEA with unary variation model, drop 'Archived' from the name.
7

---

PDCsRA
POC
Stfichlish n Singletonsokk
ScricMaaph n SingltterSoubon ZoroSum
C2.1
4.4
3.6-
01
5:2
5.
2.5
TSCOEA 12 on
TSCOEA (R- 1-10)
2.
2.5
0.3
0.8-
544
2.4
0.2
0.0 02
0.4 0.6
V- 1.0 0.0 0.2
0.8
0.1 0.6
1.8
Figure 1: Best proven stability bounds of PDCoEA and TSCoEA on various problem classes. Green regions indicate the algorithm is 7-stable on all instances of the relevant class; red regions indicate the algorithm not 7-stable all instances of the relevant class; amber regions indicate there exist some instances the relevant class on which the algorithm is not y-stable. For each region, the relevant theoretical result is indicated (e.g., BT). As Theorem 3.5 proves the region q < Y must always be red, the boundary algorithm deviates from the theoretical limit what could be hoped for in terms of stability.
shows both the improvement made by Theorem (.66oremm.66aam and also how far the
D1 Let
(o (1- 7)
7
IfG E STRICTNASHI ZEROSUM and (Mx, MUTATION(X, (go(7), 1]) then As(Mx, My, X) is 7-stable on G.
D2 Suppose additionally that = and les
1
%0(7)
sup
(7)
aE[:.]] (2 a)(2 2(1 a) 7/0) r/a)
D2.1 I E STRICTNASH ZEROSUM and (Mx. E MUTATION (go(()) 1]), then As(Mx, A) stable on G. D2.2 There is a sequence of problems (z with Gn STRICTNASH ZEROSUM BITSTRING, for every E N such that if (Mx, My) UNBIASED(T; [0, (o()))),
then AsMMx,My, X) not y-stable on Gn for n sufficiently large.
Empirical analysis of stability
In this section we present the empirical stability of PDCoEA and TSCoEA on range of zero-sum games and compare our findings to the theoretical bounds derived in Section 3.2 Three problems are considered: Bilinear (3 32 40, which emulates standard game-theorethe saddle point trade-off' between two players; PlantedBi SeddBBllieaa linear, a randomly instantiated many-d miny-dimensional generalisation of Bilinear; and MBJR_ 2024 34). a game based on that first introduced by Maiti et [47 challenging instance for pairs of no-regret learners. By making minor modifications as necessary, all games have same search domains X' y {0, 11" and have a unique strict Nash equilibrium (x" (=",""), These games were chosen because they have large strategy spaces, however the Nash equi- librium known in each case and so can be injected into the initial population a controlled rate as necessary to analyse stability. For full descriptions of the three problem instances as well details of

---

Bilinear
Planted Billnear
MBJR_2024
PDCoEA
0.-
600
024
TSCoEA
62
42
Figure 2: Heatmaps indicating the proportion of runs for which T. (A;G) > 4 x 10th for combina- tions of (7, g) E 10, 1J2. Green regions indicate that A observed as 7-stable on G for the given q; points not coloured green indicate that AA was observed to be not y-stable on G for the given q.
computational resources used carry out the runs, see Appendix Code to reproduce the experiment is available at https:///iithut com/ wsweefood/staailllie.. analysis coeas
The mutation operator M used by each algorithm is standard bitwise mutation, which flips each
bit of a searchpoint E (0, 1 independently with probability x/n for some fixed x. For range
of combinations of (7: 9) E 0, 1]2. X was chosen to ensure that (M,M) UNBIASED(n; {q) and initial populations (Po. Qu) of size À = 10t were generated with Unif([0, 1))), so that [(P Qo) n {(x .y""""" = 7X² (the individuals not initialised on the Nash equilibrium were sampled uniformly at random from {0, 1)").
and
1Q n H -1 (where
As we cannot test all possible values in Definition 3.2 we make no specific assumption about 5 but instead simply test whether Tep (A: G) is small for a large population size. The event that Thp (A; G) small was then tested for by running the algorithm for 4 x 105 evaluations of the payoff function. By repeating this process 25 times for each (7, -combinntnion, we obtain broad indication of whether A is 7-stable on G when using mutation in UNBIASED(1; {g}).
The corresponding results displayed in Figure 2 alongside our best theoretical bounds for stability on the given problems, which are all members of STRICTNASH n ZeROSUm (see middle two plots of Figure [T]. The most important aspect of each plot is the boundary between the green region indicating stability (as all corresponding runs maintained the initial proportion on Nash) and the non-green region indicating instability. In all cases, the empirical boundary sits between the two theoretical lines, and so the observed stabilities are in close agreement with our theoretical predictions. Of particular note is the fact that for each algorithm the empirical boundary varies depending on problem instance, suggesting that gaps between theoretical bounds on stability and instability exist due to variation in problem instance and not because potential improvements missing from the corresponding proofs. In this sense, some of the derived bounds may be best possible.
n
5 Regret analysis
We now turn our attention to how deeper understanding of stability of CoEAs can be used to enable regret analysis for coevolution. Let us consider zero-sum game with unique Nash equilibrium G = (X -f, (a", y v))). The regret for strategic interaction between two agents is defined with
respect to action outputs ) and (2 in X' and y generated by a learning process. The cumulative regret after time T is the total payoff improvement the players could have received, were

---

they given advanced knowledge of their opponents' actions and allowed to adopt a best (constant) response accordingly. Formally, this is
RT : max
Σ (hi m(sr).)))) DEY
max
Σ Va( S2( v.)
ZEd
Evro, (() 1(3h.)1))
max min #Ed yEy
The learning process then said to be e-Hannan consistent if the time-averaged regret converges almost surely to the interval (0,s]. That is.
P lim sup
T- T RT
& =1.
(8)
In the case where = O, the learning process is called Hannan consistent or zero-regrel (6]]]]6)] It known that the time-averaged output of zero-regret algorithm converges a pure Nash equilibrium when one exists, and ascertaining theoretical guarantees about regret has been fundamental to the development of multi-agent algorithms including Exp3 [3, CFR 664 D. and FTRL [23]. Such guarantees instill confidence in these algorithms, however they are typically only applicable when the strategy spaces X and y are small enough query every possible strategy. Here we turn our attention to regret analysis of CoEAs, which potentially apply to games with superpolynomial search spaces where polynomial identification of a pure Nash equilibrium is highly non-trivial.
Assume that at each time step, a population-bast based CoEA A outputs a pair (#t, ye) of elites selected from the current populations (Pr, Q+) according
It argmax min fxx y)
Y/ argmin max f(r,
zEP. wEQ:
yEQ. =EP;
Recall that for zero-sum games, this policy always ensures (xx, M1) (a", ,²) whenever (x*, yy) Pt x Q.. Runtime analysis (e.g.. 31 40 43) typically proves polynomial bounds on the expected time until (x", =y") first discovered, however this alone does not ensure regret guarantee. However, when combined with an added provision of stability (as given by the results of Section 3). it is straight- forward deduce e ((A)
consistency, where =(A) a function that decays exponentially in X. This is handled in the following theorem, which is proven in Appendix B.8 In the statement, the runtime condition is represented using Th (A; G) (see Definition 3.1).
Theorem 5.1. Let G E ZEROSUM n SINGLETON
and suppose for some 7 E (0, 1] and T: N + Rz0 that the following runtime bound holds for all populations P E X* and Q y
E G) (Po, Qo) (P, Q)] T()).
If A is 7-stable on G then there is a constant e such that A is T T(A)e -c ed -Hnnnan consistent.
Limitations and further directions
There several further directions and open questions related to the foundational results stability of CoEAs set out here. First, the empirical analysis of Section 4implied that the gaps between the always-stable and never-stable regions in Figure Ilikely occur due to variation in application rather lack of tightness of results. This is not yet confirmed rigorously, but could be with the construction and analysis of specific problem instances. Second, there are many important solution concepts in addition to Nash equilibrium, including dominating strategies, evolutionarily stable strategies, and max-min strategies (for non-zero-sum games), and stability analysis can be undertaken using the tools of Section 3.1 We also note that the methodology of the empirical analysis in Section is limited by its applicability only problems where the solution concept is already known. Finally, and perhaps most importantly, it is noteworthy that the proven regions where y-stability is assured D1 D2.1 do not meet the line y O, despite the fact that O-stability is clearly desirable for ensuring populations will grow on the solution concept for single individual. While 0-stability is observed for existing algorithms certain problem instances (see Figure 2). we should strive to design algorithms configurable to assure O-stability on general problem classes. As our tools provide means to prove whether this criterion is met, designing such algorithms is also a topic for future work.
for general problem classes (C2.1 C3
10

---

Acknowledgements
This research was supported by a Turing Fellowship (EPSRC grant EP/V025562/1), The computations were performed using the University of Birmingham's BlueBEAR HPC service. See http::/www.bbr http://www.bbiiiiia..aaa. ac. wkkbear for more details.
References
[1] Angeline and J. B. Pollack. Competitive environments evolve better solutions for complex tasks. In Proceedings of the 5th International Conference on Genetic Algorithms, pages 264-270, 1993.
[2] K. Arulkumaran, A. Cully, and J. Togelius, AlphaStar: An evolutionary computation perspec- tive. In Proceedings of the Genetic and Evolutionary Computation Conference Companion. GECCO '19, pages 314-315, 2019.
[3] Auer, N. Cesa-Bianchi, Y. Freund, and R. Schapire. The nonstochastic multiarmed bandit problem. SIAM Journal on Computing, 32(1))48-77, 2002.
[4] D. Balduzzi, S. Racaniere, J. Martens, J. Foerster, K. Tuyls, and T. Graepel. The mechanics of n-player differentiable games. In Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 354 354-363, 2018.
[5] A. Benford and K. Lehre. Runtime analysis of coevolutionary algorithms on class of symmetric zero-sum games. In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO '24, pages 1542-1550, 2024.
[6] A. Benford and P. K. Lehre. A general upper bound for the runtime of a coevolutionary algorithm impartial combinatorial games. In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO '25, pages 1594-1603, 2025.
[7] N. Brown, A. Bakhtin, A. Lerer, and Q. Gong. Combining deep reinforcement learning and search for imperfect-infommane
games. In Advances in Neural Information Processing Systems 33, NeurlPS '20, pages 17057-17069, 2020.
[8] N. Brown, A. Lerer, S. Gross, and T. Sandholm. Deep counterfactual regret minimization. In Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 793-802, 2019.
[9] N. Brown and T. Sandholm. Superhuman Al for multiplayer poker. Science, 365(6456):885-89) 2019.
[10] Casgrain, B. Ning, and S. J. and. Deep Q-learning for Nash equilibria: Nash-DQN. Applied Mathematical Finance, 29(1):62-78, 2022.
[11] N. Basa-Bianchi and G. Lugosi. Prediction, Learning, and Games. Cambridge University Press, 2006.
[12] E. Chigot and Wilson. Coevolution of neural networks for agents and environments. In Proceedings of the Genetic and Evolutionary Computation Conference Companion, GECCO '22, pages 1306-2309, 2022.
[13] D. Corus, D.-C. Dang, A. V. Fremeev, and K. Lehre. Level-based analysis of genetic algorithms and other search processes. IEEE Transactions on Evolutionary Computation, 22(5):707-719 2018.
[14] V. Costa, N. Lourenço, and P. Machado. Coevolution of generative adversarial networks. In International Conference on the Applications of Evolutionary Computation (Part of EvoStar), pages 473-487, 2019.
[15] C. Daskalakis, P. Goldberg, and Papadimitriou. The complexity of computing Nash cquilibrium. Communications of the ACM, 52(2):89-97, 2009.

---

[16] B. Doerr, C. Doer, and J. Yang. Optimal parameter choices via precise black-bon -ox analysis. Theoretical Computer Science, 801:1-34, 2020.
[17] B. Doerr and F. Neumann. A survey on recent progress in the theory of evolutionary algorithms for discrete optimization. ACM Transactions on Evolutionary Learning and Optimization, 1(4):1-43, 2021.
[18] S. G. Ficici. Solution concepts in coevolutionary algorithms. PhD thesis, Brandeis University, 2004.
[19] A. Gilpin, S. Hoda, J. Peña, and T. Sandholm. Gradient-based algorithms for finding Nash equilibria in extensive form games. In Internet and Network Economics, pages 57-69, 2007.
[20] A. Greenwald and K. Hall. Correlated Q-learning. In Proceedings of the Twentieth International Conference on International Conference on Machine Learning, ICML '03, pages 242-249, 2003.
[21] R. Guha, R. Mckendrick, B. Feest, and K. Deb. Multi-objectiive competitive co-evolutionary optimization and regularity- based decision- for two-agent wargame strategy optimization. IEEE Transactions on Evolutionary Computation, 2025.
[22] A. Hauptman and M. Sipper. GP-EndChess: Using genetic programming to evolve chess endgame players. In Proceedings of the 8th European Conference Genetic Programming, EuroGP '05, pages 120-131, 13,, 2005.
[23] E. Hazan. Introduction to online convex optimization. Foundations and Trends in Optimization, 2(3 4):157-3223 2016.
[24] J. He and X. Yao. Drift analysis and average time complexity of evolutionary algorithms. Artificial Intelligence, 127(1):57-85, 2001.
[25] J. Heinrich and D. Silver. Deep reinforcement learning from self-play in imperfect-innformaiion games. arXiv preprint /603v:/603.0/ 121, 2016
[26] E. Hemberg, Moskal, U.-M. O'Reilly, F. Liu, and I.. Fuller. Evolutionary and coevolutionary multi-agent design choices and dynamics. In Proceedings of the Genetic and Evolutionary Computation Conference Companion, GECCO '25, pages 559-562, 2025.
[27] E. Hemberg, J. Rosen, G. Warner, S. Wijesinghe, and U.-M. O'Reilly. Detecting tax evasion: a co-evolutionary approach. Artificial Intelligence and Law, 24(2):149-18)) 2016
[28] M. Hevia Fajardo, J. Toutouh, E. Hemberg, U.-M. O Reilly, and P. K. Lehre. Runtime bounds for coevolutionary algorithm classes of potential games. In Proceedings of the 18th Conference on Foundations of Genetic Algorithmss, FOGA '25, pages 85-95, 2025.
[29] M. A. Hevia Fajardo, F. Hemberg. J. Toutouh, U.-M. O'Reilly, and P. K. Lehre. A self-adaptive coevolutionary algorithm. In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO '24, pages 841-849 2024.
[30] M. A. Hevia Fajardo and P. Lehre. How fitness aggregation methods affect the performance of competitive CoEAs on bilinear problems. In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO '23, pages 1593-1601, 2023.
[31] M. A. Hevia Fajardo and K. Lehre. Ranking diversity benefits coevolutionary algorithms on an intransitive game. In Parallel Problem Solving from Nature PPSN XVIIII pages 213-229, 2024.
[32] M. A. Hevia Fajardo, P. K. Lehre, and S. Lin. Runtime amalysis of co-evolutionary algorithm: Overcoming negative drift in maximin-optimmsstion. In Proceedings of the 17th Conference on Foundations of Genetic Algorithms, FOGA '23, pages 73-83, 2023.
[33] Hu and M. Wellman. Nash Q-learning for general-sum stochastic games. Journal of Machine Learning Research, 4:1039-1069, 2003.
12

---

[34] S. Ito, H. Luo, T. Tsuchiya, and Y. Wu. destance-dependee regret bounds for learning two-player zero-sum games with bandit feedback. In Proceedings of the 38th Conference on Learning Theory, volume 291 of Proceedings of Machine Learning Research, pages 2858-228882 2898,2892,, 2025.
[35] W. Jaškowski, K. Krawiec, and B. Wieloch. Fitnessless coevolution. Proceedings of the Genetic and Evolutionary Computation Conference, GECCO '08, pages 355-362, 2008
[36] D. Klijn and A. Eiben. A coevolutionary approach to deep multi-agent reinforcement learning. In Proceedings of the Genetic and Evolutionary Computation Conference Companion, GECCO '21, pages 283-284, 2021.
[37] V. Kovařík and V. Lisy. Analysis of hannan consistent selection for monte carlo tree search in simultancous move games. Machine Learning, 109(1):1-50, 2020.
[38] P. K. Lehre. Negative drift in populations. In Parallel Problem Solving from Nature PPSN XI, pages 244-253, 2010.
[39] P. K. Lehre. Runtime analysis of competitive co-evolutionary algorithms for maximin optimi- sation of a bilinear function. In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO '22, pages 1408-1416, 2022.
[40] P. K. Lehre. Runtime analysis of competitive co-evolutionary algorithms for maximin optimisa- tion of bilinear function. Algorishmica, 86(7):2352-2392 2024.
[41] P. K. Lehre, M. Hevia Fajardo. J. Toutouh, E. Hemberg, and U.-M O'Reilly, Analysis of pairwise dominance coevolutionary algorithm and DefendIt. In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO '23, pages 1027-1035, 2023.
[42] K. Lehre and Lin. Overcoming binary adversarial optimisation with competitive coevolu- tion. In Parallel Problem Solving from Nature PPSN XVIII, pages 117-132, 2024.
[43] K. Lehre and S. Lin. Towards runtime analysis of population- baseed co-evolutionary algorithms on sparse binary zero-sum game. Proceedings of the AAAI Conference on Artificial Intelligence, 39(25):2004427762. 2025.
[44] P. K. Lehre and C. Witt. Black-box search by unbiased variation. Algorithmica, 64(4):623-642, 2012.
[45] J. Lengler. Drift analysis. In Theory of Evolutionary Computation: Recent Developments in Discrete Optimization, pages 89-131. Springer International Publishing, Cham, 2020.
[46] Y. Liu, A. Zhou, and H. Zhang. Termination detection strategies in evolutionary algorithms: A survey. In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO '18 pages 1063-1077 2018
[47] A. Maiti, R. Boczar, K. Jamieson, and L. Ratliff. Near-optimal pure exploration in matrix games: A generalization of stochastic bandits and dueling bandits. In Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, volume 238 of Proceedings of Machine Learning Research, pages 2602-2610, 2024.
[48] C. McDiarmid, On the method of bounded differences. In Surveys in Combinatorics, 1989: Invited Papers the Twelfth British Combinatorial Conference, London Mathematical Society Lecture Note Series, pages 148-188, 1989.
[49] Noble and R. A. Watson. Pareto coevolution: Using performance against coevolved opponents in game as dimensions for Pareto selection. In Proceedings of the 3rd Annual Conference on Genetic and Evolutionary Computation, GECCO '01, pages 493-500, 2001.
[50] G. Ochoa. Error thresholds in genetic algorithms. Evolutionary computation, 14(2):157-1822 2006.
[51] M. J. Osborne and A. Rubinstein. A course in game theory. The MIT Press, 1994.
13

---

[52] T. Paixão, G. Badkobeh, N. Barton, D. Çörüş, D.-C. Dang, T. Friedrich, P. K. Lehre, D. Sudholt, A. M. Sutton, and B. Trubenová. Toward unifying framework for evolutionary processes. Journal of Theoretical Biology, 383:28 43, 2015.
[53] D. Pfau and O. Vinyals. Connecting generative adversarial networks and actor-critic methods. arXiv preprint arXiv: 1610.0194, 2016.
[54] B. Pollack and A. D. Blair. Co-evolution in the successful learning of backgammon strategy. Machine Learning, 32(3):225-240, 1998.
[55] E. Popovici, A. Bucci, R. P. Wiegand, and E. D. De Jong. Coevolutionary principles. In Handbooo of Natural Computing, pages 987-1033. Springer, 2012.
[56] R.-J. Qin and Y. Yu. Learning in games: A systematic review. Science China Information Sciences, 67(7):171101, 2024.
[57] Schäfer and A. Anandkumar. Competitive gradient descent. Advances in Neural Informa- tion Processing Systems 32, NeurlPS 19, 2019.
[58] M. Szubert, W. Jaškowski, and K. Krawiec. On scalability, generalization, and hybridization of coevolutionary learning: case study for Othello. IEEE Trunsactions on Computational Intelligence and Al in Games, 5(3):214 226, 2013.
[59] M. J. Turner, E. Hemberg, and U.-M. O' O'Reilly. Analyzing multi-agent reinforcement learning and coevolution cybersecurity. In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO '22, pages 1290-1298, 2022.
[60] O. Vinyals. I. Babuschkin, W. M. Czarnecki, M. Mathieu, A. Dudzik, J. Chung, D. H. Choi, R. Powell, Ewalds, P. Georgiev, J. Oh, Horgan, M. Kroiss, Danihelka, A. Huang. L. Sifre, T. Cai, J. P. Agapiou, M. Jaderberg, A. S. Vezhnevets, R. Leblond, T. Pohlen, V. Dalibard, D. Budden, Sulsky, J. Molloy, T. L. Paine, C. Gulcehre, Z. Wang. T. Pfaff, Y. Wu, R. Ring, D. Yogatama, D. Wünsch, K. McKinney, O. Smith, T. Schaul, T. Lillicrap, K. Kavukcuoglu,
D. Hassabis, C. Apps, and D. Silver. Grandmaster level in StarCraft II using multi-agent reinforcement learning. Nature, 575(7782):350-355 Nov 2019.
[61] R. Wang, J. Lehman, J. Clune, and K. O. Stanley. POET: Open-ended coevolution of en- vironments and their optimized solutions. In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO '1,, pages 142-151, 2019.
[62] K. Xu, C. Li, J. Zhu, and B. Zhang. Understanding and stabilizing GANs' training dynamics using control theory. Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 10566-10575, 2020.
[63] G. Zhang and Y. Yu. Convergence of gradient methods on bilinear zero-sum games. In International Conference on Learning Representations, ICLR 220, 2020.
[64] M. Zinkevich, M. Johanson, M. Bowling, and C. Piccione. Regret minimization in games with incomplete information. In Advances in Neural Informtion Processing Systems 20, NIPS '07, 2007.
[65] A. Zychowski and Mańdziuk. Coevolution of players strategies in security games. Journal of Computational Science, 68:101980, 2023,
A On the strength of Definition 3.2
Theorem A.1. Let Sx be any selection operator, let G == (8.),fi.f2.4 x B) e SINGLETONSOL.TIION and let (Mx,My) E MUTATION(X,)) (0,1)). constant 8 > 0 such that for all X N and populations P E X and Q E y
Then there exists
P (A:G) > 5A (Po, = (P, Q) < 55A
where = As(Mx, A). In particular, i N + R is any function that grows faster than exponential (that is, h()) ((e for any ā E IR), then limx (1 & h())] 1.
14

---

Proof. Write S = {(2", .v") }, Because
Mx(x)(x) My(w)()) E (0,1)
(10)
holds for every (z,y) X x V, either have (x*r")("") < 1 or (v") < Assume without loss of generality that Mx(x") (x=)))))) < 1 (as the case My(y")(")) < 1 is similar). Since
(TO) implies that Mx (x) 0 for all x + x', we have (x(xx)xx)) for all # x" also. Thus, we define
8 2 min In (1 (xxxx) 00
it now holds for any x. X' and x² (x that P(a' # x*)= 8/2 Thus, for any P E X and
Q E JAa, by considering Line 4 of Algorithm
P((P++1 x
PAQ Q) -AA/2
We may now bound for any r N and (P.Q) E X² x yM,
PiT > T (Po, Qo) (P.Q) < (1 --ee-o -881/27 & exp (ape-re-00 -8/22)
Setting Ed now yields
P P dcp (A; 36 (Po. Q0) = -P.QQ) < exp (-E < (63A/2)- 22 == =
where we have used the identity exp (-z) & - for > 0.
B Deferred proofs
B.1 Preliminary results
Several of our proofs rely analysing the distribution of [(P++1 x Q++1) n ( B) (that is, the number of predator-prey pairs that lie on the solution concept at time + 1) given the value of I(Ps x Q.) n (A B) is fixed. For this task there are many concentration inequalities that will suffice, however it is particularly convenient to use McDiarmid's inequality [48), given as follows.
Theorem B.1. Suppose f X1 x... x Xn + R has the property that substituting the value of the th coordinate changes the value of f by at most o. Suppose that XI...., Xn are independent random variables where X, E X, for each i E [n]. Then, for any t > 0.
212
P X,) > E
X,)] + f) & exp
Σ c
212
P(f(X, X,) E X X.,], - t) < exp
In order to later prove conclusion A2 of Lemma 3.4 roughly speaking we need to estimate the amount of time until the number X, of predator-prey pairs on the solution concept drops below a certain value. This detail will be handled using the additive drift theorem [24] 45), which provides such estimations provided one can prove minimum expected drift on such pairs in each generation.
Theorem B.2. Let (2 be a sequence of non-negative random variables with a finite state space C R such that 0 E S. Let T inf (1. 2 X, = 0}. Suppose there exists 8 > such that for all E S {0) and all 2 0,
A.(s) = B[X, - X X₂ = 8) 1100
Then
E [
E
15

---

B.2 Basic calculations
In several of our proofs, certain steps require some calculations that are straightforward, however also lengthy (in many cases they are working through standard calculus arguments to establish the infimum or supremum of certain functions). In order to benefit the flow of presented proofs, we
provide these calculations separately here.
Proposition B.3. Let C' [0,3) be fixed, and let a: [0, 1]2 + R and 3: [0, 1]2 - R be defined by
ala, b) = =a(a- + Cb(1 - a)); B(a,b) - b(b Ca(1 -)))
It holds for any y E (0, 1] that
sup ae(r.]] a(u, 7/4) 7/a, = (1+0)v1-0+))
Proof. The case C- 0 is trivial so additionally assume that C' 0. Let g: [7, 1] - R be given by g(a) axa, 7/a) /(a,,/a)// We have
g(a) (a + c a
-c) (2 +Cao - (c a
72
a a2 022
+o
and hence,
g((a) 2Ca - (C² +C (C² +0) 7²
20
a²
a3
C (2a² - 11+C)aa + (1+ +1+ 272)
(a2 - -2)22² - C1ha+h+ 27)
1 (a+ v=)(2n² - (1 + C.aa + 27).
The discriminant of the quadratic 2a² - + +)
(1 (1+ 16y < (1+ - 167 = 7- + -)- -16) < Therefore, 2a² (1 +1+ C)aa + 2y positive for all a E Hence, h' h'(a) negative for a E (7, v7)
and positive for a E (v7, 1), and hence
inf g(a) = 2(v7) = (1+ aEh.u
The result now follows.
Proposition B.4. Let a [0, 112 + R be defined by ala, b) = a(a+26(1-aa) For all E (0, (0.9/16).
we have
ab
inf (a a(a, b) a(b,a)
> (3 22
(11)
Proof. Let g (0, 2 + R be given by g(a. a(a, a(,, a)/(ab) (a+ + 26(1 - (b)
2a(1 b)). We can compute the partial derivative
0g
da b) (1 2b) + 2a 2ab) + (a + 26 - 2ab) 26)
5b 6b2 + 4a 12ab + Sab²
b(3 6b) + 4(1 - 2b)(1 b)a.
If < b & 1/2, then 8g (a,b)
> b(5 6b) > 0. On the other hand, if 1/2 < b < v%, then
8n
4(1 (11-2b)(1 bb) is negative, and so
0g
(a. b) > b(5 6b) + 4(1 - 21) - b) / > 6(5 - 6b) + 3(1 - 2b) - b)
Da
= 5b - 6b + - 9b + 6b = 3 - 4b 3 3 4/723 4(3/4) = 0.
16

---

As da any a, b, E (0, vnJ. g(a.b) b) & (Vv[((/ b) g(b, vn) ,/ v1) (3 - 27)². Therefore,
dg is non non-negative on (0, v we have g(a, b) < s(v7. b) for all a. E v Therefore, for
1 (a.b)E(0.V)) ala (b, (a,b)E(U g(a. b) (3 27)²²
ab
inf
inf
as required.
Proposition B.5. Let [0, + R and 3: [0, + RR be defined by
a(a, b) = (1 (1- (1-(1-a))) (1 (1,b)),
B(a, b) (1 (1-
aa)).
holds for any r E (0, 1] that
7
sup aEh.1] a(a, 7/a) 3/a,
(1- (1 (1-
Proof. ge: : 1 + R be given by g(a) 7/a)
B(a, 7/a) and note that g(a) > 0 for all
a E 1.. We have g(a) = B(a) where
A(a) 1 (1 - a1=a)*
B(a) = 1 (1-7/1))
C(a) - (1 - >/a)"
D(a) - a1
Therefore we write
A'(a)
A(a) + Ca(a)
+ D'(a)
D(a) + B'(a)
g'(a) = g(a)
C(a)
B(a)
[k(1 - -a) a)h11
(2) k(1 - -7/a)(-1
{l - a)c-1
- 7 {( (1-7//ae--
g(a)
11 (1 a)
a2 1 (1 (1)7
1 (1 aj²
02 1 - (1 7/03²
g(a) (hx(a) hx(7/aa + he(a) - he(7/a)),
(12)
where for m N we define hm l 1] + R by
hm (a) ma (1 a) m-
- a)m
We will shortly prove that any m E N. Am is a decreasing function. then follows that h4 (a)
hy (1//a)) + he(a) - he(r/a) is decreasing in Thus, from 122 it can be seen that g' (a) > 0 for
a E ly vil and ga( & 0 for a E l/7, 1], and hence
inf g(a) = min (,(7), (()) = (1 (1-1)))) - (1 7))-) aE(r.]]
The proposition then follows by noting that
?
7
sup aEh.1 aa,, 7/4)- B(a, inf infesty. s(a)
Thus all that remains is to prove that hm is decreasing. To see this, observe using the quotient rule that
him (a)
(1 - (1 a) ((1 a)m-1 - (m 1)a(1 a)m- a(1 tm -1 (m(1 -a) aam--1
(1 - (1 - amm
m
- m- (1 - (1
(m 1)a) ma(1 mm
(1 (1 - a)m
-amam22 m-
(1 a) ma) ma(1 11 m)m
(1 (1 J2
a) m m-2 (1 a)m ma]
(1-a) mm
o(a)
(1 (1 a) )
(1 - (1 m)m)
where o: (0, 1] + R is defined as c(a) =
We have ②'(a) = =m(1-a)m-I-m < 0
and (0) = 0, and so db(a= & 0 always. Therefore, (a) & 0 for all a E hy 1). showing that Iim decreasing function and completing the proof of the proposition.
17

---

Proposition B.6. Let e [0. 1 + R be arbitrary, and let d [0, - R be such that either d([0, 113) - [0, oo) d((0, 1] _ (- For a E [0. let
ao ao b) a(c(a, b) d(a, o). Bo (a b) = b(c(b, + d(b,a) (1 - -)).
Then, for any y E (0, 1] holds that
7
1
sup sup véh.1)EE(U.. Oa (a, 7/a) Bo (a 7/0)
sup aEh,a c(a, 7/a) (dr/a, a) + d(7//,a))
Proof. First, note that for any a, b E [0, 1] and we have ab
ab
(13)
ai (bbb)) oo(a, -ola,b))Bola.b) c(a,b) (c(b,a) a) + d(b,a))
Next, for all fixed b (0, 1] we have as(a,)) b) Ba (a b)
(c(a, b) d(a, b) o)((b)))) + (1-o))
ab
[c(a, (c a) d(b, a() a [d(a, b)c(b, a) c(a, b)d(b,
+ [d(a, b)d((b - o).
By the assumptions of the proposition, d(a. b)d(ba 0. Thus, az b) Bo(a, attains its minimum at some E (0, 1j. We now have
sup sup aE(y.1) Oo (a, 1/0) 7/a)
sup max aElr.) aa 7/a) (0 7
?
sup max aE[x1]
(ao(a,7/a) Bola,n/a) ai(a, 31 (1,
sup max ac <Eh..]]
aooaa, w/0) sola, ao(3/a,a) Bo(n/a,a)
?
max
sup (0(a,7/a) Bo(a, 7/0) aEh:1] 00(7/a, a) 80(1//,
sup
aEh.1]
max
sup [Eln.1] ao 7/a) (o(a, d'E(n.1) aula' 7/00) Bu (//a)/
sup
7 aE[h.1] a0 7/a)
sup
sup <ch.1] ((.7/aa) (c(1/a, a()/a,a))
as required.
B.3 Proof of Lemma
Lemma 3.3 is simply the case [| = 1 in the following generalisation.
J Lemma B.7. Let Sx be a selection operator, let G == Nv, A x B), and let 7 E 00, 1).
Suppose there exists a family {(au, hie of pairs of increasing functions o, : [0, 1|2 [0, 1 and
3: [0, 112 [0, 1] such that for all X E 1 and populations P. X² and Q E y there exists E such that
J A
QQB
P(x E A) 2
X
X
[Pn A|
1Qn
B
P(y E B) > 3
X
X
18

---

holds whenever (I,3) ~ Sx(P, Q). Then, provided (Mx, E MUTATTOO(X; Y; :90(1)) 1)) where
7
go(n) == sup sup aEtv.1] xer a;(a,7/a) 3i(a,7/a)'
As(MM.MMgr A) is y-stblle on G.
Proof. Let q x)) (x(x)(a) My(r)(v).
Because (Mx;MM)
MUTATION(X,)) (go(1)) 1]), have 9 %0(7). Let Ao N and 0 be such that 2/A0 & and
7
q >> sup sup aE|T,1] EE a; 7/a) 7/a)
(14)
We remark that (and Ag) can be chosen to depend only on 7, q. and {(a (,)lee,, and hence have no dependence on A. Label 5 = A x B and let X, I(P: Q:) n S|. Suppose at time t that IP A = aA and Q2, n B bλ where == ab ž 7. Using the fact that c/a 2 7/a and E (n, 11, there exists some i E / (depending on P. and Q.) such that for arbitrary k.
P((P++1 Q(4)(1)))))) E S) q (a, B((a,b) 3 q ac(a,7/a) Be(a,
(15)
We may write X₁ = (P=1))) (P41) where
((I.,,)))...,, = Σ 1((2)) E S).
j.kEAA
Note that modifying the value of any one of the (z,, U5) changes the value of f((11(((1)) Vi), (xx, by most 2X. For any 2 y and À > Ao we have
15 P((Pr+1()) Qz+1 ES 2 (7+8+2/An)A4 1)
E[X++1 Xx, = =x = Σ
j.AE(A]
= (7 + E)A² + X²
Ao
> (++ + 21 22 &)+2
Applying Theorem B.I now gives
2
P(X++1 <>>² X₁ -x>) < exp
exp (-1e2A).
(16)
(2
Write A Mo(Mx,My, For a given t, if the event T22p (A;G) < T occurs then there must
exist some t with 0 & t < J such that X, > 72² and X & 7x2 Therefore we have the relation of events
(TT CU 2 7X2 X & 7
(17)
By taking a a union bound now yields for any (P.Q) E X x yd satisfying ((P (PxQ)
>
yx?,
PIT (A:G) & d (Po. (P.Q))
P(X, > 1 & {x27)
P(X++1 & & 1x/1x, > 7)3)
16
exeep (- - c -
thus satisfying Definition 3.2 for 8 = _=²² (which is independent of A).
19

---

We now consider a connection between Lemma 3.3 (and implicitly also Lemma B.7 and the coevolutionary level-based theorem 44)] The coevolutionary level- theorem is stated with respect to constant yo and subsets of the search domains A Am C X and B1 BI...., Bm E y. with A1 = X' and B1 = V such that at each time I, the largest j for which [(P x Q:) x B2) > 2od2 is identified as the 'current level'. By using assumptions arising from algorithm and problem instance, such as lower bounds on the probability of generating offssring on the next level, the theorem derives an upper bound on the expected time for a CoEA to reach the final level Am By (which is typically identified with the solution concept). This form of analysis extends the classical level-based theorem, which uses similar constructions to derive upper bounds on expected runtime for EAs 13
One of the assumptions needed to apply the coevolutionary level-based theorem ((G2b) in 40
Theorem 3J) is that jf is the current level (so that (Pt x Qr) (Ay x B,)l > 7)A), then the expected proportion of level-j pairs in the next generation is strictly larger than 7o- Precisely, the condition is
P(P++1 (R)) Aj) (1) E By) > (1 + +8)a,
where 5 is constant (on which the eventual runtime bound depends) and k, é [A] are arbitrary indices. In the proof of the coevolutionary level-based theorem, this assumption is used to show the populations do not regress to lower level, informally that they have stabilised It is therefore not too surprising that if we identify the solution concept A x B as the current level (and also identify 70 = 7), then the assumptions of Lemma 3.3 imply assumption (G2b). Indeed, with the assumptions of Lemma 3.3 setting a = PP: n A| and arguing as in (T5) yields
the current level.
P(P++1 (A:) E A) P(Q (4) E B) > q (a, b) 3(a, b) > q a(a, 7/0) 9(a,7/u
> 7 (1 + +000=//110 </>)><//>>>>>>>>>)>> (1 8)
where is chosen (depending the mutation operators) in (4) and we set ā = s/1o- Thus, there is potential for much of the analysis in this paper (particularly the derivations of the functions a and within the proofs of Theorem 3.7 3.77nnd and Theorem (.8) to also be used to derive level-based runtime results for specific problems and problem classes.
B.4 Proof of Lemma
Before proving Lemma 3.4 we will state and prove the general result outlining situations where instability occurs which applies to games with arbitrary search domains rather than just bitstrings. Lemma 3.4 will then be derived using this result.
In general, if mutation operator is somehow rigged to produce offspring inside or near to a game's solution concept with unreasonable probability, then stability can be trivially guaranteed even for CoEAs using impractical selection operators (for example, CoEA using mutation operator that returns elements of the solution concept with probability will always be y-stable for any 7 E [o, 1)). Therefore, obtain useful negative results it necessary to have an underlying assumption related to the innate tendency the mutation operator has for moving towards or into the solution concept. In the case of Lemma 3.4 such an assumption is implicit from the fact that the relevant mutation operators over (0. 1}" are unbiased (see Definition 2.3). As there is not an analogous notion of unbiasedness for arbitrary domains, for the more general lemma in this appendix we will simply bound above the probability of mutating into the solution concept from outside (see (19 ).
Lemma B.8. Let 4,,,, (0, 1), let Sy be a selection operator, and let G S SINGLETONSOL.UTION
be problem class. Suppose there exist continuous increasing functions a 1]2 - [0, 1] and 3: [0, 1]2 + |0,, 1] such that for all X E N, problems (X,Y, (x" vy)) E G. and populations
P E x and Q E
1Q (2 P(x= <a [Pn
[Pn
QQ
and Ply g") <B
A
A
holds whenever (2,y) ~ Sx(P,Q) Q). Then provided (Mx, My) E MUTATION (, 10, g)) where
q < sup dEl:1 a(a,7/a) 3(a.7/a)'
(18)
and also
max
sup Mx(x)(x"), sup Msr(w)(8)) < 8//3, xftt
(19)
0Zy"
20

---

the algorithm , My, A) is not y-stable on any G E g.
Proof. Let (Mx,My) E M ql) and define
qx = sup (x)
and
④y = sup supp yEy
(20)
=EX
Note that by Definition 2.2 we have qx & q. Adopting the notation of a given selection and
mutation step in Algorithm (that is, sampling (a, y) Sx Qi) and then sampling P (j) Mx(ax) and Q++ My). for fixed P. and Qs we can compute
P(P(+1() = x²) = PP(P++ (i) = x x xx )p( x²) + P(P++1 (ï) x² 1 1 xx+x" x )P(( + x²)
P [ Q 1en
+P(P++1 =x" lx
A [P H
X 1
< qx
+ sup Mx(x))())) wxp
A
1v
[
Qun A
qx-0
a
Similar calculations apply for Q(+1 (j), and so we have for arbitrary E [A],
[P,n((")]
Q2 n [r"
C
P(P++1() =x²) E qx a
+
X [ [
X
3
(21)
P(Q++1(1)= = v²) E qy 3
A
3
Using 18 let a ly, 1] be chosen such that, setting b 7/a. a, we have
7 7-5
<< a(a, b) ((a, b)
Using that and B are continuous, let 17 > 0 and A N be chosen such that
7
1 -
q ala + b.b + x) B(a + b)
(22)
Let A 2 G G. and consider A == MsM,,,My. A) with initial populations Po E X and
Qo EAaA chosen to satisfy iPol [aA] and Qo = [bA]. Using that [a>] & a and [bA] & b b+
together with the fact that and B are increasing, it holds for j * k that
P((P((), Q1)) E S)
(gx a(a + 1, #) (oy B(a + 4.6 + 6. +)
q a 1. b. .1)) -))3(aa+ (3a b.. b. 1
< - 1) - Setting S = [==1((("'0__0 }}"), we may write [PP x Q1) = (((P(())Q.(()).........))))))))) where
(23)
(Fx. Σ ((1g. S).
j.kE(A]
Note that modifying the value of (Iz, changes the value ((I11,)))........ (Ix, vA)) by at most 2X. We also have
E[[(P: x Q1) = Σ ((())))Q((4))
E)
(--n 1/2)1 + ( x
iAkE[A]
Applying Theorem B.I now gives,
2n 21 [TEe (2A)2
PT P (A: = 1] P[[(P] x Q1) & 922) < exp
= =exp (-)1²
and hence is not ststbe on G.
21

---

We are now ready to derive Lemma 3.4 using the more general result.
Proof of Lemma 3.4 First we will derive
A1
Using
4 let no E N be chosen such that
7 -3/no
q < sup
(24)
aE(T.]] a(a, (/a.)//)-- 7(a.7/aaa
Suppose that n b no. G E In, and (Mx, My) E UNBIASED(1 ; [0, q)). as per the conditions of A1 In accordance with the characterisation of Lemma of [16), an unbiased mutation can be simulated by choosing a random number E {0, 1,.., n) and then flipping uniformly selected subset of bits. Thus, when combined with our minor assumption that MMx (1) & 1/n, we have that
Mx (x) (xxx
My(x) < 1/n & 1/ holds for every x, x' E (0, 1 with 전 x'. Therefore,
condition 19] of Lemma B.8 also holds for Ç 3/no. Furthermore, the condition [8] of Lemma B.8
also holds for < 3/no due to (24). Therefore, Lemma B.8 shows that As(Mx, My,,) A) is not
7-stable on any G E Gn. and so Al holds.
We now turn to proving A2
Let 8 > 0 now be chosen such that
(1 28)ab
q < inf (a. a(a,b) b) aab.aa)
(25)
Note that the assumption in Definition 2.3 that My = MMx implies that gx ạy & / (where
qx and by defined in (20). Therefore, as the calculations at the beginning of the proof of
Lemma B.8 apply with Ç = 3/n, we can deduce from 21 that for arbitrary j E [A].
1e H A 10 1e {rr P [2
Pr {a H
1
P(P++10) F.) E Va.a
X
n
(26)
H
1
P(Q++10) E B F)) E V 3
A
n
We will examine the random variable
(Ps nS) 0
if P VFA and nQ < VFA.
X1
otherwise.
Suppose that X, = & 2 A.n) Writing [P:n ad and Qin = bd, we have v% and ab > <(n). We have for j # ki
= (x)))))) (())
(Vq-a(aa b) + + -(V--a(b.0) 1t) < q a(a,b b) a(b.)) 2
(1 - 26)ab + 3
and for j = k,
P((P.+ = (x" (x))))) & Kab + 2.
We now bound
Ae(s) E[X, - X X, = > E(X, (Pt+1 x ( =
= abx²- Σ P((P.+1()) (j), (k) ES| X, =)
J,KE(A)
abx² (1 - 28) - (3/m)X² Kabx - (2/n)> A
M ((25- - K/A)ab- - 5/n) X2 > (ō5(n) 5/n]
(E(n) x²
W
2
Thus, by applying the additive drift theorem (Theorem B.2 and also noting that Xo < X2, we have for T inf (t: X, {(m))?).
2
E <
ds(n)
22

---

(We remark that Theorem B.2 is not applied directly to the stochastic process (X)) but rather to a modified process X, == max ( (X, {(n) 0}; the fact that [E[xo] & X² is also used.) By Markov's inequality, it therefore holds for any T(n) > 1 that
2
IP(T > 7| (e(n)T(n)
Next, let Tbad = min {t max [IP, n H. n H} > > H|M ad 10, [
and [2: {yr} H bλ E [0, / then by recalling that > 2/(6/7)
B| < (Vg a(a,b) + 1 < (V7 (( v7) + //
(v -1 (1- 25)7 + } ((1 5) + # < (1 8/2)
Using a similar calculation for Qi| n {2-) H applying Theorem B. and taking union bound over time steps, we now obtain
P(Thad r(n)] & (n) exp -202g22//4 =nT(n) 8/2/2 & 2T(n) 5r(n)e(n)
Setting S {(="(10"00'"" v")}, we have T= min (T (5), Thad); and hence
3
(8) > r(n)] < P[T [(n)] PTahad T(n)) & 8r(m)e(n)
as required.
B.5 Proof of Theorem 3.6
While its exact statement is not necessary for the proof of Theorem 3.6 the following is formalisation of what means to be a k-candidate selection operator. The proof of Theorem 3.6 is then given afterwards.
Definition B.9. A k-candidate selection operator is selection operator Sx for which there exists function Sx : x x yk x X x V + P(X x y) satisfying the following two properties.
E1 For all P' E x Q' E* PEX,, and Q E ydA
P(OEP'AVEQ))
holds whenever (x.y) 3P ('',''''' P.Q).
E2 For all P (II...., E Xx and Q = (y1,.... ..........!!... y2) E ena.
1
Σ Σ Sx((zi,..., (U:. P.Q), = Sx(..)..
2
i E(A) JEEA
Let G E BITSTRING, A SINGLETONSOOLUTION and let (x". be the solu- tion concept for Let E and let PE X', Q E y arbitrary. Write a = IP (a" H// and b Q n fu" 1/>. Because Sx is k-candidate selection operator, if (æ, y) Sx Q) then the event x = xx can occur only at least one of the predator candidates is equal to x=, an event which occurs with probability - (1 a) In particular P(x x²) 1 - (1 - a)* More formally, if we write P (21...., 2x) A and (Vi.... yx) E y and also define / = {i E [X] # x*}
Proof of Theorem 3.6
23

---

(so that ||| = (1 a))), we have
P(z = x²) = Σ (x (z)))
yey
30
Σ
Σ
Sa((ci........ (yh, ................................ P..).P.U.. (rQ)(r,
2h
yEY
Mo E|A] JUEA
E
E
3x((2))) TTe) TJ)) ;Vr,), (x,
2
BEY
SE STA
Σ
Σ
Ex (.))
A
J JEA NEY
*² (11 (11-00 a)Aa* = -1
Σ
E
A
X
14 (E Jn EEA
Similarly. P(y y') (1-(1-5) 6)β. Moreover, the event r = x² Ay y can occur only if at least
one of the k predator candidates is equal to x" and one of the prey candidates is equal y", which occurs with probability at most (1 - (1 (1 - (1 b)*) < ab. Therefore, the prerequisites of Lemma 3.4 are satisfied with a(a, b) - (1 - a)², 3 = - (1 61- and K = k2t B1 now
follows by applying Al and verifying that
sup aEh..
(1 (1 (1 - 7/a)a)
1 (1 7)
A2 follows by applying A2 and verifying that ab
inf (a.b)E(0. (1 (1-(1)))))1 (11-b(b))))) b)a) > inf ab 1
(a.b) k2ab k.2"
B.6 Proof of Theorem 3.7
Proof of Theorem 3.7 We prove each of part of the theorem in turn.
C1 Let G E STRICTNASH and let B be the solution concept for G. Recall that f1 y) > F1(2',0 y) and fe > fa(2,y') holds for all x E A, X' & A, B, and y & B. Let X E N and PE Pe E be arbitrary. Write a = APA/ A and = BI/. If (z. ~ (P, then letting 1 22 be independent uniform samples from P and yı: V/2 be independent uniform samples from Q, we have
P(x A) > P(1 E AA E A + [P(#
E & A)
+ P(r AA A E)
a² + 3 aab(1 - a) = a(a }b(1 a)).
Similarly, Ply E B) > b(b 3 aa( - b)). aet [0 + R and B [0, 1| + R be given by
a(a, 6) = a(a + 6 a)) and (aa, b) b(b + aa(1 - b)). C1 now follows from Lemma 3.3 by
verifying that
(3V7 n)
sup
aE(x.1] a(a, 7/0) (a, v/a)
which can be seen by setting C C= 332/2 in Proposition B.3
and let A x B be the solution concept for G. Recall that (i > (i y) and f2 v) > fa(æ, v²) holds for all æ E A, x' & A, E B, and y & B. Let À E N and P E X2, Q E yd be arbitrary. Write a = |PnA] and b = 1 n Q If (z. S, Q), then letting 21, 222 be independent uniform samples from P and yı, 32 be independent uniform samples from Q, we have
C2 Let G E STRICTNASHI SINGLETONSOLUTION
P(x E A) > P(21 E AA x2 E A) P(11 E AA E BA $ A)
+ + & AA x2 E AΛ E B)
= a² + 2ab(1 a) = ala + 2b(1 a)).
24

---

a: [0.1]² + [0.1] and 8 [02 - [0. be given by Similarly. P(y E B) > b(b+ 2a(1 b)). a
a(a. 6) a(a 2b(1 a)) and ((a, b(b 2a(1 6)). C2.1 now follows from Lemma 3.3 by verifying that
aEh. a(a, 7/0) B(a,1/a) (3 27)
sup
7
(27)
which can be seen by setting = (f0, (0, fi, f2, (1", 1"),, where fi and f2 are given by
in Proposition
B.3
Next, let Gn =
0
if + 1 and 1" if = 1 and y + 1". otherwise,
fI
i 1 and 1". if = 1 and y * 1".
82(2,
0
otherwise,
and label A B= Let A e and P X², . yd be arbitrary. Write a = (Pn.l// and b = QQ n BJ/X. If (z, (x Q). then letting I1, 22 be independent uniform samples from P and y1, y/2 be independent uniform samples from Q, we have
P(xx E A) = P(mi E AAA 32 E A) P( E EAA E BA22 A)
+ P(xi AA E AA B)
a² + 2ab(1 a) = a(a 2b(1 a)).
Similarly,
F(y B) = b(b + 2a(1 (1 b)).
Using also the fact that Sx is a 2-candidate selection operator, the prerequisites of Lemma 3.4 are satisfied with aa,, b) = a(a + 2b(1 a)), ((a, b) b(b + 2a b)). and K = 4 (this is covered in detail in the proof of Theorem 3.6 provided in Appendix B.5). C2.2 now follows by applying
using (27). Because K < co and a(a, b) ((b, a). in order to additionally deduce C2.3 from we only need to prove that for all 7 E (0, 9/16].
ab
inf (o. b) alb,a) a)
> (3 27)
This is confirmed by Proposition B.4
Let G E STRICTNASH n SINGLETONSOLUTION n ZEROSUM have payoff function f and solution concept (z* .y). Let N and P X and Q yd be arbitrary. Write a IP H/A and = IQn (yr H/A. Moreover, let = (1 a)d and s = (1 - -))2, and note that by reordering the elements of P and Q if necessary, may assume that P(j) * x² whenever j [r] and Q(k) # y whenever E [s]. Given j E [r] we will write
[[k e [s] S(P(). Q())) < f(x ((+))
Pj
and given & [s] we will write
4h ((P)))(P()))())))) f(P())
Note that + Eşerr) Pj is the proportion of pairs (x, (P (a*)) x (Q \ (v*)) satisfying f(z v) < f(=", v). and that ExE(s) 9k is the proportion of pairs (I,y) E (2) (Q 1) satisfying fæz y) > f(x,y²) Because f(x,y") > f(z", (ra")")) f(z,y") holds for any (x,y) (P (x x (Q) (y*)) all such pairs satisfy at least one of these conditions, and hence
1
Σ jEIr)
P3 +
> 1.
(28)
kEle]
25

---

If (z. Sx(P,Q) then letting 21, 22 be independent uniform samples from P and y1 U2 be independent uniform samples from Q is not difficult see that
P(x E A
21 E AA AAM BAY y2 E B) =1
P(r E A
21 E AAZ2 FAM E BA & B)=1 =1
P(x E A
21
E
AA & AAVI BAy B) 20
and
P(r E A P(rr E A
æ & AA AA BA E =1,
#1 $ AAm E E =
21 & AA E AADI É BA B) =1 P(x E A
There two remaining conditioning cases that require more A A yn & B A y/2 $ B and Fg == I1 & A A x2 E A y1 & B A y2
E1 == I1 AA &
& B. To examine
these, write Cj { [s] ((P()),((K)) Q(C,) = (Q(k) le E Cj). ). We now have
f(x", Q(k))) that pj |C,l/r, and write
P(x E A E1) >
Σ
P(y e Q(C,) Ag U2 E Q(C,) ((PU). & f(P()).2) Et)
jELr
Σ
P(1 E Q(C,) A2 Q(C,) E1) - 5P3.
SEL
je(r]
Additionally,
P(x E AA) > P(f(11,1)) < f(x",))) E2)
Σ
P(u EQ(C)) -2)= Σ P
JELI
jE
Combining all of these observations using the law of total probability,
P(x A) > a² a(1 a) b² + 3b(11 b) +(1 +1--))2 Σ
2 +b² ( -b)2 Σp, Ps
jElri
sElr
a² a(1 a)
(3b 62 + +11 6)2 EyEn pj))
> aaa + a) 3b b² (1 b)² (+ pb)
+ + P:)
where in the final line we have used Jensen's inequality. similar argument for y yields.
Ply E B) > b(b + (1 - b) 3a a² a1) (1 (# )=) + Exela qk )
Let {(ao, Ba) Ba))o{(011) be the family of pairs of increasing functions 0a
[0. 1|2 + [0.1] 1] and
3 1]2 + [0, 1] given by
(o b) ala + (1- (1-a) -1 61 (1 (o)))
(a, b) b(b (1 (3 a² + a) (1 + { (1))
It now holds (in part due to
28 that for all populations P E X and Q E ynd there exists a E [0,
such that
Pn A
QnB
P(r E A) > 0o
X
X
QQB
Ply E B) > B
X
holds whenever (x,y) ~ SS(P,, Q). The result now follows from Lemma
B.7
26

---

B.7 Proof of Theorem 3.8
The following simple lemma will be useful in the proof of Theorem 3.8 for identifying conditions for TSCoEA to select parents on the solution concept of a game in STRICTNASH n ZEROSUM. The proof of Theorem 3.8 is then given afterwards.
Lemma B.10. Let G STRICTNASH ZEROSUM have payoff function f and solution con- cepr A x B. Suppose X S X and Y S y are such that X n A # @ and Y n B + 9. Then P(argmax,es Fxx minyey f(r E A) and P(argmax muinezz--(ez.)) E B) =
Proof. Let E XnA be arbitrary. Using that G E STRICTNASHIZZROSUM we have f(x"
<
f(*".1/ ./) for all y E B and yf $ B. In particular, there some y" B such that
min f(x", ,)) f(=" .y) yEY
(29)
Using again that G E STRICTNASH n ZEROSUM, we have
f(z,8") > f(z'8v")
for all r E A and x' $ A.
(30)
Thus, for any x' E X \ A,
min f(z' y) & f(z','11 8²) yEY
f(x", .y")
29
min f(=",
yEY
and hence we have P(argmaxx, EX mingEr (ax y) E A) = 1. The corresponding proof that P(argmaxyey (- E B) 1 is similar.
Proof of Theorem 3.8 We prove each of part of the theorem in turn.
DI: Let STRICTNASHIIZEEOSON and let A B be the solution concept for G. Let À E N and
E yd be arbitrary. Write = IP Al/A X and b = =|Q (QDBB) BlA. If y) ~ Sx then letting 21,...,IA Ih be independent uniform samples from P and y1.... Ve be independent uniform samples from Q we have (using Lemma B.10
PEX* and Q
PP E A) > P( n A + A tyI.....,... n B 0)
=1 - (1 (1- (1-(1-a)*)(1 (1-bb))))))
(1-
Similarly, Ply E B) (1 (1-
a)²). Let a: [0, 1|2 + and B [0, 1]2 - R be
given by a(a, b) = (1- )) 6) and B(a, (1 (1 - b)*)(( (1 (1 a)²). D1
now follows from Lemma 3.3 by verifying that
aEh.1] aaa 7/0) (la, (1- (1-0-))9(--1-13)
sup
which is confirmed by Proposition B.5
D2.1: Let G' E STRICTNASHI n ZEROSUM have payoff function f and solution concept A x B. Let us write
fx min min f(x y) =EA B
fy: max max f( v)- yEB Z
(31)
Note that if (x* v) A (J) ZEROSUM,
B) and (x, (X \ A) B, then because G STRICTNASH
f(x,1") f(=xx'')) f(*
Therefore, fx > fy.
Let X E N and P E x² and Q E y* be arbitrary. Write a = IP Al/A and b= 1Q B//X. Moreover, let (1 - a)d and (1 b) and note that by reordering the elements of P and Q if necessary, we may assume that P()) & A whenever E [r] and Q(k) & B whenever & E [s]. Given j [r] will write
[k [s] (IP().Q(K) > SxH1
Pj
27

---

and given & E [s] we will write
[) & fy}l
Note that +
, je(r] Py is the proportion of pairs (r, y) E (P) A) (Q) B) satisfying ((x 3 Sx.
and that E kE(e] Us is the proportion of pairs (I, v) E (P) A) x (Q B) satisfying (x. < fy.
Because fx > fy, these are disjoint sets, and hence
1 T Ps JELN
Σ
Σ
9k 1
(32)
S
kE[s]
If (x, w)- ~ Sx(P.Q then letting 21,22 be independent uniform samples from P and ,I....,, De be independent uniform samples from Q we have
P(x E A) P((1 AA 22 E A) P( A i1 AA
22 & A) P(1 E AA & A)
+ +P(( E A Φ1 $ AAA E A) P(r & A2 E A)
x2
= 2 a - a) (P(z E A 11 E AA 22 & A) + P(x E A 21 AA E A))
æ1 E A & A). = a² + 2a(1 - a) (p E A
Let Ej be the event 21 E AA D2 É A and let Eg be the event Vı.... Ul...... De & B. Because E₁ and Eg are independent events, we have PP EE Ei) P(Es) (1 b)$ and hence
P(x E
F1)
P(x E A
E1 F22) [P Fn) PPo A F2) P(222 F1)
P(x E A
E A F2) (1 - b) + P(EEAAAAA (1-(1-b)
Using Lemma
B.10
P(r E A E1 A Eg) P(# E x1 AA & AA (Vi....,, .66 n xB = 1.
Additionally,
P(x & A F1 A F2) = P(x A z1 AA & A AAvi.....57 .. $ B)
Pmmin f >
min f(z v.) 0 E AA $ AA yı, Ve $ B)
xE(1)
xE(!]
31
P(min ( yi) > fx æ E A & AA V.......ye
ye $ B)
iElé
P'minn f(22 vi) >> fx 2 $ AA VI........ we $ B) sE(t]
1
Σ
P(min f v:) > fx x2 = P() A Ui. .i.... ... U1 $ B) [E
jELr
1
Σ
Pmmi f(P(j). 91) > fx vy..... KE|!]
ye $ B)
7
jE(r)
Pj.
JElr
Combining these observations, we have
P(x E A) > a² + 2a(1 - a) [[1 - b)¹ (1 - $ + Pi) + - (1 - b))]
a² + 2a(1 a)(1 (1 - -).. ESEth Pi)
= a(a + 2(1 a)(1 - (1 - (1-b) 4 Pj))
= a(2 - a - 2(1 - a) 8)'. - py)
A similar argument for yields
P(y E B) > 6(2 b b- 2(1 - (111- a) 1 ExE(e) 9x).
28

---

Let {(ag, {o))) be the family of pairs of increasing functions a, [0. 1]2 + [0. 1] and
Ba [0, 1]2 + [0, 1] given by
b) = a-- -of-)))) bb)
(a, = b(2 b- 2(1-b)(1 b) a) o))..
now holds (in part due to such that
32 that for all populations P E X' and Q E yd there exists or E [0,
Pn A
Qn
P( E A) 3 do
X
À
[Pn A
QQn BI
P(y E B) > 8
A
holds whenever (x,y) y) Sx(P. Q). Thus, the result now follows from Lemma B.7 by using Proposition B.6 to establish that
1
sup sup aE(T. cE a (a, 7/a) (a.
sup aE(3.]] (2 a)(2 2(1 2(1-aa((1 -//a))//) 7/a)
D2.2 Let G₁ = (00,1)".0..))) )), where f is given by
if and = 0",
-1
if / 1st and 1
f(z,8) = 1
if x = 1 and + 1 otherwise.
label A= B (1"). Let A E N and P E X.,, Q yd be arbitrary. Write IP Al/A and b= Q n BI/X. If (z, ~ Sx(P, Q). then letting 21, 22 be independent uniform samples from P and 1/, 1/2 be independent uniform samples from Q, we have
P(x E A) P(, E AA 32 E A) 2a a² = =u(2 - a).
Additionally,
Plye BB= E BAg2 E B) +)+F(y E BAA $ BA f01 22) nA
+ & 82 E BA [2) n # #)
1/2 + 2b(1 - (1 - -11-)) 1(b + 2(1 b) - (1-
6(2 - 1012-2(1-2) 2(1-a)²(0 (1)
Using also the fact that S₁ is a 2-candidate selection operator, the prerequisites of Lemma 3.4 are now satisfied with (aa.b) = a(2 a), ([a, is covered in detail in the proof of Theorem 3.6 provided in Appendix B.5 D2.2 now follows by applying A1
b(2 2(1 - a)²(1 b) b), and K (this
B.8
Proof of Theorem 5.1
Proof of Theorem 5.1
Using that A is 7-stable on G. let 8 be a constant such that, for all
populations P E X and Q E yd satisfying (P x Q) ((x", " """)} > 7X2, it holds that
P|T dep (A;G) < 26 (Po, Qo) = (P, Q)] < 2662
(33)
Set a = [e26A] Given E N, let G, be the event that (x*,y") ) E Pt x Qr For i E N, let let us define the time interval
[aa] [ 1)a], so that [i| = a. Define
T: min (a + 13 U (t [a] G(--Datt holds).
From 9 have ET]. < T T()).
29

---

Let E, denote the event that (Iz, v1) = (z',y") for all but at most Ex values of E 4. By (33) the probability that Ge holds for all (i - 1)a + T x t & ia is at least (1 - 11---26, 2-26) Therefore, for all
populations P E x and Q E E
P(E, | (Pas Q(-11aa (P.Q)) PT, < ) 61-c ( 281)
e (1 e k [Tii) - E 26 > 1 1 8A, (34)
Let X1, X2.... be sequence of independent identically distributed random variables with
P(X; = a) = 2 6A
P(X; = ) - -1 - 2T(A) 62
For i E N, let Y; (1 E I G. does not not hold)/
Using 33 it holds for all i E N and
01.--. D1-1 E {0) U [a] that
PP(Y, E Ay
Y = y1 A. A Y = 11-1) 2T(e) -62
In particular, X lim sup - 1 k
Eie(y) X; and Y lim sup EiEWs Y,, then
X> Y
(35)
We now turn our attention to
g Writing
F max
f(z,8)
min f(r
(
(x.))Xx))
We first note that for any x E X and y E
((r,))) (I,,,V) & F(1 1(G)))
(36)
Thus for any T.
F T
F alT/a
max min T
ZEX' yEy
E((e, - f(o..0)) -f(.))))(((
<
T
Σ (1
((G))
& oF
T
Σ (1 (G.)
t=1
alT/al
aF
F
Σ
(1 (1- (G-1)
T
TTT/a|
[T/a]
aF
Yo
T
LTT/a]
i=1
and hence,
T -u(c..)) s(ee.)))))
limsup max min T-500 T ZEX
<
lim sup 10000
limsup
Σ
Y,
Ey.
(37)
K
1m1
Additionally, by the strong law of large numbers,
P(X < E[X1))= =
(38)
Next, note that there is constant e (depending F and 8) such that
F E E[
F F (2T(A)E 82 88 2T())) > T(A) 2F 62 1/a)
a
= T(()) 2F 8d - 1/1c201)) 3 T(A)e
(39)
We now have
PP
lim sup min
1
Σ
(f(x, vr) f(2(1)))
< T(()e-oc
P
Ey
F
y < T(A)e-oh
T ZE yEy
T-0
F x <
F
F P(X & B(x1))
PP
(())e cA
PP
X
[|x1]
Thus, Ais T(A)e cA Hannan consistent, as required.
30

---

C Experimental details
The runs used to produce the data represented in Figure 2 provisioned with 1344 CPU cores and 6TB of RAM and had a wall-clock time of 36 hours, resulting in maximum total provision of 48384 core- hours. A Python implementation of the experiment is publicly available at htttts://ggthmmee
were executed on an internal cluster
com/ aswanf wttpfffo/dd/ttttt////ooaa www.ablitttaaaalsiisssaaaa of coeas
We now provide complete definitions for the three problems considered in the empirical analysis of Section 4 As all three problems are zero-sum games use the same action spaces X' = =
-y= = {0. 1)
we then take fi f and f2 f). In all cases, the problems where instantiated with = 50. In the subsequent definitions
suffices in each case to specify the payoff function f for player
we write [x] for the number of 1-bits {0, 1)" (that is, |x| = Eie x(i)).
C.1 Bilinear
Let a, b E (0,....n], Given x {0, 1)", write LO(z) for the length of a maximal prefix of 1-bits of a and write TZ(x) for the length of a maximal suffix of 0-bits of æ. Formally,
LO(x) = - x(i),
iE[n] jEB
TZ(x) = Σ
II (1 x(n - 1)).
KE [m] jEja
Additionally, write (xx) = (0)x) + TZ(x) and note that & h(x) & n. The payoff function for
Bilinear is now given follows.
2 + h(x)) - h(y)
| = a and
ly * b. lyv = b,
f(x,8) v)
+ h(x)) h(y)
if | * a and otherwise.
(|x) al(l b) h(z) - h(y)
The strict Nash equilibrium is given by x²' 1-0R~a and y² = 1m Note that this payoff function is isomorphic to the problem definitions appearing in 40 31,, except the addition of the = (to ensure the Nash equilibrium is strict) and h(z) h(y) (to ensure that the Nash equilibrium is unique). All runs were exccuted using problem parameters a 35 and b = 10.
C.2 PlantedBilinear
PlantedBil lnner is randomly instantiated zero-sum game. First, and v sampled uniformly random from {0, 1)", a random n matrix instantiated by generating each entry uniformly at random from [0, 1]. The payoff function is then defined as
E
if u and y / v, if x マ and v, otherwise.
f(r,y)
-
2T Ay xT Av uT
Where E is chosen to satisfy < 1(2x Ay-x' 1(2xTAy-12 Au-u- Au-u A T and * bHl (we used min_ float from Ocaml's native Float module). The strict Nash equilibrium given by x² and y w. PlantedBil inear generalises Bilinear-type problem to forms more akin to that provided in 63 All runs were executed using the same random seed to generate u, v, and A, so that all problem instances were identical.
31

---

1/ n. C.3 MBJR_2024
Introduced in 47 using the function
adopt the zero-sum sum formulation of after projecting {0, 1]" onto (0. , n
|. Let Amin: A1 E R. The payoff function for MBJR_2024 is given as follows.
if and n,
24 2 min
if n and |g|
1,
-2mmin min
if [ n and [ 72
2
if [
|vl < 1, and
f(z v)
- 1
if
and [
0
if
y/
72
if
[yl
[x] 12,
-1
if [
The strict Nash equilibrium is given by x² = y" = =1 Our runs were executed using Amin 0.001 and A 0.1.
32

---

NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and introduction claim the development of theoretical technique for deriving upper and lower bounds on the threshold between stability and instability for population-based CoEAs with unary variation, well number of applications of this tool to various algorithms and problem classes, comparison to empirical analysis, and proven link to regret analysis. The promised tool is developed in Section [3.1] (with corresponding proofs in Appendices [B.3] and B.4). the subsequent applications are given in Section 3.2 (with corresponding proof's throughout Appendix B), the empirical analysis is provided in Section 4 and the corresponding regret analysis is covered in Section (with corresponding proof Appendix B.8
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
It is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
The main limitations arise from the gaps between the upper and lower bounds on stability, our rigorous understand of what extent such gaps are necessary, and the fact that only one class of solution concept (strict Nash equilibrium) is considered in detail. These are discussed Section
Justification:
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-ter system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they seale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
33

---

While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification:
All results have all assumptions stated precisely with respect to the definitions
set out in Section [ All proof's complete and contained in Appendix B Results upon which our proofs are dependent are stated and referenced Appendix B.
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: The algorithms examined empirically in Section 4 are simple and plainly stated (alonggsiede in Algorithms (2 and (alongside Algorithm Methodological aspects including mutation operator, population size, number of runs, and the procedure followed to generate Figure 2 are all provided in Section 4 and complete descriptions of the problem instances can be found Appendix C
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
34

---

(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g.. a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g.. to registered users), but it should possible for other researchers have some path reproducing verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: Python code that reproduces the empirical analysis in the paper is publicly available htttts://giiiie com/ htwp/////////ttttaalllaaaaaaaaaa -tt.-aaallyyiss---ooees- coeas
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
http:/bbbic/guiies//eeeeeeee /
/mippscc/pput wttpcccppppppp.cccccoooooooppcpp
CCoeee/mddSSubieeee itttssummmssiooPoooooo wssionooiccyyy for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification: Full specification of mutation operator, population size, number of runs, and statistical aspects of the procedure followed to generate Figure 2 are provided in Section
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, appendix, or as supplemental material.
35

---

7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [No]
Justification: As all of the claims made in this paper are theoretical, the aim of the empirical analysis is to provide broad intuition about behaviour in circumstances where gaps between theoretical bounds make no specific prediction, rather than to scientifically test a claim or hypothesis. As the contributions of the paper were claims supported by rigorous proof rather than experimental data, statistical tests were not appropriate.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative етror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: The relevant details for the computational resources used to produce Figure are provided in Appendix C Cadd signposted in the paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification: The research has been conducted fully in accordance with the NeurlPS Code of Ethics.
36

---

Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- cration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive socictal impacts and negative socictal impacts of the work performed?
Answer: [Yes]
Justification: In Section I we consider how theoretical guarantees instill greater con- fidence in the output of CoEAs. We also explain how the quantitive nature the main theoretical contribution makes it valuable tool for practitioners applying such algorithms. No foreseeable negative societal impacts arise beyond anything applicable to all theoretical works advancing understanding of CoEAs.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative socictal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: This paper poses such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided relcasing unsafe images.
37

---

We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: This paper does not existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g.. website). the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswi thcode. cow datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
This paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
38

---

According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/teview based on the requirements of your country institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does involve LLMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to L.MM policy http:p/s/aaarrpspscc///ofeeeeees for what should or should not be described.
39


Reviews:
[{"review_id": "0Z7M8VT8nc", "reviewer": "Reviewer_RsCt", "summary": "This paper investigates the theoretical guarantees of coevolutionary algorithms (CoEAs) for identifying Nash equilibria (NE) in games. The authors introduce the concept of stability for CoEAs, defined as an algorithm’s ability to retain a discovered Nash equilibrium over a long period with high probability, both increasing exponentially with population size. They derive theoretical bounds on the mutation strength under which different classes of CoEAs are guaranteed to be stable or unstable. These theoretical results are also validated empirically. Finally, by combining the stability assumption with a runtime analysis, a bound on the expected time to find a NE for the first time, the authors demonstrate that CoEAs applied to zero-sum games with a single pure NE are ε-Hannan consistent, meaning that the time-averaged regret converges almost surely to a value below ε.", "questions": "How exactly could practitioners make use of the derived bounds on the mutation strength for the algorithm stability besides just avoiding unstable regions?\nWhat exactly is the class of games assumed in Theorem 5.1? Are those indeed only zero-sum games with just a single pure NE?", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\nThe paper is generally clearly written and easy to follow. In particular, the visualizations of the derived theoretical bounds with their empirical validation are helpful.\nThe authors introduce and prove a novel theory of stability for evolutionary algorithms, which traditionally lack strong theoretical guarantees.\nThe derived mutation strength bounds could be valuable for practitioners by helping them to avoid parameter settings that cause algorithmic instability.\n\nWeaknesses:\nThe notion of stability is not, by itself, particularly insightful, as it only provides a necessary condition for practical algorithm behavior. It remains unclear how mutation strength within the “stable” region affects other algorithmic properties, and thus how one should optimally select this parameter.\nDue to these limitations, the overall significance and practical impact of the theoretical results seem rather narrow.\nDefinition 2.1 of a game is somewhat confusing and unconventional, as it includes a definition of a solution concept as a simple subset of players’ actions without further clarification. \nThere appears to be a typo in Chapter 5, where the definition of y_t should use arg⁡min instead of arg⁡max.\nAn issue (and question) I have relates to Theorem (5.1). The way I understand this, it assumes pure Nash (SINGLETONSOLUTION). But this is a very pathological assumption, making many things trivial (e.g. computing Nash even in non-zero sum games becomes polynomial, etc). Am I missing something? Why is that case interesting?", "was_revised": true, "final_justification": "I apppreciate the authors response, happy to increase score from borderline reject to borderline accept", "rebuttal": "Many thanks for your helpful review. We appreciate your recognition of the novelty of our analysis in an area which traditionally lacks theoretical guarantees, and that our results could provide valuable guidance for practitioners.\n\n**Insight from stability.** While necessary conditions cannot provide a complete description of algorithm behaviour, it is absolutely critical for practitioners to ensure these such conditions are met to stand any chance of practical behaviour. For standard bitwise mutation with rate $\\chi$ (see lines 276-277), it is common in evolutionary computing to recommend a mutation rate of $\\chi=1$; however, this corresponds to a $q$-value of $(1-1/n)^{2n}\\approx e^{-2}\\approx0.135$. As our results indicate this does not meet the necessary condition for stability for many CoEAs (see Figure 1), the guidelines provided can be an essential revelation. We acknowledge this paper alone cannot paint a full picture of how to parameterise mutation strength, and that its insights must be combined with knowledge about impact on other algorithmic properties. However, this is a deep and thoroughly studied topic where no single paper can provide a complete description, and very few provide guidance as rigorous and general as that provided here.\n\n**Theorem 5.1 is highly non-trivial due to the possibly overwhelming number of pure strategies to query.** Theorem 5.1 is marginally more general than your understanding (it could apply also to other solution concepts of cardinality 1 that are not Nash equilibrium); however, because it needs to be combined with a stability result for a meaningful conclusion, and also because the stability results presented in Section 3 concern Nash, then your understanding of the class of games is correct within the bounds of this paper (we only stated it with more generality to maximise future applicability). The thing missing is that computing a pure Nash is only polynomial if the number pure strategies is also polynomial, whereas a motivating assumption for CoEAs is that the pure strategy space is too large to practically compare all strategies (for example, if strategies bitstrings of length n), and thus standard approaches fail. This is the reason why the setting considered is highly non-trivial. This is explained in the introduction (see lines 17-27), however as it is not repeated explicitly elsewhere, we agree that we should do more to emphasise this aspect.\n\nWe also acknowledge the unconventionality present in Definition 2.1. Like the statement of Theorem 5.1, the decision to formulate the definition this way was taken to prioritise generality, however we see that this has negatively impacted understandability. We will modify the corresponding section to reduce confusion. Thank you also for bringing the typo in Section 5 to our attention."}, {"review_id": "OEf2ySnoq8", "reviewer": "Reviewer_mYrY", "summary": "This paper addresses the challenge of finding and retaining Nash equilibria in games with large action spaces, where exhaustive search methods become infeasible. While coevolutionary algorithms (CoEAs) offer practical randomized search heuristics, they lack established theoretical guarantees, particularly regarding stability after discovering a Nash equilibrium. The authors develop a theoretical framework to derive necessary and sufficient conditions under which a CoEA remains stable (retaining a Nash equilibrium once found). The paper quantifies the relationship between algorithm stability and mutation strength, revealing that excessive mutation prevents stability, while overly weak mutation hinders exploration. Empirical results validate the theoretical predictions. Furthermore, the authors extend their framework to provide regret bounds for CoEAs, drawing parallels to classical regret guarantees for learning algorithms in small action spaces.", "questions": "- How can we model any real world problem with the framework of CoEA? Can we find a more compelling setting for Neurips audiences such as AI safety, multi-agent interactions or computational social science?\n- How does this problem related to the mean field games and the result and analysis there?\n- How should we understand the relationship between CoEA and standard multi-agent learning problem under simple normal-form games? Are any of the insight obtained from CoEA useful there?", "limitations": "yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Strength \n\n- The paper did a reasonably good job educating me on the concepts of CoEA, mutation and selection. There seems to be many new ideas in the analysis of this problem, though I am not familiar with the prior work along this line. \n- The setting of this problem is well-motivated for general dynamics evolved among a population. The paper also provides some experiments on problems motivated from some real-world applications. The heat map plots in Figure 2 are very well designed.\n-  The paper clearly acknowledged the limitations of their results.\n\nWeakness\n\n- I am not sure if the problems studied by this paper fits into the theme of Neurips, or its result might be interesting to a general audience at this conference. \n- Perhaps a notation table can help us quickly parse through your technical results.", "was_revised": true, "final_justification": "The paper is well-written yet I still have some concerns on whether the problems studied by this paper fits into the theme of NeurIPS. Hence, I keep my score as a borderline acceptance.", "rebuttal": "Many thanks for your helpful review – your comments on how to better position the research for NeurIPS audiences is very useful. We are glad you found the paper to be informative and well-motivated, and its results well presented.\n\n**Coevolution and real-world problems.** There are plenty of real-world problems modelled within the framework of coevolution, including but not at all limited to\n - GANs [A]\n - Cybersecurity and defence [B,C]\n - Detecting tax evasion [D]\n - Coevolutionary training for game players [E,F,G]\n\nMany of these have strong connections to topics you mentioned. As pointed out by reviewer VykP, the paper can be improved with the inclusion of a section on related work. We believe highlighting these practical applications in a new related work section will help provide a more compelling setting for NeurIPS audiences.\n\n**Mean field game theory.** Coevolution typically focuses on two-player games modelled either using two populations (as in this paper) or a single population representing both players. In principle, the many-player single-population setting of mean-field games can also fit the broader scope of coevolution, however there is less precedent for this. We understand mean-field game theory is often analysed as a continuous rather than as a discrete system, and so overlaps with evolutionary game theory (which is adjacent yet related to CoEAs) where “infinite population and continuous time” is a common assumption. Such assumptions would in fact make a lot of our theoretical analysis far easier, however we generally opt to maintain a focus on discrete-time finite population stochastic processes, so that theory matches actual algorithms as closely as possible.\n\n**Multi-agent learning problem**. CoEAs could be interpreted as a special form of multi-agent learning. The mathematical techniques we apply, in particular drift analysis, are highly general. We expect that drift analysis and similar techniques can be applied to study classical multi-agent learning. It is an open problem to explore the similarities and differences between these areas more in detail.\n\n[A] Costa, V., Lourenço, N. and Machado, P., 2019, March. Coevolution of generative adversarial networks. In International Conference on the Applications of Evolutionary Computation (Part of EvoStar) (pp. 473-487). Cham: Springer International Publishing.\n\n[B] Matthew J. Turner, Erik Hemberg, and Una-May O'Reilly. 2022. Analyzing multi-agent reinforcement learning and coevolution in cybersecurity. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO '22). Association for Computing Machinery, New York, NY, USA, 1290–1298.\n\n[C] Zychowski, A. & Mańdziuk, J., 2023. Coevolution of players strategies in security games. Journal of Computational Science\n\n[D] Erik Hemberg, Jacob Rosen, Geoff Warner, Sanith Wijesinghe, and Una-May O'reilly. 2016. Detecting tax evasion: a co-evolutionary approach. Artif. Intell. Law 24, 2 (June      2016), 149–182.\n\n[E] Vinyals, O., Babuschkin, I., Czarnecki, W.M. et al. Grandmaster level in StarCraft II using multi-agent reinforcement learning. Nature 575, 350–354 (2019).\n\n[F] Arulkumaran, K. et al. (2019) ‘AlphaStar: An Evolutionary Computation Perspective’, in Proceedings of the 2019 Genetic and Evolutionary Computation Conference Companion (GECCO ’19 Companion), ACM.\n\n[G] Estelle Chigot and Dennis G. Wilson. 2022. Coevolution of neural networks for agents and environments. In Proceedings of the Genetic and Evolutionary Computation Conference Companion (GECCO '22). Association for Computing Machinery, New York, NY, USA, 2306–2309."}, {"review_id": "AUrzGvz3jA", "reviewer": "Reviewer_VykP", "summary": "The authors study the stability of (two-player) co-evolutionary algorithms, with a particular focus on Bitstring Games (where actions are tuples with binary elements) and games with unique NE. However, some of the results apply outside of these assumptions. The goal of the paper is to establish \\gamma-stability which, informally, states that NE solutions persist in the population for a long time with high probability, given that they were present in the population to begin with. The authors then show negative results on stability for several classes of games, and finally establish regret bounds for zero-sum games.", "questions": "1. Line 541:  I am missing the final step of this proof, could you please explain why the union bound yields the result?\n\n2. Is there a method to estimate $\\delta$ for a given problem class empirically?\n\n3. How do the authors think the results hold for elitist population-based CoEAs (i.e. in which the top candidates are selected and mutated, whilst the remaining are removed from the population)?", "limitations": "Yes (This section is exceptionally written)", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 4, "originality": 3, "strengths_and_weaknesses": "Strengths: \n1. The paper provides novel contributions to the community regarding the behaviour of derivative-free approaches to solving games. In particular, the formulation and result of \\gamma-stability is novel, as is the regret analysis. \n2. For the most part, the paper is well written, with definitions clearly given, alongside informal statements to aid in understanding\n3. The authors also show that their theoretical results are satisfied in practice, in particular showing their necessary and sufficient conditions for stability, on various choices of \\gamma and mutation rate q. \n4. Whilst the majority of negative results are defined for bitstring games with unique NE, the sufficient condition for stability holds for generic games and Co-evolutionary algorithms.\n5. The results are clearly of use to practitioners in terms of setting the hyperparameters of their mutation method to encourage stability of the learned solutions. \n\nWeaknesses:\n1.  The authors have not sufficiently motivated bit-string games. Whilst it is convenient to design examples (as the authors do for their experiments) they do not discuss the domains in which bitstring games are of interest. \n2. There are a number of issues with notation. In particular:\n     (a) $\\mathcal{X}^\\lambda$ is not defined. By inferring, one realises that it is a subset of $\\mathcal{X}$ with cardinality $\\lambda$. However, without defining it as a countable subset of $\\mathcal{X}$, this is merely inference.\n    (b) The dual use of Q as a subset of $\\mathcal{Y}$ and as a subset of $[0, 1]$ in Defn 2.2 is extremely confusing. Please change this.\n    (c) The selection operator $S$ should be defined implicitly with the cardinality of the set (i.e. write it as $S_\\lambda$). Otherwise its domain varies for different choices of $\\lambda$. \n3. Related to (1), the authors have not provided justification for MJBR or PlantedBilinear as experiments. I would imagine that the reason these were chosen was that their NE is known and so can be injected into the initial population. Even saying this is fine, but it ought to be stated.\n4. Graphs are poorly displayed - fonts are almost unreadable and a legend is not provided. \n5. The proof structure in the Appendix is not clear. Please provide more detail than \"Here is McDiarmid's inequality\". In particular, it would be useful to know a-priori how and where the result will be used (in the proof of Lemma 3.3). \n___\n**Note**: The above criticisms do not have a bearing on the content on the paper, but on its exposition. What follows are more serious concerns.\n___\n5. There is no attempt to provide empirical evidence of the paper's results outside of the assumptions made, (e.g. games that are not Bitstrings). This would have strengthened the paper's contributions in presenting the formalism by which stability can be analysed. This is somewhat remedied by the extensive future work section. \n6. There is *no* related work section. As such, for someone who is not an expert in the field, it is impossible to place the work in the context of other works on co-evolutionary algorithms, or learning methods. The closest is the paragraph on line 40, which argues that theirs is the first work to study stability, rather than runtime analysis (hitting time of solution). However, without a related work section, it becomes impossible to assess the technical novelty of the work in relation to existing works. \n\n\nAdditional minor remarks:\n1. Typo on line 524: \"of pairs of...\"\n2. Line 465:  It would be clearer to say that, since $M_X(x)(x) < 1$, it follows that $M_X(x)(x^\\star) < 1$ rather than in reference to eq (10).\n3. Line 537: I think you mean changing $\\{ (x_j, y_j) \\}_{j \\in [\\lambda]}$ changes the value of $f$ by at most $2 \\lambda$, rather than changing any $(x_j, y_j)$.", "was_revised": true, "final_justification": "I believe that this work makes a strong advancement in the study of co-evolutionary algorithms and fits in well both with existing works on CoEAs as well as more general related work in Nash Equilibrium finding. Please see the Strengths section of my review. I had a few minor concerns regarding presentation as well as some major concerns on the exposition. Both have been addressed by the authors and I trust that they will make the changes that they have proposed. Therefore, due to the novelty of the work and its significance to the multi-agent learning community, I strongly believe that this work should be accepted.", "rebuttal": "Thank you for your detailed and helpful review. We appreciate that you find our results to be novel, well-written, empirically supported, and useful for practitioners.\n\nThe more minor weaknesses you have pointed out are very useful for us, and we will take steps to address them in revisions. To say a few words about a few of them:\n - We always take population size $\\lambda$ to be finite, and so $\\mathcal{X}^\\lambda$ is a tuple over $\\mathcal{X}$ of length $\\lambda$, as is standard. Equivalently, this is indeed a multiset of cardinality $\\lambda$, hence our use of set notation in relation to it (this is pointed out on lines 64-66). We will take care to define $\\mathcal{X}^\\lambda$ more clearly.\n - The reason the games were chosen is indeed because the NE is known, and we will state this.\n\nOn the more serious concerns:\n\n**Extensions beyond bitstrings.** Our negative results can just as easily be proven in any domain. However, it is contingent on certain assumptions that must be made about the mutation operator being used. For example, one needs to rule out the possibility or mutation operator that always generates optimal strategies with high probability, else a meaningful negative result is not possible. Bitstrings have a well-established notion of unbiased operators, which allows our negative results to apply for all operators deemed natural or “sensible” for the domain, hence motivating our focus (in addition to a restriction to bitstrings being standard for theory of evolutionary computing). We could have shown negative results or gathered empirical evidence for other domains, however that would rely on what we deem to be a sensible mutation operator for the domain, and this is a more subjective view.\n\nOne way we can extend the scope of negative results beyond bitstrings is to include a version of Lemma 3.4 for arbitrary domains which includes an added assumption bounding above the probability of mutating into the solution concept. Due to space constraints this will need to be in the appendix, but we will ensure it is discussed in the main text. The proof should not be much longer than the two-page proof of Lemma 3.4, and indeed Lemma 3.4 could be a special case of such a result, and so this will not add much to the amount of mathematical material in the paper. Let us know if this would adequately address this concern. We are also happy to add similar empirical analysis for one or two choices of non-bitstring domains, with the understanding we would need to make a potentially subjective choice of mutation operator.\n\n**Related work.** We accept the decision to forego a dedicated related work section due to space limitations was a poor one. We propose making space for a related work section in the main text either by transferring some of the lengthier negative results (i.e. A2 and those derived from it) to the appendix, or stating abridged summaries of such results in the main text with full details given in the appendix. In the new related work section we will contextualise our work by covering the following.\n - There is a well-established range of theoretical analysis for evolutionary algorithms (EAs) (see e.g. survey [H]), and also demand to extend such analysis to CoEAs (see [I]).\n - The first theoretical analysis for competitive CoEAs considered the runtime of PDCoEA on Bilinear [J]. All subsequent theoretical work on CoEAs either considers how runtime is impacted by algorithmic features [K,L,M] or considers runtime in new problem classes [N,O].\n - There are also theoretical and empirical analyses of how mutation thresholds relate to stability for classical EAs [P,Q].\n - Challenges relating to the successful application of CoEAs are covered in, e.g., [R]\n - We will also include an overview of uses of CoEAs for practical applications, as suggested in our reply to Reviewer mYrY.\n\n**Answers to questions.**\n\n1. The union bound is over the first $e^{\\frac{1}{4}\\epsilon^2\\lambda}$ time steps. Specifically, for a given $\\tau$, if the event $T_\\text{dep}^\\gamma(\\mathcal{A};G)$ occurs, then there must exist some $t$ with $0\\leqslant t<\\tau$ such that $X_t\\geqslant\\gamma\\lambda^2$ and $X_{t+1}\\leqslant\\gamma\\lambda^2$ (recall here that $X_t=|(P_t\\times Q_t)\\cap S|$, and so this fits Definition 3.1). Therefore, we can write the relation of events\n$$ (T_\\text{dep}(\\mathcal{A};G)\\leqslant\\tau\\)\\subseteq\\cup_{t<\\tau}(X_t\\geqslant\\gamma\\lambda^2\\wedge X_{t+1}\\leqslant\\gamma\\lambda^2). $$\nIn addition, recalling our previous calculations apply for $c\\geqslant\\gamma$, it follows from the upper bound just above line 540 that for every $t$ we have $\\mathbb{P}(X_{t+1}\\leqslant\\gamma\\lambda^2\\wedge X_t\\geqslant c\\lambda^2)\\leqslant\\mathbb{P}(X_{t+1}\\leqslant\\gamma\\lambda^2\\mid X_t\\geqslant c\\lambda^2)\\leqslant e^{-\\frac{1}{2}\\epsilon^2\\lambda}$. Therefore the union bound gives $\\mathbb{P}(T_\\text{dep}(\\mathcal{A};G)\\leqslant\\tau)\\leqslant\\tau\\cdot e^{-\\frac{1}{2}\\epsilon^2\\lambda}$. Taking $\\tau=e^{\\frac{1}{4}\\epsilon^2\\lambda}$ gives the result. We will add these broken down steps to the paper to improve readability.\n\n2. The required value of \\delta can depend on the value of q arising from the choice of mutation operator. A method for estimating the value could be to follow the proof of Lemma 3.3, where we take $\\delta=\\frac{1}{4}\\epsilon^2$, where $\\epsilon$ is sufficiently small for (13) to hold (which will depend on the problem class and mutation operator). We note that this may not be the best possible value of $\\delta$ for a given problem or problem class.\n\n3. Undertaking the same analysis for elitist population-based CoEAs will naturally reveal them to have far stronger stability properties. There are potential wider drawbacks to using elitist selections that arise from a lack of population diversity and premature convergence to local optima, hence potential stability benefits do not necessarily make them unequivocally preferable. We focused on non-elitist CoEAs as they constitute a far less trivial setting for stability analysis. In addition to these considerations, the question of what constitutes “top candidates” for coevolution is not trivial due to intransitive payoff structures.\n\n[H] Doerr, B. and Neumann, F., 2021. A survey on recent progress in the theory of evolutionary algorithms for discrete optimization. ACM Transactions on Evolutionary Learning and Optimization, 1(4), pp.1-43.\n\n[I] Elena Popovici, Anthony Bucci, R. Paul Wiegand, and Edwin D. De Jong. 2012. Coevolutionary Principles. Springer Berlin Heidelberg, Berlin, Heidelberg, 987–1033.\n\n[J] Per Kristian Lehre. 2022. Runtime analysis of competitive co-evolutionary algorithms for maximin optimisation of a bilinear function. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO ’22).\n\n[K] M. A. Hevia Fajardo, P. K. Lehre, and S. Lin. Runtime analysis of a co-evolutionary algorithm: Overcoming negative drift in maximin-optimisation. In Proceedings of the 17th Conference on Foundations of Genetic Algorithms, FOGA ’23, page 73–83, 2023.\n\n[L] M. A. Hevia Fajardo and P. K. Lehre. How fitness aggregation methods affect the performance of competitive CoEAs on bilinear problems. In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO ’23, page 1593–1601, 2023\n\n[M] M. A. Hevia Fajardo and P. K. Lehre. Ranking diversity benefits coevolutionary algorithms on an intransitive game. In Parallel Problem Solving from Nature – PPSN XVIII, pages 213–229, 2024\n\n[N] Per Kristian Lehre and Shishen Lin. 2024. Overcoming Binary Adversarial Optimisation with Competitive Coevolution. In Parallel Problem Solving from Nature – PPSN XVIII: 18th International Conference, PPSN 2024\n\n[O] Alistair Benford and Per Kristian Lehre. 2025. A General Upper Bound for the Runtime of a Coevolutionary Algorithm on Impartial Combinatorial Games. Proceedings of the Genetic and Evolutionary Computation Conference. Association for Computing Machinery, New York, NY, USA, 1594–1603.\n\n[P] Gabriela Ochoa; Error Thresholds in Genetic Algorithms. Evol Comput 2006; 14 (2): 157–182\n\n[Q] Lehre, P.K. (2010). Negative Drift in Populations. In: Schaefer, R., Cotta, C., Kołodziej, J., Rudolph, G. (eds) Parallel Problem Solving from Nature, PPSN XI. PPSN 2010. Lecture Notes in Computer Science, vol 6238. Springer, Berlin, Heidelberg.\n\n[R] Popovici, E., Bucci, A., Wiegand, R.P., De Jong, E.D. (2012). Coevolutionary Principles. In: Rozenberg, G., Bäck, T., Kok, J.N. (eds) Handbook of Natural Computing. Springer, Berlin, Heidelberg."}, {"review_id": "aHvYI5sZcb", "reviewer": "Reviewer_SkGQ", "summary": "In this paper, the authors provide a thorough theoretical analysis of the bounds of the coevolutionary algorithms (CoEAs), which specify the necessary and sufficient conditions for a CoEA to be stable. Besides, the authors also provide bounds on regret based on the obtained results. Empirical studies also confirm the theoretical guarantees obtained in the paper.", "questions": "Will the authors release the code?", "limitations": "The authors have adequately addressed the limitations of the paper.", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The motivation of the paper is clear and reasonable. The theoretical results in the paper could have important implications in guiding the design of CoEAs for finding the Nash equilibrium stably. The paper is well-written, and the results are well-organized.\n\nI am not an expert in theory, so I only check some parts of the theoretical analysis. From my sense, I did not find any significant weakness, and I would like to see more comments from other reviewers.", "was_revised": true, "final_justification": "After reading the authors' responses to the other reviewers' comments, I think the authors have addressed some of the concerns, and I will maintain my positive score. Good luck.", "rebuttal": "Many thanks for your review. We are pleased that you found our results to be important, well-written, and well-organised.\n\nThe question of whether we release the code is covered in Question 5 of the NeurIPS paper checklist. You may have seen already and simply be asking now as a follow up, but we will restate here for convenience. The codebase used is part of a large software framework which we cannot release presently. However, as the algorithms, games, and methodology used to produce Figure 2 are all reasonably simple, in the event that the paper is accepted we are happy to provide a dedicated script to reproduce the figure."}]

Author rebuttal:

Meta-review: The paper provides novel stability conditions for coevolutionary algorithms (CoEAs) retaining Nash equilibria in large action spaces, with regret bounds for zero-sum games. Reviewers highlight its strong advancement in CoEA theory, fitting well with Nash equilibrium research, and its practical guidance on mutation strength. Concerns about real-world motivation, fitness to the general audience of the conference, notation, and exposition were addressed in the authors’ rebuttal, with commitments to add a related work section and clarify definitions. Based on the above, I recommend acceptance as a poster for its significant contribution to multi-agent learning, with minor revisions for clarity.
Decision: Accept (poster)