Strategic Divergence in Discrete Bidding Games

41 concepts33 papers1 proposal

Economic theory and game design have long enjoyed the mathematical comforts of the continuum. When modeling auctions, resource allocation, or competitive graph games, assuming that players can bid any real number or divide their budgets infinitely makes the math beautifully tractable. It allows researchers to deploy calculus, leverage fixed-point theorems to guarantee the existence of equilibria, and derive elegant closed-form solutions.

However, real-world systems do not operate on a continuum. Whether dealing with ad auctions on major tech platforms, blockchain transaction fees, or finite tokens in a board game, budgets and bids are inherently discrete. They are constrained by minimum currency units and fixed bid increments.

For a long time, a common assumption was that discrete spaces are merely close approximations of continuous ones—that if you make the grid fine enough, the continuous theory will accurately predict discrete behavior. A growing body of research reveals that this assumption is fundamentally flawed. Transitioning from continuous to discrete action spaces does not just add rounding errors; it introduces non-smooth mathematical properties, alters the existence of equilibria, and completely upends optimal strategies.

The Non-Equivalence Paradox

To understand why discrete bidding behaves so differently from continuous bidding, consider an infinite-duration graph game where two players bid for the right to move a token along a directed graph. In a continuous model, a player with a slightly larger budget can often guarantee a win by outbidding their opponent by an infinitesimally small, irrational amount.

When bids are restricted to integers, this mathematical symmetry breaks down. In Determinacy in Discrete-Bidding Infinite-Duration Games, Milad Aghajohari et al. demonstrated a striking paradox: discrete-bidding games do not function as simple approximations of continuous ones. In fact, the authors proved that a player who possesses a mathematically guaranteed winning strategy in a continuous-bidding model can be guaranteed to lose in the discrete version, regardless of how much budget they hold.

As explored by Suman Sadhukhan in Reachability Poorman Discrete-Bidding Games, integer-based budgets introduce non-smooth properties. Without the smooth derivatives of the continuum, calculating the minimum budget required to force a win becomes highly complex, exhibiting strange periodic patterns rather than linear scaling.

The Tyranny of Tie-Breaking

Why does this divergence happen? The root cause lies in how the two domains handle ties.

In a continuous strategy space, the probability of two players submitting the exact same real-number bid is effectively zero (a set of measure zero). Consequently, continuous models can largely ignore tie-breaking rules without affecting their theoretical guarantees.

In a discrete space, however, players choose from a finite set of options, making ties incredibly frequent. Because ties happen so often, the specific rule chosen to resolve them—such as favoring Player 1, flipping a coin, or letting the taxman take a cut—becomes the primary driver of the game's strategic landscape.

Continuous Bidding:
Player A: |------------------------o------------------------| (e.g., 7.3492...)
Player B: |---------------------------x---------------------| (e.g., 7.3511...)
Result: Ties are statistically impossible. Smooth payoff landscape.

Discrete Bidding:
Player A: |---[ 7 ]---[ 8 ]---[ 9 ]---|
Player B: |---[ 7 ]---[ 8 ]---[ 9 ]---|
Result: Frequent ties at integer steps. Tie-breaking rules dominate the outcome.

Milad Aghajohari et al. showed that while discrete games are often "determined" (meaning one player has a winning strategy), this determinacy depends entirely on the tie-breaking mechanism. If you alter the tie-breaking rule, the game's outcome can flip entirely. This sensitivity is echoed in practical market designs; David R. M. Thompson et al. demonstrated in Comparing Position Auctions Computationally that at large scales, secondary implementation choices like rounding logic and tie-breaking rules exert a disproportionate impact on the calculated efficiency and revenue of an auction.

Discontinuity and False Precision

In standard auction formats, like a second-price auction, the payoff structure is inherently discontinuous: bidding one cent below the highest bid yields zero utility, while bidding one cent above wins the item and yields a potentially large surplus.

When algorithms attempt to find equilibria by mapping continuous spaces onto discrete grids, this step-function payoff structure creates severe computational hurdles. In Computing Bayes-Nash Equilibria in Combinatorial Auctions with Continuous Value and Action Spaces, Vitor Bosshard et al. warned against the danger of "false precision." A strategy might look like a stable equilibrium on a discrete grid simply because the opponent's counter-strategies are restricted by the grid lines. Once evaluated against the full, continuous spectrum of real-world actions, these discrete approximations often collapse.

The Silver Lining of Discrete Constraints

While discrete constraints complicate mathematical analysis and break continuous proofs, they are not merely a nuisance. In many scenarios, forcing an action space to be discrete is a deliberate design choice that stabilizes systems and enables the discovery of unique strategies.

Bypassing Impossibility Theorems

In economic mechanism design, foundational theorems often prove that perfect market efficiency is impossible under continuous assumptions. For instance, the famous Myerson-Satterthwaite theorem states that efficient, deficit-free trade cannot be guaranteed when buyers and sellers have private, continuous valuations.

However, Abraham Othman et al. demonstrated in How Pervasive Is the Myerson-Satterthwaite Impossibility? that when valuations are restricted to discrete, finite sets, this impossibility frequently vanishes. In discrete settings, efficient trade becomes highly feasible, and any required subsidies are remarkably small.

Stabilizing Robust Strategies

Discrete increments can also act as a shield against malicious behavior. In combinatorial auctions, mechanisms are often vulnerable to "Sybil attacks," where a single bad actor creates multiple fake identities to manipulate the outcome.

In Optimal Mechanism Design for Agents with DSL Strategies: The Case of Sybil Attacks in Combinatorial Auctions, Yotam Gafni et al. showed that implementing fixed, discrete bid increments allows for the emergence of unique, robust strategies. These discrete constraints provide a stable environment where mechanisms can achieve near-optimal social welfare and revenue, even in the presence of attackers—a stability that continuous models fail to guarantee.

Algorithmic Tractability

Finally, from a purely computational perspective, discrete spaces allow for the deployment of combinatorial algorithms where continuous optimization fails. For example, Victor Naroditskiy et al. in Using Iterated Best-Response to Find Bayes-Nash Equilibria in Auctions leveraged discrete bid and value spaces to efficiently compute Bayes-Nash Equilibria via an iterated best-response framework, bypassing the need for complex analytical derivations.

Conclusion

The shift from continuous to discrete bidding constraints is far more than a change in granularity. It represents a fundamental shift in how games are won, lost, and designed. By understanding that discrete constraints introduce frequent ties, break continuous determinacy, and alter the stability of equilibria, mechanism designers can move past brittle continuous approximations and build systems optimized for the discrete reality of computation.

Key Foundational Work

Optimal design of english auctions with discrete bid levels (2007) — contributed 1 concept elements to this direction.
Learning Environmental Parameters for the Design of Optimal English Auctions with Discrete Bid Levels (2005) — contributed 1 concept elements to this direction.
Using Iterated Best-Response to Find Bayes-Nash Equilibria in Auctions (2007) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_discrete_bidding_constraints_6aeeaede,
  title = {discrete bidding constraints},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/discrete-bidding-constraints/rdr_6aeeaede2b8d4a7bb28f62ed3402eb29},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_discrete_bidding_constraints_6aeeaede_v1,
  title = {discrete bidding constraints},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/discrete-bidding-constraints/rdr_6aeeaede2b8d4a7bb28f62ed3402eb29/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake