Optimal strategy against straightforward bidding in clock auctions

Jad Zeroual, Marianne Akian, Aurélien Bechler, Matthieu Chardy, Stéphane Gaubert

TL;DR

This paper tackles the challenge of finding an optimal bidding strategy in complex clock auctions, specifically for the 5G spectrum allocation in France. By modeling the auction as a Partially Observable Markov Decision Process (POMDP) and assuming competitors use a "straightforward bidding" strategy, the authors derive a "Bellman strategy" that offers a robust and near-optimal performance compared to a perfectly informed bidder.

What Problem Does This Paper Address?

Spectrum auctions are crucial for telecommunications companies, and their complexity has evolved significantly. The French 5G auction, for instance, uses a clock auction format where prices increase until demand equals supply. A key challenge for bidders is to determine their optimal strategy when their competitors' valuations (and thus their bidding behavior) are unknown. This paper focuses on a specific scenario: what's the best strategy for a bidder when they assume their competitors are using a simple, myopic "straightforward bidding" (SB) strategy? SB involves bidding to maximize immediate utility, without considering future price changes or competitor reactions. The authors aim to find a strategy that maximizes a bidder's own profit in this environment, moving beyond the limitations of assuming perfect information or overly simplistic models.

Methods

The core of the paper's methodology lies in framing the auction as a Partially Observable Markov Decision Process (POMDP). This is a powerful framework for sequential decision-making under uncertainty, where the agent (the bidder) doesn't know the exact state of the world (competitors' valuations) but receives observations.

Key techniques include:

  • POMDP Formulation: The auction is modeled with states representing time, current price, player's bid, and opponent's demand. Observations include past bids and demands.
  • Bellman Strategy: The authors derive an optimal strategy, termed the "Bellman strategy," by solving the POMDP. A crucial contribution is showing that this strategy can be expressed in a concise form, avoiding the computationally intensive solution of dynamic programming over the entire belief space. This is achieved by identifying a "sufficient statistic" (the opponent's demand) under certain assumptions.
  • Aggregation of Opponents: To simplify the model, multiple "straightforward bidders" are aggregated into a single "super SB-player."
  • Probabilistic Models: To test their strategy, the authors use specific probabilistic models for opponent valuations, namely the "uniform case" and the "exponential case," which satisfy the assumptions required for their theoretical results (Markov property and stochastic monotonicity).

Datasets

Not discussed in the paper. The paper focuses on theoretical modeling and simulation-based experiments rather than using pre-existing datasets.

Key Insights and Ideas

  • Concise Optimal Strategy: The most significant insight is the derivation of a "Bellman strategy" that is not only optimal against straightforward bidders but also has a tractable, concise form. This avoids the computational burden of traditional POMDP solutions.
  • Robustness to Deviations: The Bellman strategy is shown to be robust. Even if opponents deviate from the assumed straightforward bidding strategy (within certain bounds), the bidder's expected gain does not decrease. This is a crucial practical guarantee.
  • Bellman vs. SB: The Bellman strategy consistently outperforms the straightforward bidding strategy, especially when compared to a perfectly informed player. This highlights the value of a more sophisticated, forward-looking approach in auctions.
  • Equilibrium Question: The paper suggests that the straightforward bidding strategy might not be an equilibrium in this context, as a bidder would prefer to deviate to the Bellman strategy. However, it leaves the question of whether the Bellman strategy itself is an equilibrium open for future work.

Key Results

  • Theorem 15: Provides a simplified expression for the Bellman strategy, avoiding belief space dynamic programming, under assumptions about the opponent's demand.
  • Theorem 27: Guarantees that the Bellman strategy's expected gain does not decrease if opponents deviate from straightforward bidding, as long as their strategy is "less than or equal to SB."
  • Empirical Evidence (Simulations):
    • Against a super SB-player, the Bellman strategy achieves expected gains that are 94-95% of a perfectly informed player's gain in the uniform case, significantly outperforming the SB strategy (around 88%).
  • In at least 89% of simulated auctions, the Bellman strategy yields a utility higher than 80% of the best-possible utility.
  • In about half of the samples, the Bellman strategy achieves the same utility as a perfectly informed player.
  • Similar conclusions hold for the exponential case.

Limitations and Future Work

  • Assumption of Opponent Behavior: The core strategy relies on the assumption that opponents play straightforward bidding. While the strategy is robust to deviations, its optimality is proven under this specific assumption.
  • Valuation Distribution Knowledge: The derived strategy requires knowledge of the distribution of opponents' valuations. In practice, this information is sensitive and hard to acquire.
  • Markov Chain Assumption: The paper assumes the opponent's demand follows a Markov chain. This is a simplification, as real-world valuations might be history-dependent or revised during the auction.
  • Equilibrium Analysis: The paper doesn't definitively prove whether the Bellman strategy is a Nash equilibrium. Future work could involve computing the expected gain of an SB player against a Bellman opponent to explore this.
  • More Complex Valuations: Extending the model to handle history-dependent valuations or dynamic budget adjustments would be valuable.
  • Higher-Dimensional Auctions: Applying the findings to more complex auctions (e.g., simultaneous ascending auctions with multiple items) is a promising direction.

Summary updated

Abstract

We study a model of auction representative of the 5G auction in France. We determine the optimal strategy of a bidder, assuming that the valuations of competitors are unknown to this bidder and that competitors adopt the straightforward bidding strategy. Our model is based on a Partially Observable Markov Decision Process (POMDP). We show in particular that this special POMDP admits a concise statistics, avoiding the solution of a dynamic programming equation in the space of beliefs. We illustrate our results by numerical experiments, comparing the value of the bidder with the value of a perfectly informed one.
BibTeX
@article{zeroual2025optimal,
  author = {Jad Zeroual and Marianne Akian and Aurélien Bechler and Matthieu Chardy and Stéphane Gaubert},
  title = {{Optimal strategy against straightforward bidding in clock auctions}},
  journal = {Perform. Evaluation},
  year = {2025},
  doi = {10.1016/j.peva.2025.102502},
}
Figure