On Sex, Evolution, and the Multiplicative Weights Update Algorithm

Reshef Meir; David Parkes

cs.LGFeb 17, 2015

On Sex, Evolution, and the Multiplicative Weights Update Algorithm

Authors: Reshef Meir, David Parkes

Organizations: Harvard University

Abstract

We consider a recent innovative theory by Chastain et al. on the role of sex in evolution [PNAS'14]. In short, the theory suggests that the evolutionary process of gene recombination implements the celebrated multiplicative weights updates algorithm (MWUA). They prove that the population dynamics induced by sexual reproduction can be precisely modeled by genes that use MWUA as their learning strategy in a particular coordination game. The result holds in the environments of weak selection, under the assumption that the population frequencies remain a product distribution. We revisit the theory, eliminating both the requirement of weak selection and any assumption on the distribution of the population. Removing the assumption of product distributions is crucial, since as we show, this assumption is inconsistent with the population dynamics. We show that the marginal allele distributions induced by the population dynamics precisely match the marginals induced by a multiplicative weights update algorithm in this general setting, thereby affirming and substantially generalizing these earlier results. We further revise the implications for convergence and utility or fitness guarantees in coordination games. In contrast to the claim of Chastain et al.[PNAS'14], we conclude that the sexual evolutionary dynamics does not entail any property of the population distribution, beyond those already implied by convergence.

Figures & tables

$w_{ij}$	$b_{1}$	$b_{2}$	$p^{0}_{ij}$	$b_{1}$	$b_{2}$	$\mathbf{y}^{0}$	$p^{1}_{ij}$	$b_{1}$	$b_{2}$	$\mathbf{y}^{0}$
$a_{1}$	1	0.5	$a_{1}$	0.1	0.15	0.25	$a_{1}$	0.094	0.080	0.174
$a_{2}$	1.5	1.2	$a_{2}$	0.1	0.15	0.25	$a_{2}$	0.158	0.170	0.328
$a_{3}$	1.3	0.8	$a_{3}$	0.2	0.3	0.5	$a_{3}$	0.255	0.242	0.497
			$\mathbf{x}^{0}$	0.4	0.6		$\mathbf{x}^{1}$	0.5075	0.4925

Table 1: An example of a 2-locus haploid fitness matrix, with

n=3,m=2

. There are 6 allele combinations, or genotypes. On the left we give the fitness of each combination

\left\langle a_{i},b_{j}\right\rangle

. In the middle, we provide an initial population distribution, and on the right we provide the distribution after one update step of the SR dynamics, for

r=0.5

SR	$b_{1}$	$b_{2}$	$\mathbf{y}^{1}$	RS	$b_{1}$	$b_{2}$	$\mathbf{y}^{1}$
$a_{1}$	0.088	0.086	0.174	$a_{1}$	0.099	0.075	0.174
$a_{2}$	0.167	0.162	0.328	$a_{2}$	0.149	0.179	0.328
$a_{3}$	0.252	0.245	0.497	$a_{3}$	0.258	0.239	0.497
$\mathbf{x}^{1}$	0.507	0.493		$\mathbf{x}^{1}$	0.507	0.493

Table 2: Population frequencies

P^{1}=(p^{1}_{ij})_{ij}

, i.e. after one update step, for the simplified case of

r=1

(which is not a biologically valid). On the left, we provide frequencies when selection occurs before recombination, whereas on the right recombination precedes selection. The updated marginal frequencies of alleles are the same in both cases.

SR	$b_{1}$	$b_{2}$	$\mathbf{y}^{1}$	RS	$b_{1}$	$b_{2}$	$\mathbf{y}^{1}$
$a_{1}$	0.094	0.08	0.174	$a_{1}$	0.099	0.074	0.174
$a_{2}$	0.158	0.170	0.328	$a_{2}$	0.149	0.179	0.328
$a_{3}$	0.255	0.242	0.497	$a_{3}$	0.258	0.239	0.497
$\mathbf{x}^{1}$	0.507	0.493		$\mathbf{x}^{1}$	0.507	0.493

Table 3: Population frequencies

P^{1}

for

r=0.5

. Under RS we get the same frequencies as with

r=1

(and in fact any other value of

r

). This is because when

P^{0}

is a product distribution there is no effect of recombination under RS.

SR	$b_{1}$	$b_{2}$	$\mathbf{y}^{2}$	RS	$b_{1}$	$b_{2}$	$\mathbf{y}^{2}$
$a_{1}$	0.079	0.042	0.122	$a_{1}$	0.09	0.034	0.124
$a_{2}$	0.228	0.172	0.401	$a_{2}$	0.203	0.195	0.398
$a_{3}$	0.294	0.183	0.477	$a_{3}$	0.305	0.173	0.478
$\mathbf{x}^{2}$	0.602	0.398		$\mathbf{x}^{2}$	0.598	0.402

Table 4: Population frequencies

P^{2}

, i.e. after two update steps for

r=0.5

. The marginal distributions are no longer the same, since

P^{1}

under RS is not a product distribution.

Figure 1: On the left,

F(T)

is the fraction of instances that converge (reach

\max_{ij}p^{t}_{ij}>1-10^{-5}

) within at most

T

generations. On the right,

F(Q)

is the fraction of instances that converge to an equilibrium with quality

q

at most

Q

, where

q=\frac{\overline{w}^{t}-1}{\max_{ij}w_{ij}-1}

(the ratio between average fitness in the equilibrium that was reached, and the optimal fitness). Results are for random fitness matrices of size

8\times 5

, where

w_{ij}

is sampled uniformly at random from

[1-s,1+s]

. Note that most instances do not converge to the optimal outcome.

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 2 — Figure 2: Left: the maximal distance from the Wright manifold as a function of $r$ . Right: The distance from the Wright manifold over time for $r=0.001$ .

Evolutionary Game Theory

Evolutionary game theory studies how strategic behaviors spread or disappear through selection, imitation, learning, and interaction.

See all 31 papers

Jul 23, 2026

Natural Invariant Measures for Chaotic Game Dynamics: Finding Order in Chaos

We study the long-term behavior of the Multiplicative Weights Update (MWU) algorithm in game settings where learning dynamics frequently fail to converge to Nash equilibria and instead exhibit Li-Yorke chaos. While such chaos precludes the prediction of specific long-term strategy profiles, it does not imply a lack of statistical structure. We demonstrate that natural invariant measures - a fundamental concept from ergodic theory - provide the rigorous framework necessary to find order within this chaos. Focusing on a two-strategy congestion game, we prove that these measures allow for a comprehensive statistical characterization of the dynamics. Crucially, we show that this framework extends beyond simple strategy frequencies to general observables, enabling the precise calculation of long-term time averages for broad classes of economic metrics - including payoffs, social cost, and regret - despite chaos. Our results reveal that this simple learning algorithm captures the full spectrum of behaviors found in one-dimensional dynamical systems, from unique or multiple absolutely continuous invariant measures to complex periodic attractors as well as coexisting chaotic and stable (periodic) behaviors. By bridging game theory and dynamical systems, we show that statistical predictability is attainable even in the absence of pointwise convergence.

Jakub Bielawski, Thiparat Chotibut, Fryderyk Falniowski +2

Department of Mathematics, Krakow University of Economics, Rakowicka 27, 31-510 Kraków, Poland · Chula Intelligent and Complex Systems Lab, Department of Physics, Faculty of Science, Chulalongkorn University,Bangkok 10330, Thailand · Department of Mathematical Sciences, Indiana University Indianapolis,402 N. Blackford Street, Indianapolis, Indiana 46202, USA +1

Dynamical Systems Game Theory Congestion Games Chaotic Dynamical Systems

Ask PDF

May 26, 2026

Evolutionary Data Theory: On the Similarities between Data Problems and Evolutionary Games

Applying the concepts and formalism from Evolutionary Game Theory to the data regime, the fundamental paradigms of Evolutionary Data Theory are introduced. It is shown that essential definitions and results such as replicator equations, evolutionary strategies, the Bishop-Cannings theorem and the analogy to Lotka-Volterra systems can be mapped to the data interpretation. Understanding data in matrix form as evolutionary entities, input data is mapped to genes and organisms. Steered by genetic fitness and two evolutionary strategies, Dominant-Balanced and Altruistic-Selfish, data records and features conduct an evolutionary game. It is shown that this evolutionary interpretation remains universally meaningful, by proving convergence to a unique rest point, where all data features persist in the population. A basic example of multi-objective optimization is shown as well as a related distribution problem and machine learning applications.

Philipp Wissgott

danube.ai solutions gmbh, 1040 Vienna, Austria

Replicator Dynamics

Ask PDF

Apr 5, 2026

Parent Selection Mechanisms in Elitist Crossover-Based Algorithms

Parent selection methods are widely used in evolutionary computation to accelerate the optimization process, yet their theoretical benefits are still poorly understood. In this paper, we address this gap by proposing a parent selection strategy for the

(μ+1)

genetic algorithm (GA) that prioritizes the selection of maximally distant parents for crossover. We show that, with an appropriately chosen population size, the resulting algorithm solves the Jump

_k

problem in

O(k4^kn\log(n))

expected time. This bound is significantly smaller than the best known bound of

O(nμ\log(μ)+n\log(n)+n^{k-1})

for any

(μ+1)

~GA using no explicit diversity-preserving mechanism and a constant crossover probability. To establish this result, we introduce a novel diversity metric that captures both the maximum distance between pairs of individuals in the population and the number of pairs achieving this distance. The main novelty of our analysis is that it relies on crossover as a mechanism for creating and maintaining diversity throughout the run, rather than using crossover only in the final step to combine already diversified individuals. The insights provided by our analysis contribute to a deeper theoretical understanding of the role of crossover in the population dynamics of genetic algorithms.

Andre Opris, Denis Antipov

University of Passau Passau, Germany · Sorbonne Université, CNRS, LIP6 Paris, France

Evolutionary Optimization Genetic Algorithms Runtime Analysis of Evolutionary Algorithms

Ask PDF

Abstract

Evolutionary Game Theory

Explore similar work

Natural Invariant Measures for Chaotic Game Dynamics: Finding Order in Chaos

Evolutionary Data Theory: On the Similarities between Data Problems and Evolutionary Games

Parent Selection Mechanisms in Elitist Crossover-Based Algorithms