Monte Carlo methods for equilibrium computation

simulations
monte-carlo
equilibrium-computation
numerical-methods
Use Monte Carlo simulation in R to approximate Nash equilibria, estimate equilibrium payoffs under uncertainty, and validate analytical solutions through large-sample simulation experiments.
Author

Raban Heller

Published

May 8, 2026

Modified

May 8, 2026

Keywords

Monte Carlo, simulation, Nash equilibrium, stochastic, numerical methods, convergence

Introduction & motivation

Analytical solutions for game-theoretic equilibria exist only for special cases — symmetric games, small strategy spaces, or games with particular structural properties. For larger or more complex games — those with many players, continuous action spaces, stochastic payoffs, or incomplete information — exact computation may be intractable. Monte Carlo simulation provides a powerful alternative: rather than solving the game analytically, we simulate thousands or millions of plays and estimate equilibrium properties from the resulting sample. This approach is particularly valuable in three contexts. First, validation: we can verify analytical equilibrium predictions by simulating the game under equilibrium strategies and checking that payoffs, winning probabilities, and other statistics match the theory. Second, approximation: when the equilibrium is known in functional form but expected payoffs involve complex integrals (common in auction theory and Bayesian games), Monte Carlo integration provides numerical answers. Third, exploration: when the equilibrium is unknown, we can search over strategy spaces using simulation-based optimisation to find approximate equilibria. This tutorial simulates Matching Pennies at its known mixed equilibrium and a first-price auction with independent Beta(2,5) private values. It demonstrates payoff estimation, pointwise confidence intervals, and the relationship between sample size and precision. It does not search for an unknown equilibrium or implement variance reduction.

Mathematical formulation

For a game with strategy profile \(s = (s_1, \ldots, s_n)\) and payoff functions \(u_i(s, \omega)\) where \(\omega\) represents random elements (types, nature’s moves), the expected payoff under strategy profile \(s\) is:

\[E[u_i(s)] = \int u_i(s, \omega) \, dF(\omega)\]

The Monte Carlo estimator with \(M\) samples is:

\[\hat{u}_i^M = \frac{1}{M} \sum_{m=1}^M u_i(s, \omega_m), \quad \omega_m \sim F\]

By the central limit theorem, \(\hat{u}_i^M \xrightarrow{d} N(E[u_i], \sigma^2/M)\), giving a 95% confidence interval:

\[\hat{u}_i^M \pm 1.96 \cdot \frac{\hat{\sigma}}{\sqrt{M}}\]

The convergence rate is \(O(1/\sqrt{M})\): halving the confidence interval width requires quadrupling the sample size — a fundamental limitation of Monte Carlo methods.

For equilibrium search, we define a strategy \(s_i\) parameterised by \(\phi_i\) and search for \(\phi^*\) such that no player can improve by deviating:

\[\phi_i^* = \arg\max_{\phi_i} \hat{u}_i^M(\phi_i, \phi_{-i}^*)\]

R implementation

set.seed(42)

# === 1. Validation: Mixed-strategy NE in Matching Pennies ===
# NE: both mix 50-50. Expected payoff = 0 for both players.
n_sims <- c(100, 500, 1000, 5000, 10000, 50000)

mc_matching_pennies <- function(M) {
  p1 <- sample(c(1, -1), M, replace = TRUE)  # H=1, T=-1
  p2 <- sample(c(1, -1), M, replace = TRUE)
  payoff1 <- ifelse(p1 == p2, 1, -1)  # P1 wins if match
  c(mean = mean(payoff1), se = sd(payoff1) / sqrt(M))
}

cat("=== Monte Carlo Validation: Matching Pennies (NE: both mix 50-50) ===\n")
=== Monte Carlo Validation: Matching Pennies (NE: both mix 50-50) ===
mp_results <- sapply(n_sims, mc_matching_pennies)
for (i in seq_along(n_sims)) {
  cat(sprintf("  M = %6d: mean = %+.4f, SE = %.4f, 95%% CI = [%.4f, %.4f]\n",
              n_sims[i], mp_results[1,i], mp_results[2,i],
              mp_results[1,i] - 1.96*mp_results[2,i],
              mp_results[1,i] + 1.96*mp_results[2,i]))
}
  M =    100: mean = -0.0600, SE = 0.1003, 95% CI = [-0.2566, 0.1366]
  M =    500: mean = -0.0560, SE = 0.0447, 95% CI = [-0.1436, 0.0316]
  M =   1000: mean = +0.0100, SE = 0.0316, 95% CI = [-0.0520, 0.0720]
  M =   5000: mean = -0.0272, SE = 0.0141, 95% CI = [-0.0549, 0.0005]
  M =  10000: mean = -0.0138, SE = 0.0100, 95% CI = [-0.0334, 0.0058]
  M =  50000: mean = -0.0058, SE = 0.0045, 95% CI = [-0.0146, 0.0030]
# === 2. Approximation: First-price auction with Beta-distributed values ===
# Values ~ Beta(2,5), n=3 bidders. Analytical BNE is complex; MC estimates revenue.
n_bidders <- 3
n_auction_sims <- 20000

# Symmetric independent-private-values equilibrium:
# b(v) = v - integral_0^v F(t)^(n-1) dt / F(v)^(n-1).
# Integrate once on a grid concentrated near zero, then interpolate bids.
# Quadrature/interpolation error is separate from Monte Carlo sampling error.
make_beta_bid <- function(n, a_shape = 2, b_shape = 5, n_grid = 20001L) {
  stopifnot(length(n) == 1L, is.finite(n), n >= 2, n == floor(n),
            length(a_shape) == 1L, is.finite(a_shape), a_shape > 0,
            length(b_shape) == 1L, is.finite(b_shape), b_shape > 0,
            length(n_grid) == 1L, is.finite(n_grid), n_grid >= 100,
            n_grid == floor(n_grid))
  grid <- seq(0, 1, length.out = n_grid)^2
  cdf_power <- pbeta(grid, a_shape, b_shape)^(n - 1)
  integral <- c(0, cumsum(diff(grid) *
                          (head(cdf_power, -1) + tail(cdf_power, -1)) / 2))
  bid <- numeric(length(grid))
  positive <- cdf_power > 0
  bid[positive] <- grid[positive] - integral[positive] / cdf_power[positive]
  bid <- pmax(0, pmin(grid, bid))
  interpolate <- approxfun(grid, bid, rule = 1)
  function(v) {
    if (!is.numeric(v) || any(!is.finite(v)) || any(v < 0 | v > 1))
      stop("Values must be finite numbers between zero and one.")
    interpolate(v)
  }
}
bid_fpa_beta <- make_beta_bid(n_bidders)
values <- matrix(rbeta(n_bidders * n_auction_sims, 2, 5), nrow = n_auction_sims)
bids <- matrix(bid_fpa_beta(as.vector(values)), nrow = n_auction_sims)

winners <- apply(bids, 1, which.max)
revenues <- bids[cbind(1:n_auction_sims, winners)]
winner_values <- values[cbind(1:n_auction_sims, winners)]
surpluses <- winner_values - revenues

cat(sprintf("\n=== First-Price Auction: Beta(2,5) values, n=%d bidders, M=%d ===\n",
            n_bidders, n_auction_sims))

=== First-Price Auction: Beta(2,5) values, n=3 bidders, M=20000 ===
cat(sprintf("  Mean revenue: %.4f (SE: %.4f)\n", mean(revenues), sd(revenues)/sqrt(n_auction_sims)))
  Mean revenue: 0.2751 (SE: 0.0005)
cat(sprintf("  Mean winner surplus: %.4f\n", mean(surpluses)))
  Mean winner surplus: 0.1520
cat(sprintf("  Mean winner value: %.4f\n", mean(winner_values)))
  Mean winner value: 0.4272
cat(sprintf("  Efficiency (winner has highest value): %.1f%%\n",
            100 * mean(apply(values, 1, which.max) == winners)))
  Efficiency (winner has highest value): 100.0%
# === 3. Convergence tracking ===
# Track running mean of auction revenue as M grows
running_means <- cumsum(revenues) / (1:n_auction_sims)
sample_count <- seq_along(revenues)
running_variance <- pmax(0, cumsum(revenues^2) - sample_count * running_means^2) /
  pmax(1, sample_count - 1)
running_se <- sqrt(running_variance / sample_count)
running_se[1] <- NA_real_


cat(sprintf("\n  Convergence: at M=100: %.4f, M=1000: %.4f, M=10000: %.4f, M=20000: %.4f\n",
            running_means[100], running_means[1000], running_means[10000], running_means[20000]))

  Convergence: at M=100: 0.2794, M=1000: 0.2757, M=10000: 0.2743, M=20000: 0.2751

Static publication-ready figure

conv_df <- tibble(
  M = 1:n_auction_sims,
  running_mean = running_means,
  se = running_se,
  lower = running_mean - 1.96 * se,
  upper = running_mean + 1.96 * se
) |> filter(M >= 10)  # skip first few for stability

final_est <- tail(running_means, 1)

ggplot(conv_df, aes(x = M)) +
  geom_ribbon(aes(ymin = lower, ymax = upper), fill = okabe_ito[2], alpha = 0.3) +
  geom_line(aes(y = running_mean), color = okabe_ito[5], linewidth = 0.6) +
  geom_hline(yintercept = final_est, linetype = "dashed", color = "grey50") +
  annotate("text", x = n_auction_sims * 0.7, y = final_est + 0.01,
           label = sprintf("Final estimate: %.4f", final_est), size = 3.5) +
  scale_x_log10(labels = scales::comma_format()) +
  labs(title = "Monte Carlo convergence: first-price auction revenue",
       subtitle = sprintf("Beta(2,5) values, n=3 bidders; CI narrows as O(1/√M)"),
       x = "Number of simulations (M)", y = "Running mean of revenue") +
  theme_publication()
Figure 1: Figure 1. Monte Carlo convergence of expected revenue in a first-price auction with Beta(2,5) values and 3 bidders. The running mean (blue) estimates revenue under the numerically approximated bidding strategy. The shaded intervals are pointwise normal approximations; they are not a simultaneous confidence band and exclude numerical integration error. The inset text shows the final estimate. This demonstrates the fundamental trade-off in Monte Carlo methods: more precision requires quadratically more computation. Okabe-Ito palette.

Interactive figure

# Compare MC precision across different sample sizes for multiple game statistics
sample_sizes <- c(50, 100, 200, 500, 1000, 2000, 5000, 10000)
n_reps <- 200  # replications per sample size

precision_data <- lapply(sample_sizes, function(M) {
  reps <- replicate(n_reps, {
    vals <- matrix(rbeta(n_bidders * M, 2, 5), nrow = M)
    # Monotone symmetric bids make the highest-value bidder the winner.
    winner_value <- do.call(pmax, as.data.frame(vals))
    rev <- bid_fpa_beta(winner_value)
    mean(rev)
  })
  tibble(M = M, mean_est = mean(reps), sd_est = sd(reps),
         cv = sd(reps) / mean(reps) * 100)
}) |> bind_rows() |>
  mutate(text = paste0("M = ", M,
                       "\nMean revenue: ", round(mean_est, 4),
                       "\nSD of estimates: ", round(sd_est, 4),
                       "\nCV: ", round(cv, 2), "%"))

p_precision <- ggplot(precision_data, aes(x = M, y = sd_est, text = text)) +
  geom_line(color = okabe_ito[5], linewidth = 1) +
  geom_point(color = okabe_ito[5], size = 3) +
  scale_x_log10() +
  scale_y_log10() +
  labs(title = "Monte Carlo precision vs sample size",
       subtitle = "SD of revenue estimates across 200 replications; log-log scale shows 1/√M slope",
       x = "Sample size (M)", y = "Standard deviation of estimates") +
  theme_publication()

ggplotly(p_precision, tooltip = "text") |>
  config(displaylogo = FALSE, modeBarButtonsToRemove = c("select2d", "lasso2d"))
Figure 2

Interpretation

The Matching Pennies example estimates the zero payoff implied by independently mixing 50–50. The auction uses the symmetric risk-neutral equilibrium formula for independent private values, approximated by trapezoidal integration on a fixed grid. The bids are computed once and interpolated for every simulated value, avoiding millions of repeated numerical integrations. Regression checks compare the bids with adaptive numerical integrals and the closed-form uniform-value auction.

There are two distinct error sources: numerical approximation of the bidding function and Monte Carlo estimation of revenue. The plotted standard errors describe sampling uncertainty only. At a fixed sample size, the normal intervals are asymptotic pointwise intervals; inspecting many successive intervals does not give simultaneous 95% coverage. These draws are independent, so a stationary-regime or burn-in diagnostic is not relevant.

The repeated-sampling plot estimates how the standard deviation changes with sample size. The expected rate is \(O(M^{-1/2})\) when variance is finite. A precision target should use the estimated standard error relative to the estimated revenue, rather than a universal sample-size prescription. Antithetic sampling, control variates, and importance sampling are possible extensions; this tutorial does not measure their benefit or establish an unknown equilibrium.

References

Back to top

Reuse

Citation

BibTeX citation:
@online{heller2026,
  author = {Heller, Raban},
  title = {Monte {Carlo} Methods for Equilibrium Computation},
  date = {2026-05-08},
  url = {https://cttir.github.io/equilibria/tutorials/simulations/monte-carlo-game-equilibria/},
  langid = {en}
}
For attribution, please cite this work as:
Heller, Raban. 2026. “Monte Carlo Methods for Equilibrium Computation.” May 8. https://cttir.github.io/equilibria/tutorials/simulations/monte-carlo-game-equilibria/.