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

Natural Invariant Measures for Chaotic Game Dynamics: Finding Order in Chaos
Jul 23, 2026Jakub Bielawski, Thiparat Chotibut, Fryderyk Falniowski +2Dynamical Systems Game Theory
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
Evolutionary Data Theory: On the Similarities between Data Problems and Evolutionary Games
May 26, 2026Philipp WissgottReplicator Dynamics
danube.ai solutions gmbh, 1040 Vienna, Austria
Parent Selection Mechanisms in Elitist Crossover-Based Algorithms
Apr 5, 2026Andre Opris, Denis AntipovEvolutionary Optimization Genetic Algorithms
University of Passau Passau, Germany · Sorbonne Université, CNRS, LIP6 Paris, France

Jul 23, 2026J/K move · Enter open · S save

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

Jakub Bielawski, Thiparat Chotibut, Fryderyk Falniowski, Michał Misiurewicz+1

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

Open paper AskPDF arXiv

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.

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