Minimax Duality in Game-Theoretic Probability

Rafael FrongilloarXiv 2025 · DOI · arXiv

TL;DR

This paper establishes a formal bridge between measure-theoretic probability (the standard Kolmogorov approach) and game-theoretic probability by framing them as two sides of a minimax duality. By proving a new minimax theorem for finite-time horizons, the author shows how to "lift" traditional probabilistic results into more robust, "pathwise" game-theoretic statements that hold without any underlying stochastic assumptions.

What Problem Does This Paper Address?

Probability theory has two historical lineages: the "measure-theoretic" approach (Fermat), which counts outcomes and assigns weights, and the "game-theoretic" approach (Pascal), which reasons about fair stakes and betting strategies. While measure theory became the dominant language of 20th-century math, game-theoretic probability (GTP) has seen a resurgence because it is more robust—it doesn't require assuming a data-generating process exists.

However, the precise mathematical relationship between these two worlds has remained somewhat fuzzy. We know they often agree, but we lacked a general "translation manual." The challenge is that GTP results are often "worst-case" (holding for all possible sequences), while measure-theoretic results are "average-case" (holding almost surely under a specific distribution). This paper seeks to unify them using the lens of minimax duality: the idea that in a zero-sum game, the order of play shouldn't change the value of the game.

Methods

The author introduces several novel theoretical components:

  • Gamble Spaces: A new, streamlined formalism $(\Omega, \mathcal{Z})$ that serves as the game-theoretic analog to a probability space. It defines "upper expectations" as the minimum cost to replicate a payoff using available gambles.
  • Sequential Minimax Theorem: The paper's technical core is a proof (Theorem 4.15) for finite-time horizons. It uses backward induction—a technique common in game theory and reinforcement learning—to show that game-theoretic and measure-theoretic expectations align when certain convexity and measurability conditions are met.
  • Descriptive Set Theory: To handle the "messy" math of infinite outcome spaces, the author employs the theory of analytic sets and universal measurability. This allows the framework to remain mathematically rigorous while dealing with the complex conditional structures required for sequential games.

Datasets

Not discussed in the paper. This is a theoretical mathematical work; it uses formal proofs rather than empirical data.

Key Insights and Ideas

  • Probability as a Game: The paper treats probability as a zero-sum game between Gambler (who tries to get rich) and World (who chooses the outcomes). Measure-theoretic probability corresponds to World playing first (committing to a distribution), while game-theoretic probability corresponds to Gambler playing first (committing to a strategy).
  • Constructive Refinement: Game-theoretic probability is a "constructive refinement" of measure theory. While measure theory might tell you an event has probability zero, game-theoretic probability gives you the actual betting strategy to "test" that claim and profit if it fails.
  • The Price Chain: The author identifies a hierarchy of "prices" (expectations). The gap between these prices represents the "bid-ask spread" created by different levels of information or adversarial power granted to "World."
  • Online Learning Connection: A major "aha moment" is the realization that minimax regret in adversarial online machine learning is mathematically identical to a game-theoretic upper expectation. This links two previously distinct fields of study.

Key Results

  • Finite-Time Duality: The paper proves that for any finite time $T$, the game-theoretic and measure-theoretic views are duals. This allows researchers to take a standard measure-theoretic bound (like Azuma-Hoeffding) and automatically produce a game-theoretic version.
  • Composite Ville’s Theorem: The author generalizes Ville’s classic theorem, showing that a single betting strategy can witness the "nullness" of an event across an entire set of probability measures simultaneously.
  • Translation Success: The paper successfully translates several major results—including the Quantitative Central Limit Theorem and Matrix Concentration inequalities—into the game-theoretic framework, proving they hold "pathwise" without needing a fixed probability measure.

Limitations and Future Work

  • The Infinite Horizon Gap: The main minimax theorem is currently limited to finite time. Extending this to infinite time (e.g., the Strong Law of Large Numbers) is a major open conjecture. The author notes that the "discontinuity" of infinite-time events (like tail events) makes the math significantly harder.
  • Non-Constructive Existence: While the minimax theorem proves that a successful betting strategy exists, it doesn't always tell you how to compute it efficiently.
  • Measurability Hurdles: On the measure-theoretic side, the duality relies on heavy machinery from descriptive set theory. Bypassing these technical requirements to make the theory more accessible is a suggested future direction.

Summary updated

Abstract

Game-theoretic probability uses the structure of gambles to define a concept like probability, but which is more flexible and robust. We show that results in game-theoretic probability can be thought of as minimax theorems for specific zero-sum games between two players, Gambler and World. The traditional measure-theoretic versions arise when World must play first. This perspective suggests the possibility of a more general minimax theorem from which a wide array of game-theoretic results would follow. After developing a new framing of game-theoretic probability via gamble spaces, we prove such a theorem for finite time. Applying this minimax theorem to games derived from existing measure-theoretic statements, we prove several existing and novel game-theoretic statements. This general minimax theorem can be thought of as a composite Ville's theorem, as we discuss along with future directions.
BibTeX
@misc{frongillo2025minimax,
  author = {Rafael Frongillo},
  title = {{Minimax Duality in Game-Theoretic Probability}},
  year = {2025},
  eprint = {2512.21026},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2512.21026},
}
Figure