Pairwise Dominance CoEA (PDCoEA)
Require: Min-max-objective function \(g:\{0,1\}^n\times\{0,1\}^n\rightarrow\mathbb{R}\).
Require: Population size \(\lambda\in\mathbb{N}\) and mutation rate \(\chi\in (0,n]\)
for \(i\in [\lambda]\) do
Sample \(P_0(i)\sim\unif(\{0,1\}^n)\)
Sample \(Q_0(i)\sim\unif(\{0,1\}^n)\)
end for
for \(t\in\mathbb{N}\) until termination criterion met do
for \(i\in[\lambda]\) do
Sample \((x_1,y_1)\sim \unif(P_t\times Q_t)\)
Sample \((x_2,y_2)\sim \unif(P_t\times Q_t)\)
if \((x_1,y_1)\succeq_g (x_2,y_2)\) then
\((x,y):= (x_1,y_1)\)
else \((x,y) := (x_2,y_2)\)
end if Obtain \(x'\) by flipping each bit in \(x\) with probability \(\chi/n\).
Obtain \(y'\) by flipping each bit in \(y\) with probability \(\chi/n\).
Set \(P_{t+1}(i):=x'\) and \(Q_{t+1}(i):=y'\).
end for end for
Dominance. Given \(g:\mathcal{X}\times\mathcal{Y}\rightarrow\mathbb{R}\) and two pairs
\((x_1,y_1),(x_2,y_2)\in\mathcal{X}\times\mathcal{Y}\), we say that \((x_1,y_1)\) dominates
\((x_2,y_2)\) wrt \(g\), denoted \((x_1,y_1)\succeq_g (x_2,y_2)\), if and only if
\[g(x_1,y_2) \geq g(x_1,y_1) \geq g(x_2,y_1).\]
Bilinear. For \(\alpha,\beta\in[0,1]\),
\[\bilinear(x,y) := \|y\|(\|x\|-\beta n)-\alpha n \|x\|,\]
where \(\|z\|:=\sum_{i=1}^n z_i\). The plot shows \(\bilinear/n^2\), and the
red ring marks \(\|x\|=\beta n\), \(\|y\|=\alpha n\), where \(\nabla g=0\).
Diagonal [Lehre and Lin 2025]. Given \(n\in\mathbb{N}\), \(\mathcal{X}=\mathcal{Y}=\{0,1\}^n\),
the payoff function \(\diagonal:\mathcal{X}\times\mathcal{Y}\rightarrow\{-1,1\}\) is
\[\diagonal(x,y) := \begin{cases} 1 & |y|_1\leq |x|_1 \\ -1 & \text{otherwise}\end{cases}.\]
\((x^*,y^*)=(1^n,1^n)\) is the unique maximin optimum (red ring).
The plot uses eclib's general_diagonal_test: payoff 1 if
\(\|y\|\leq c\|x\|+\alpha n\) with \(c=(1-\alpha)/(1-\beta)\), and 0 otherwise. For
\(\alpha=\beta=0\) this is \(\diagonal\) with \(-1\) replaced by 0, which preserves every
comparison in \(\succeq_g\), so PDCoEA behaves identically.
P. K. Lehre and S. Lin. Towards Runtime Analysis of Population-Based
Co-evolutionary Algorithms on Sparse Binary Zero-Sum Game. In Proceedings of the 39th AAAI
Conference on Artificial Intelligence (AAAI) , 2025.
Copy
@inproceedings{lin2025aaai,
author = {Lehre, Per Kristian and Lin, Shishen},
title = {Towards Runtime Analysis of Population-Based Co-evolutionary Algorithms on Sparse Binary Zero-Sum Game},
booktitle = {Proceedings of the 39th AAAI Conference on Artificial Intelligence (AAAI)},
year = {2025},
address = {Philadelphia, Pennsylvania, USA},
}
Diagonal, three-valued. eclib's general_diagonal_test with
is_three_valued: with \(c=(1-\alpha)/(1-\beta)\), the predator payoff is 1 if
\(\|y\|\lt c\|x\|+\alpha n\), 0 if \(\|y\|= c\|x\|+\alpha n\), and \(-1\) otherwise.
The red ring marks \((1^n,1^n)\).
Maximin hill. With \(x=\|x\|/n\) and \(y=\|y\|/n\), \[g(x,y) := |\alpha-y|\,|\beta-x| - \bigl(|\beta-x| - |\alpha-y|\bigr).\] The red ring marks \(\|x\|=\beta n\), \(\|y\|=\alpha n\).
eclib discr_maximinhill (lib/coproblem.ml).
Double bilinear. With \(x=\|x\|/n\) and \(y=\|y\|/n\), \[g(x,y) := \begin{cases} \gamma\bigl(\alpha(1-x/\beta) + y(x/\beta-\tfrac12)\bigr) & x\lt \beta \\ \frac{(x-\beta)(\alpha-y)}{1-\beta} + \frac{y}{2} & \text{otherwise.}\end{cases}\] The optimum is \(y=\alpha\) and \(x=\beta/2\) if \(\gamma>1\), \(x=3\beta/2\) if \(\gamma\lt 1\), or both if \(\gamma=1\) (red rings, where inside the square).
eclib discr_double_bilinear (lib/coproblem.ml).
DGSZ 2022 f1. With \(\theta=2\|x\|/n-1\) and \(\omega=2\|y\|/n-1\), \[g := -4\Bigl(\theta^2-\bigl(\omega-(3\theta+\tfrac{\theta^3}{20})\bigr)^2-\tfrac{\omega^4}{10}\Bigr)e^{-(\theta^2+\omega^2)/100}.\] eclib defines no optimum or regret.
eclib dgsz2022_f1 (lib/coproblem.ml).
DGSZ 2022 f2. With \(\theta=2\|x\|/n-1\), \(\omega=2\|y\|/n-1\), and \(S(t)=0\) for \(t\le0\), \(3t^2-2t^3\) for \(0\lt t\le1\), 1 otherwise, \[g := \theta\omega+\frac{\omega^2}{2}-\frac{0.1}{2}\,S(\theta^2+\omega^2)\,\omega^2.\] The optimum is \(\theta=\omega=0\), i.e. \(\|x\|=\|y\|=n/2\) (red ring).
eclib dgsz2022_f2 (lib/coproblem.ml).
Monkey saddle. With \(x=\|x\|/n\) and \(y=\|y\|/n\), \[g(x,y) := (y-\alpha)^3-\theta\,(y-\alpha)(x-\beta)^2.\] eclib defines no optimum.
eclib monkey_saddle (lib/maximin_fitness.ml).
Handkerchief. With \(x=\|x\|/n\) and \(y=\|y\|/n\), \(a=6(y-\alpha)\) and \(b=6(x-\beta)\), \[g(x,y) := \frac{a^3}{3}+2h\,a^2+h\,a\,b^2-2b^2.\] eclib defines no optimum.
eclib handkerchief (lib/maximin_fitness.ml).
Mexican hat. With \(x=\|x\|/n\) and \(y=\|y\|/n\), and \(r=w\sqrt{(x-\beta)^2+(y-\alpha)^2}\), \[g(x,y) := \frac{\sin r}{r}.\] At \(r=0\) the plot uses the limit 1, where eclib gives NaN. eclib defines no optimum.
eclib mexican_hat (lib/maximin_fitness.ml).
Grimmer 2020. With \(x=\|x\|/n\) and \(y=\|y\|/n\), \(f(t)=(t-3)(t-1)(t+1)(t+3)\), \(u=4(x-1)\) and \(v=4(y-1)\), \[g(x,y) := f(v)-f(u)-A\,u\,v.\] eclib defines no optimum.
eclib grimmer2020 (lib/maximin_fitness.ml).
Quadratic diagonal. \[g(x,y) := \begin{cases}1 & \|y\|\le c\,(\|x\|-n/2)^2+n/2\\ 0 & \text{otherwise.}\end{cases}\] The regret is \(2n-\|x\|-\|y\|\), so the red ring marks \((1^n,1^n)\).
eclib diagonal_qd_test (lib/diagonal_test_quadratic.ml).
Sigmoid diagonal. \(g(x,y)=1\) if \(\|y\|\le b(\|x\|)\) and 0 otherwise, where \(b(0)=0\), \(b(n)=n\), and \[b(t) := \frac{n}{1+e^{-s(t-n/2)}}\quad\text{otherwise.}\] The red ring marks \((1^n,1^n)\).
eclib diagonal_sigmoid_test (lib/diagonal_test_sigmoid.ml).
Jump diagonal. \[g(x,y) := \begin{cases}1 & \|x\|=n\\ [\|y\|\le\|x\|] & \|x\|\le n-k\\ [\|y\|\le 2(n-k)-\|x\|] & \text{otherwise,}\end{cases}\] where \([\cdot]\) is 1 if the condition holds and 0 otherwise (naive_jump). The red ring marks \((1^n,1^n)\).
eclib jump_diagonal_test (lib/diagonal_test_jump.ml).
Trap diagonal. With \(h=n/2-b(\|x\|-n/2)\), \[g(x,y) := \begin{cases}1 & \|x\|\ge n-k \text{ and } \|y\|\le h\\ [\|y\|\ge h] & \|x\|>n/2 \text{ and } \|y\|\le\|x\|\\ 0 & \text{otherwise.}\end{cases}\] The red ring marks \((1^n,1^n)\).
eclib trap_diagonal_test (lib/diagonal_test_trap.ml).
Plateaus. \(g(x,y)=1\) if \(\|y\|\le p(\|x\|)\) and 0 otherwise, where \[p(t) := \begin{cases}\frac{n}{n-2d}\,t & t\lt n/2-d\\ n/2 & t\lt n/2+d\\ \frac{n}{n-2d}(t-n)+n & \text{otherwise.}\end{cases}\] eclib defines no regret; the red ring marks \((1^n,1^n)\).
eclib plateaus_test (lib/plateaus_test.ml).
Cantor. \(g(x,y)=1\) if \(\|y\|\le n\,C_\gamma(\|x\|/n)\) and 0 otherwise, with the Cantor function to depth \(\gamma\): \(C_0(t)=t\) and \[C_m(t) := \begin{cases}C_{m-1}(3t)/2 & t\lt 1/3\\ 1/2 & t\lt 2/3\\ 1/2+C_{m-1}(3t-2)/2 & \text{otherwise.}\end{cases}\] eclib defines no regret; the red ring marks \((1^n,1^n)\).
eclib cantor_test (lib/cantor_test.ml).
Triangle. With \(f_1(t)=\frac{\beta-1}{\alpha}t+n\), \(f_2(t)=\frac{\beta-1}{\alpha-1}(t-n)+n\), \(f_3(t)=\frac{\beta}{\alpha-1}(t-n)\) and \(f_4(t)=\frac{\beta}{\alpha}t\), \(g(x,y)=1\) if \(\|y\|\ge\max(f_1,f_2)(\|x\|)\) or \(\|y\|\le\min(f_3,f_4)(\|x\|)\), and 0 otherwise. The red ring marks the optimum \((\alpha n,\beta n)\).
eclib triangle_test (lib/triangle_test.ml).
MBJR 2024. \[g(x,y) := \begin{cases}2\delta_{\min} & \|x\|=n,\ \|y\|=n-1\\ 2\delta_1 & \|x\|=n,\ \|y\|\lt n-1\\ -2\delta_{\min} & \|y\|=n,\ \|x\|=n-1\\ -2\delta_1 & \|y\|=n,\ \|x\|\lt n-1\\ \operatorname{sign}(\|x\|-\|y\|) & \text{otherwise.}\end{cases}\] The red ring marks the optimum \((1^n,1^n)\).
eclib mbjr_2024 (lib/coproblem.ml).
Initialisation is uniform as in lines 1–4, or with a fixed number of one-bits
(Init controls).
P. K. Lehre. Runtime Analysis of Competitive Co-evolutionary Algorithms for
Maximin Optimisation of a Bilinear Function. Algorithmica 86(7):2352–2392, 2024.
doi:10.1007/s00453-024-01218-3
PDF
Copy
@article{lehre_bilinear_algorithmica,
title = {Runtime {Analysis} of {Competitive} {Co}-evolutionary {Algorithms} for {Maximin} {Optimisation} of a {Bilinear} {Function}},
author = {Lehre, Per Kristian},
journal = {Algorithmica},
volume = {86},
number = {7},
pages = {2352--2392},
month = jul,
year = {2024},
issn = {1432-0541},
doi = {10.1007/s00453-024-01218-3},
url = {https://doi.org/10.1007/s00453-024-01218-3},
}