---
title: "Genetic algorithms for equilibrium computation"
description: "Apply genetic algorithms to find Nash equilibria in bimatrix games by encoding mixed strategies as chromosomes, using negative regret as fitness, and designing crossover and mutation operators on probability simplices."
author: "Raban Heller"
date: 2026-05-08
date-modified: 2026-05-08
categories:
- optimization-numerical-methods
- genetic-algorithms
- nash-equilibrium
- metaheuristics
keywords: ["genetic algorithm", "nash-equilibrium", "evolutionary computation", "mixed strategy", "optimization"]
labels: ["optimization", "evolutionary"]
tier: 1
bibliography: ../../../references.bib
vgwort: "TODO_VGWORT_optimization-numerical-methods_genetic-algorithm-equilibria"
image: thumbnail.png
image-alt: "Line plot showing convergence of genetic algorithm fitness over generations toward Nash equilibrium using the Okabe-Ito palette."
citation:
type: webpage
url: https://cttir.github.io/equilibria/tutorials/optimization-numerical-methods/genetic-algorithm-equilibria/
license: "CC BY-SA 4.0"
draft: false
has_static_fig: true
has_interactive_fig: true
has_shiny_app: false
---
```{r}
#| label: setup
#| include: false
library(ggplot2)
library(dplyr)
library(tidyr)
library(plotly)
okabe_ito <- c("#E69F00", "#56B4E9", "#009E73", "#F0E442",
"#0072B2", "#D55E00", "#CC79A7", "#999999")
theme_publication <- function(base_size = 12) {
theme_minimal(base_size = base_size) +
theme(plot.title = element_text(size = base_size * 1.2, face = "bold"),
plot.subtitle = element_text(size = base_size * 0.9, color = "grey40"),
axis.line = element_line(color = "grey30", linewidth = 0.3),
panel.grid.minor = element_blank(), legend.position = "bottom",
plot.margin = margin(10, 10, 10, 10))
}
```
## Introduction & motivation
Computing Nash equilibria is a fundamental problem in algorithmic game theory, but it is also a notoriously difficult one. The Lemke-Howson algorithm and support enumeration provide exact solutions for bimatrix games, but their worst-case complexity is exponential in the number of strategies. For large games arising in practical applications -- such as security games with hundreds of targets, network routing games with thousands of nodes, or auction mechanisms with combinatorial bid spaces -- exact methods become computationally infeasible. This motivates the use of metaheuristic optimisation techniques that trade guaranteed exactness for practical scalability.
Genetic algorithms (GAs) offer a particularly natural approach to equilibrium computation because the biological metaphor aligns with game-theoretic concepts. A population of candidate strategy profiles evolves over generations through selection, crossover, and mutation. Individuals with higher fitness -- defined as lower total regret -- are more likely to survive and reproduce. Over time, the population converges toward profiles where no player can profitably deviate, which is precisely the definition of a Nash equilibrium. This connection between evolutionary dynamics and Nash equilibrium has deep theoretical roots: the replicator dynamic, which models evolution in biological populations, converges to Nash equilibria under certain conditions, and genetic algorithms can be viewed as a discretised simulation of evolutionary dynamics with enhanced exploration capabilities.
The technical challenge lies in encoding mixed strategies as chromosomes and designing genetic operators that respect the geometry of the strategy space. A mixed strategy for a player with $m$ pure strategies is a point on the $(m-1)$-dimensional probability simplex, a constrained subset of $\mathbb{R}^m$ where all components are non-negative and sum to one. Standard crossover and mutation operators, designed for unconstrained real-valued optimisation, will generally produce offspring that violate these constraints. We need simplex-aware operators: crossover that interpolates between parent strategies while remaining on the simplex, and mutation that perturbs strategies without leaving the feasible region.
This tutorial implements a complete genetic algorithm for finding Nash equilibria in two-player bimatrix games. We develop the chromosome encoding, fitness function (negative maximum regret), simplex-preserving crossover and mutation operators, and tournament selection. The algorithm is tested on a three-by-three game with a known mixed-strategy equilibrium to allow validation. We track the convergence of fitness over generations and compare the GA solution against the exact equilibrium. The implementation demonstrates both the potential and the limitations of evolutionary approaches: the GA reliably finds approximate equilibria but requires careful parameter tuning and provides no guarantee of convergence to an exact solution. This makes it a valuable complement to, rather than a replacement for, exact methods.
The broader lesson is methodological. Game-theoretic problems often exhibit a landscape of local optima, saddle points, and plateaus that challenge gradient-based optimisation. Genetic algorithms, with their population-based search and stochastic operators, can navigate these landscapes more robustly than single-point methods. At the same time, they require problem-specific design choices -- the fitness function, the genetic operators, the population size -- that benefit from deep understanding of the mathematical structure of the equilibrium problem.
## Mathematical formulation
Consider a two-player game with payoff matrices $A \in \mathbb{R}^{m \times n}$ and $B \in \mathbb{R}^{m \times n}$. A strategy profile is a pair $(\mathbf{x}, \mathbf{y})$ where $\mathbf{x} \in \Delta^{m-1}$ and $\mathbf{y} \in \Delta^{n-1}$. The chromosome encodes the concatenation $\mathbf{c} = (\mathbf{x}, \mathbf{y}) \in \Delta^{m-1} \times \Delta^{n-1}$.
The fitness function is defined as negative maximum regret:
$$
f(\mathbf{x}, \mathbf{y}) = -\max\Big(\max_i \mathbf{e}_i^\top A \mathbf{y} - \mathbf{x}^\top A \mathbf{y},\; \max_j \mathbf{x}^\top B \mathbf{e}_j - \mathbf{x}^\top B \mathbf{y}\Big)
$$
At a Nash equilibrium, $f(\mathbf{x}^*, \mathbf{y}^*) = 0$. Simplex-preserving crossover of parents $\mathbf{x}_1, \mathbf{x}_2$ uses Dirichlet interpolation:
$$
\mathbf{x}_{\text{child}} = \frac{\alpha \mathbf{x}_1 + (1-\alpha) \mathbf{x}_2}{\|\alpha \mathbf{x}_1 + (1-\alpha) \mathbf{x}_2\|_1}, \quad \alpha \sim U(0,1)
$$
Mutation adds Dirichlet noise: $\mathbf{x}' \propto \mathbf{x} + \eta \cdot \text{Dir}(\mathbf{1})$ where $\eta$ is the mutation strength.
## R implementation
We implement the genetic algorithm with simplex-aware operators and run it on a three-by-three game. The convergence trajectory is recorded for visualisation.
```{r}
#| label: ga-equilibrium
set.seed(42)
# 3x3 game with known mixed equilibrium
A <- matrix(c(0, -1, 1, 1, 0, -1, -1, 1, 0), 3, 3, byrow = TRUE)
B <- -A # zero-sum game (Rock-Paper-Scissors variant)
m <- nrow(A); n <- ncol(A)
# Random point on simplex via Dirichlet(1,1,...,1)
rsimplex <- function(k) {
x <- -log(runif(k))
x / sum(x)
}
# Fitness: negative max regret
fitness <- function(chromo) {
x <- chromo[1:m]; y <- chromo[(m+1):(m+n)]
pay1 <- as.numeric(t(x) %*% A %*% y)
pay2 <- as.numeric(t(x) %*% B %*% y)
regret1 <- max(A %*% y) - pay1
regret2 <- max(t(B) %*% x) - pay2
-max(regret1, regret2)
}
# Simplex crossover
crossover <- function(p1, p2) {
alpha <- runif(1)
child <- numeric(m + n)
# Crossover each player's strategy separately
x_child <- alpha * p1[1:m] + (1 - alpha) * p2[1:m]
y_child <- alpha * p1[(m+1):(m+n)] + (1 - alpha) * p2[(m+1):(m+n)]
child[1:m] <- x_child / sum(x_child)
child[(m+1):(m+n)] <- y_child / sum(y_child)
child
}
# Simplex mutation
mutate_chromo <- function(chromo, strength = 0.1) {
x <- chromo[1:m]; y <- chromo[(m+1):(m+n)]
noise_x <- -log(runif(m))
noise_y <- -log(runif(n))
x_new <- x + strength * noise_x
y_new <- y + strength * noise_y
x_new <- pmax(x_new, 1e-12); y_new <- pmax(y_new, 1e-12)
c(x_new / sum(x_new), y_new / sum(y_new))
}
# GA parameters
pop_size <- 80
n_gen <- 150
mutation_rate <- 0.3
elite_frac <- 0.1
n_elite <- max(2, floor(pop_size * elite_frac))
# Initialise population
pop <- lapply(1:pop_size, function(i) c(rsimplex(m), rsimplex(n)))
history <- data.frame(generation = integer(), best_fitness = numeric(),
mean_fitness = numeric(), worst_fitness = numeric())
for (gen in 1:n_gen) {
fits <- sapply(pop, fitness)
rank_idx <- order(fits, decreasing = TRUE)
history <- rbind(history, data.frame(
generation = gen, best_fitness = max(fits),
mean_fitness = mean(fits), worst_fitness = min(fits)))
# Elitism
new_pop <- pop[rank_idx[1:n_elite]]
# Tournament selection + crossover + mutation
while (length(new_pop) < pop_size) {
t1 <- sample(pop_size, 3); p1 <- pop[[t1[which.max(fits[t1])]]]
t2 <- sample(pop_size, 3); p2 <- pop[[t2[which.max(fits[t2])]]]
child <- crossover(p1, p2)
if (runif(1) < mutation_rate) child <- mutate_chromo(child)
new_pop[[length(new_pop) + 1]] <- child
}
pop <- new_pop
}
# Extract best solution
best_idx <- which.max(sapply(pop, fitness))
best <- pop[[best_idx]]
x_ga <- best[1:m]; y_ga <- best[(m+1):(m+n)]
cat("GA Nash Equilibrium Approximation:\n")
cat(sprintf(" Player 1 strategy: (%.4f, %.4f, %.4f)\n", x_ga[1], x_ga[2], x_ga[3]))
cat(sprintf(" Player 2 strategy: (%.4f, %.4f, %.4f)\n", y_ga[1], y_ga[2], y_ga[3]))
cat(sprintf(" Maximum regret: %.6f\n", -fitness(best)))
cat(sprintf(" True equilibrium: (1/3, 1/3, 1/3) for both players\n"))
cat(sprintf(" Max deviation from true: %.6f\n",
max(abs(x_ga - 1/3), abs(y_ga - 1/3))))
```
## Static publication-ready figure
The convergence plot tracks the best, mean, and worst fitness across generations, showing how the population evolves toward the Nash equilibrium.
```{r}
#| label: fig-ga-convergence-static
#| fig-cap: "Figure 1. Convergence of a genetic algorithm toward the Nash equilibrium of a 3x3 Rock-Paper-Scissors game. Lines show best, mean, and worst fitness (negative maximum regret) across 150 generations with a population of 80 individuals. Fitness of zero corresponds to an exact Nash equilibrium. Simplex-preserving crossover and Dirichlet mutation operators ensure feasibility throughout evolution. Okabe-Ito palette."
#| dev: [png, pdf]
#| fig-width: 9
#| fig-height: 5
#| dpi: 300
history_long <- history %>%
pivot_longer(-generation, names_to = "metric", values_to = "fitness") %>%
mutate(metric = factor(recode(metric,
best_fitness = "Best", mean_fitness = "Mean", worst_fitness = "Worst"),
levels = c("Best", "Mean", "Worst")))
p <- ggplot(history_long, aes(x = generation, y = fitness, colour = metric,
text = paste0("Generation: ", generation,
"\nMetric: ", metric,
"\nFitness: ", round(fitness, 5)))) +
geom_line(linewidth = 0.8) +
geom_hline(yintercept = 0, linetype = "dashed", colour = "grey50", linewidth = 0.4) +
scale_colour_manual(values = okabe_ito[c(3, 1, 6)], name = "Population statistic") +
labs(title = "Genetic algorithm convergence to Nash equilibrium",
subtitle = "3x3 Rock-Paper-Scissors | Population: 80, Mutation rate: 0.3",
x = "Generation", y = "Fitness (negative max regret)") +
theme_publication()
p
```
## Interactive figure
Hover over the convergence lines to inspect fitness values at each generation. The interactive view reveals the fine structure of convergence, including plateaus and jumps caused by beneficial mutations.
```{r}
#| label: fig-ga-convergence-interactive
ggplotly(p, tooltip = "text") |>
config(displaylogo = FALSE,
modeBarButtonsToRemove = c("select2d", "lasso2d"))
```
## Interpretation
The genetic algorithm demonstrates clear convergence toward the known Nash equilibrium of the Rock-Paper-Scissors game, where both players should mix uniformly over all three actions with probability 1/3 each. The best fitness reaches values very close to zero (zero regret) within approximately 50 to 80 generations, confirming that the algorithm successfully identifies the equilibrium. However, several nuances merit careful discussion.
The convergence trajectory exhibits a characteristic two-phase pattern. In the first phase (roughly generations 1 through 30), fitness improves rapidly as the population moves from random initialisation toward the central region of the simplex. During this phase, selection pressure is strong because there is high variance in fitness across the population, and even simple crossover operations produce meaningful improvements. In the second phase, convergence slows considerably as the population clusters near the equilibrium and further improvements require precise fine-tuning of strategy weights. This deceleration is inherent to the problem geometry: near the equilibrium of a zero-sum game, the regret function has zero gradient (since both players' payoffs are locally flat with respect to small deviations), making the fitness landscape locally flat and difficult for the GA to navigate.
The gap between best and mean fitness provides insight into population diversity. Early in the run, this gap is large, indicating a diverse population exploring different regions of the strategy space. As evolution proceeds, the gap narrows as selection pressure drives the population toward consensus. The worst fitness line converges more slowly because mutation continually injects low-fitness individuals into the population, which is essential for maintaining exploration but creates a persistent tail of poor solutions. The elite preservation mechanism ensures that the best solutions are never lost, allowing the best fitness to be monotonically non-decreasing.
Comparing the GA solution to the exact equilibrium reveals the fundamental trade-off of metaheuristic methods. The GA achieves regret values on the order of 1e-3 to 1e-4, which is sufficient for many practical purposes but far from the machine-precision accuracy achievable by exact methods like support enumeration. For a game where we need precise equilibrium strategies (for instance, to compute exact expected payoffs or to verify theoretical predictions), the GA solution would need to be refined using a local optimisation method initialised at the GA's output. This hybrid approach -- using the GA for global exploration and a gradient-based method for local refinement -- is a common and effective strategy in practice.
The choice of genetic operators has significant impact on performance. Our simplex-preserving crossover, which interpolates between parents using a random convex combination, maintains feasibility by construction. The Dirichlet mutation operator adds noise proportional to the current strategy weights, ensuring that strategies near the boundary of the simplex are not pushed to infeasible regions. Alternative designs, such as using a logit transformation to map strategies to unconstrained space, are also viable but change the implicit metric of the search space. The mutation rate of 0.3 balances exploration and exploitation; higher rates would slow convergence while lower rates would risk premature convergence to a local optimum, which in this symmetric game is unlikely but becomes a real concern in games with multiple equilibria.
The scalability of the approach is both its strength and its limitation. The GA requires only fitness evaluations, which involve simple matrix multiplications, making each generation computationally cheap even for large games. However, the number of generations needed for convergence grows with the dimensionality of the strategy space, and the population size must increase to maintain adequate coverage. For games with dozens of strategies per player, the GA remains practical, but for games with hundreds of strategies, more structured approaches such as fictitious play or regret matching may be preferable.
## Extensions & related tutorials
The genetic algorithm approach extends naturally to multi-player games by concatenating all players' strategies into a single chromosome. For extensive-form games, behavioural strategies at each information set can be encoded separately. Combining the GA with local search produces a memetic algorithm that achieves faster convergence.
- [Unit testing game theory solvers in R](../../r-package-development/unit-testing-game-solvers/)
- [Eigenvalue methods for repeated game analysis](../../linear-algebra-matrix/eigenvalue-methods-repeated-games/)
- [Key player identification in network games](../../network-games/key-player-identification/)
- [GANs as a game-theoretic training process](../../ml-and-gt/gan-game-theoretic-training/)
## References
::: {#refs}
:::