In classical economic theory, markets are often assumed to possess a single, predictable point of stability: a unique equilibrium where supply perfectly matches demand, or where rational agents settle on a clear set of strategies. In these idealized settings, mechanism designers can easily forecast revenues, and participants can confidently optimize their behavior.
However, when real-world constraints—such as finite budgets, automated pacing algorithms, or market uncertainties—are introduced, this clean predictability shatters. Instead of a single stable state, markets frequently exhibit equilibrium multiplicity, a phenomenon where a single set of initial conditions can support multiple, distinct, and often conflicting stable outcomes.
Understanding why multiplicity emerges, how it complicates market predictability, and why it creates severe computational barriers is essential for designing modern digital marketplaces.
The Root Cause: How Constraints Warp the Game
To understand why multiplicity happens, consider a standard second-price auction. Without budget constraints, bidding one's true valuation is a dominant strategy, leading to a unique and predictable equilibrium. However, in modern advertising platforms, participants rarely bid in isolation; instead, they deploy automated bidding agents operating under strict high-level constraints, such as a maximum daily budget or a target cost-per-acquisition (CPA).
These constraints introduce complex interdependencies between otherwise independent events. For instance, if an advertiser is close to exhausting their budget, the platform may deliberately skip certain auctions to pace their spending. As shown by Chen et al., when platforms implement this kind of participation "throttling" in second-price auctions, it creates a highly chaotic strategic landscape with multiple distinct equilibria.
The intuition behind this multiplicity is a feedback loop:
- If Advertiser A expects Advertiser B to bid aggressively in the morning, Advertiser A will conserve their budget and bid in the afternoon.
- Because Advertiser A drops out of the morning auctions, Advertiser B wins them cheaply, validating their aggressive morning strategy.
- Conversely, if Advertiser A expects Advertiser B to save their budget for the afternoon, Advertiser A will dominate the morning, leaving the afternoon open for Advertiser B.
Both scenarios represent perfectly stable Nash equilibria, yet they yield entirely different allocations and prices. Conitzer et al. demonstrated a similar structural vulnerability in multiplicative pacing systems, where automated markets support multiple stable states that satisfy everyone's budget constraints but yield highly unpredictable trajectories.
[Initial Market Conditions]
│
▼
┌─────────────────────────────────────────┐
│ High-Level Constraints Introduced │
│ (Budgets, Pacing, Target CPAs) │
└─────────────────────────────────────────┘
│
├──────────────────────────────────────┐
▼ ▼
┌───────────────────────────────────┐ ┌───────────────────────────────────┐
│ Equilibrium A │ │ Equilibrium B │
│ Aggressive early bidding; │ │ Conservative early bidding; │
│ Low afternoon prices. │ │ High afternoon prices. │
└───────────────────────────────────┘ └───────────────────────────────────┘
This structural shift is not unique to ad auctions. Whenever a market model incorporates non-linear preferences or strategic personalization, uniqueness is compromised. For example, Li proved that when sellers in a linear Fisher market shift from uniform pricing to personalized pricing and priorities, the market transitions from a stable, predictable environment to one characterized by multiple stable allocations or even a total absence of equilibrium. Similarly, Romm et al. showed that introducing varied financial aid packages into college admission matching markets expands the set of stable outcomes from a small, predictable core into a large, diverse set of potential student assignments.
The Consequence: Revenue Volatility and Ambiguity
For market designers and participants, equilibrium multiplicity is more than a theoretical quirk; it introduces severe operational risks.
The primary danger for platform operators is revenue volatility. In an empirical and computational analysis of position auctions, Thompson et al. observed a striking divergence between social welfare and platform revenue. While the total value generated by the auction (social welfare) remained relatively stable across different stable states, the platform's revenue fluctuated wildly depending on which specific equilibrium the bidders settled upon. This means a platform could experience a massive drop in revenue purely due to an unpredictable shift in equilibrium selection, even if the market remains socially efficient.
Multiplicity also distorts the behavior of the participants themselves:
- Strategic Ambiguity: When optimizing over complex constraints like target CPAs across multiple auctions, there is rarely a single clean outcome. Liaw et al. highlighted that this multiplicity creates deep ambiguity for advertisers, making it incredibly difficult for them to evaluate the risks and rewards of truthful versus strategic reporting to their own autobidding agents.
- Exogenous Shocks: Outside factors can easily tip a market from one equilibrium to another. Melolidakis demonstrated that in Cournot competition models, the mere introduction of demand uncertainty (stochastic demand) can cause production levels to fracture into multiple stable states, complicating forecasting for businesses and regulators alike.
- Structural Market Power: In large-scale industrial settings, such as natural gas markets, Baltensperger et al. showed that multiplicity is a natural byproduct of market power rather than an error in model specification, meaning that a single set of physical market conditions can legitimately yield a wide range of plausible pricing outcomes.
The Computational Barrier: Hardness and Non-Approximability
If a market supports multiple equilibria, a natural algorithmic goal is to find the "best" one—for instance, the equilibrium that maximizes revenue or social welfare. However, the mathematical structure that creates multiplicity also tends to make these optimization problems computationally intractable.
When utility functions are capped or constrained, navigating the equilibrium space becomes an NP-hard problem. For example, Mehlhorn et al. studied Fisher markets where buyers have budget-additive utilities (meaning their satisfaction caps out after a certain point). Because these caps create non-unique equilibrium states with highly fragmented price distributions, the authors proved that finding an equilibrium that maximizes overall social welfare is strictly NP-hard.
┌─────────────────────────────────────────────────────────────────────────┐
│ Computational Landscape │
├────────────────────────────────────┬────────────────────────────────────┤
│ First-Price Auctions / Unconstrained│ Second-Price / Budget-Constrained │
├────────────────────────────────────┼────────────────────────────────────┤
│ • Unique Equilibrium │ • Multiple, Disconnected Equilibria│
│ • Easily Calculated │ • PPAD-Complete / NP-Hard │
│ • Predictable Revenue │ • High Revenue Volatility │
└────────────────────────────────────┴────────────────────────────────────┘
Furthermore, the geometry of the equilibrium space itself changes. Instead of a single, continuous region of stability, multiple equilibria often manifest as isolated, disconnected points. This fragmentation creates a fundamental barrier for approximation algorithms. Tao et al. demonstrated that the existence of these disconnected equilibrium states prevents the development of high-precision polynomial-time approximation schemes (PTAS) for identifying the most beneficial equilibrium for a given agent.
This computational chaos forces a shift in how economists and computer scientists approach market analysis:
- Abandoning the Nash Assumption: Because finding a Nash equilibrium in these environments is often PPAD-complete—as Chen et al. showed for throttling mechanisms—researchers are moving away from assuming markets ever reach a perfect equilibrium. Instead, Nekipelov et al. proposed an econometric framework built on "no-regret learning," which allows structural value inference from observed bidding data without requiring the market to settle into a unique Nash state.
- Simplifying Strategy Spaces: To make verification tractable in repeated keyword auctions, Belardinelli et al. introduced formal logics to restrict reasoning to simpler, human-friendly strategies, bypassing the vast, unmanageable space of potential equilibria.
- Accepting Coarse Guarantees: Rather than trying to pinpoint a exact equilibrium in a complex autobidding world, mechanism designers are focusing on robust, worst-case bounds. Feng et al. showed that despite the non-uniqueness and calculation hardness inherent to second-price autobidding, simply enforcing a budget constraint guarantees that any pure Nash equilibrium will still capture at least 50% of the optimal liquid welfare.
As marketplaces become increasingly automated—integrating multi-channel constraints (Aggarwal et al.) and real-time generative AI tools (Wang et al.)—the challenges of equilibrium multiplicity will only intensify. Designing robust mechanisms requires moving past the assumption of a single market clearing state, and instead building systems that are resilient to the volatile landscape of multiple equilibria.
Key Foundational Work
Comparing Position Auctions Computationally (2010) — contributed 2 concept elements to this direction.
Econometrics for Learning Agents (2015) — contributed 1 concept elements to this direction.
Spectrum sharing games on the interference channel (2010) — contributed 1 concept elements to this direction.