2025-11-12T07:16:10.215779

Unending Sequential Auctions

Ban
Sequential auctions for identical items with unit-demand, private-value buyers are common and often occur periodically without end, as new bidders replace departing ones. We model bidder uncertainty by introducing a probability that a bidder must exit the auction in each period. Treating the sequential auction as a Markov process, we demonstrate the existence of a unique steady state. In the absence of uncertainty, the steady state resembles a posted-price mechanism: bidders with values above a threshold almost surely win items by repeatedly bidding the threshold price, while those below the threshold almost surely do not. The equilibrium price corresponds to the threshold value that balances supply (bidders with values above the threshold) and demand (auction winners). When uncertainty is introduced, the threshold value persists but becomes less precise, growing "fuzzier" as uncertainty increases. This uncertainty benefits low-value bidders, those below the threshold, by giving them a significant chance of winning. Surprisingly, high-value bidders also benefit from uncertainty, up to a certain value limit, as it lowers equilibrium bids and increases their expected utility. On the other hand, this bidder uncertainty often reduces the auctioneer's utility.
academic

Unending Sequential Auctions

Basic Information

  • Paper ID: 2510.08742
  • Title: Unending Sequential Auctions
  • Author: Amir Ban (Hebrew University of Jerusalem)
  • Classification: cs.GT (Computer Science - Game Theory)
  • Publication Date: October 2025
  • Paper Link: https://arxiv.org/abs/2510.08742

Abstract

This paper investigates the problem of infinite-horizon sequential auctions, modeling unit-demand buyers with private valuations for identical goods. Buyer uncertainty is modeled by introducing a probability that buyers must exit the auction in each period. Sequential auctions are treated as Markov processes, and the existence of a unique steady state is established. Without uncertainty, the steady state resembles a fixed-price mechanism: buyers with valuations above a threshold almost surely win items through repeated threshold-price bidding, while those below the threshold almost surely do not win. When uncertainty is introduced, the threshold persists but becomes less precise, becoming increasingly "blurred" as uncertainty increases. Surprisingly, this uncertainty benefits not only low-value buyers but also high-value buyers to some extent.

Research Background and Motivation

Problem Identification

  1. Real-world demand: Many real-world auctions (such as art, flowers, fish, wine, satellite leasing, etc.) persist across multiple sessions with infinite-horizon characteristics
  2. Digital scenarios: Search engine keyword bidding auctions and cloud computing resource allocation auctions often continue indefinitely
  3. Blockchain applications: Bitcoin transaction fee competition represents a typical infinite-horizon multi-unit pay-to-bid auction

Research Significance

Traditional finite sequential auction theory cannot adequately explain these persistent auction phenomena, necessitating a new theoretical framework to analyze optimal bidding strategies for buyers in infinite-horizon auctions.

Limitations of Existing Approaches

  1. Classical models: The classical model by Milgrom and Weber (2000) applies only to finite-round auctions
  2. Lack of uncertainty modeling: Existing models fail to account for various uncertainty factors faced by buyers
  3. Insufficient steady-state analysis: Lack of systematic analysis of steady-state behavior in infinite-horizon auctions

Research Motivation

By modeling infinite-horizon sequential auctions through Markov processes and analyzing the impact of buyer uncertainty on auction outcomes, this work provides theoretical guidance for practical applications.

Core Contributions

  1. Theoretical framework: Establishes a Markov process model for infinite-horizon sequential auctions and proves the existence of a unique steady state
  2. Fixed-price mechanism: Demonstrates that auctions without uncertainty converge to a fixed-price mechanism with price X(λ)=F−1(λ−1λ)X(\lambda) = F^{-1}(\frac{\lambda-1}{\lambda})
  3. Uncertainty analysis: Systematically analyzes the impact of buyer uncertainty on auction outcomes, finding that uncertainty benefits most buyers
  4. Universal results: Proves that the beneficial effects of uncertainty apply to any uncertainty model (including value discounting and lifecycle restrictions)
  5. Practical applications: Provides theoretical explanations for real-world scenarios such as the Bitcoin transaction fee market

Methodology Details

Task Definition

Investigate optimal bidding strategies and steady-state characteristics of sequential auctions conducted indefinitely. Inputs include:

  • Buyer value distribution F(x)F(x)
  • New buyer arrival rate λ\lambda (Poisson distribution)
  • Buyer uncertainty parameter δ\delta (probability of removal per round)

Outputs are the steady-state bidding function b(x)b(x) and auction characteristics.

Model Architecture

Basic Model Setup

  • Auction format: First-price sealed-bid auction conducted each round
  • Buyer characteristics: Unit demand, private valuations, values independently drawn from a known continuous distribution XX
  • Arrival process: New buyers arrive according to a Poisson process with expectation λ\lambda
  • Uncertainty modeling: Each buyer is removed with probability δ\delta each round

Markov Process Modeling

Let NtN_t denote the number of buyers in the pool at round tt, then: Nt+1=(Nt−1)++ΛtN_{t+1} = (N_t - 1)^+ + \Lambda_t where Λt\Lambda_t is the number of newly arriving buyers (Poisson distribution).

Steady-State Analysis Method

  1. State space: N={0,1,2,...}\mathcal{N} = \{0, 1, 2, ...\}
  2. Transition probabilities: Analyzed through probability generating functions
  3. Steady-state conditions: Finding distributions satisfying detailed balance conditions

Technical Innovations

1. Threshold Mechanism Discovery

Theorem 1 (Winner Threshold): When λ>1\lambda > 1 and δ=0\delta = 0, buyers with valuations above X(λ)X(\lambda) almost surely win, while those below this threshold almost surely do not win.

2. Bidding Function Derivation

Theorem 2 (Bidding without Uncertainty): In equilibrium, the buyer's bidding function is:

x & x < X(\lambda) \\ X(\lambda) & x > X(\lambda) \end{cases}$$ #### 3. Uncertainty Impact Analysis **Theorem 3 (Bidding with Uncertainty)**: When $\delta > 0$, the bidding function is: $$b(x) = \left[\frac{1}{W(F(x))} + \frac{1-\delta}{\delta}\right]\int_X^x \frac{zw(F(z))f(z)}{\left[1 + \frac{1-\delta}{\delta}W(F(z))\right]^2}dz$$ where $W(g)$ and $w(g)$ are the steady-state winner cumulative distribution and density functions, respectively. ## Experimental Setup ### Theoretical Verification Methods 1. **Distribution selection**: Analysis using uniform distribution $U[0,1]$ and power-law distribution $x^2$ 2. **Parameter settings**: $\lambda = 2, 5$; $\delta = 0, 0.01, 0.05$, etc. 3. **Numerical solution**: Obtaining steady-state distribution by solving implicit equation (5) ### Evaluation Metrics 1. **Expected buyer utility**: $Z(x) = [x - b(x)]H(F(x))$ 2. **Winning probability**: $H(g) = \frac{W(g)}{1-(1-W(g))(1-\delta)}$ 3. **Average pool size**: $E[N_t] = \frac{\lambda - (1-p_0)(1-\delta)}{\delta}$ ### Implementation Details - Using probability generating function methods to solve Markov chain steady-state distributions - Computing limit values through L'Hôpital's rule - Numerical methods for solving systems of differential equations ## Experimental Results ### Main Results #### 1. Fixed-Price Mechanism Verification Figure 1 shows that Bitcoin mempool snapshots perfectly align with the paper's fixed-price predictions, validating the practical applicability of the theory. #### 2. Beneficial Effects of Uncertainty **Theorem 4 (Bidding Decreases with Uncertainty)**: There exist $\delta^* > 0$ and $X^* \geq X(\lambda)$ such that: - For $\delta \leq \delta^*$ and $x \leq X^*$, $b(x|\lambda,\delta) \leq b(x|\lambda,0)$ - Bidding reduction is largest at $x = X(\lambda)$ **Theorem 5 (Expected Buyer Utility Increases with Uncertainty)**: Under identical conditions, expected buyer utility $Z(x|\lambda,\delta) \geq Z(x|\lambda,0)$. #### 3. Numerical Results - When $\lambda = 2, \delta = 0.01$, average pool size is approximately 101 - Steady-state distribution approximates Poisson distribution but with different characteristics - Winner density function exhibits "blurred" threshold characteristics ### Ablation Studies 1. **Parameter sensitivity**: Analyzing the impact of different $\lambda$ and $\delta$ values on results 2. **Distribution effects**: Comparing behavioral differences between uniform and power-law distributions 3. **Multi-winner extension**: Validating applicability of results in cases with $\mu$ winners ### Case Analysis The Bitcoin transaction fee market perfectly demonstrates the fixed-price mechanism predicted by the paper, with high-fee transactions confirming rapidly and low-fee transactions either waiting extended periods or being dropped. ## Related Work ### Classical Sequential Auction Theory - **Milgrom & Weber (2000)**: Established foundational theory for finite sequential auctions - **Weber (1981)**: Analyzed variants with interdependent valuations - **Krishna (2009)**: Provided systematic survey of auction theory ### Dynamic Auction Research - **Lavi & Nisan (2004)**: Studied time-varying auctions - **Said (2011)**: Analyzed buyers and items with stochastic arrivals - **Che & Choi (2025)**: Discussed optimal auction design in dynamic stochastic environments ### Blockchain Auction Applications - **Ferreira et al. (2021)**: Proposed fixed-price mechanisms for Ethereum - **Nisan (2023)**: Demonstrated price oscillations in cryptocurrency environments ## Conclusions and Discussion ### Main Conclusions 1. **Fixed-price convergence**: Infinite-horizon auctions without uncertainty converge to fixed-price mechanisms 2. **Dual effects of uncertainty**: Uncertainty benefits most buyers but may reduce auctioneer utility 3. **Universality**: Results apply to various uncertainty models 4. **Practical relevance**: Theoretical predictions align closely with actual markets like Bitcoin ### Limitations 1. **Price announcement effects**: With uncertainty, price announcements affect strategies, increasing analytical complexity 2. **Homogeneity assumptions**: Model assumes buyer homogeneity; actual heterogeneity may exist 3. **Parameter stability**: Requires model parameters to remain stable over time 4. **Complete information assumption**: Assumes buyers know all model parameters ### Future Directions 1. **Price announcement mechanisms**: Analyze complete impact of price announcements on auctions with uncertainty 2. **Heterogeneous buyer models**: Extend to heterogeneous buyer populations 3. **Dynamic parameters**: Consider time-varying arrival rates and uncertainty parameters 4. **Multidimensional auctions**: Extend to multidimensional value spaces ## In-Depth Evaluation ### Strengths 1. **Theoretical innovation**: First systematic analysis of infinite-horizon sequential auctions with complete theoretical framework 2. **Mathematical rigor**: Provides rigorous mathematical proofs using Markov process theory 3. **Counterintuitive findings**: Discovers the counterintuitive result that uncertainty benefits buyers 4. **Practical application**: Provides compelling theoretical explanations for real markets like Bitcoin 5. **Strong generality**: Results apply to broad classes of uncertainty models ### Weaknesses 1. **Computational complexity**: Bidding functions with uncertainty require numerical solutions; lack closed-form solutions 2. **Assumption limitations**: Homogeneous buyer and complete information assumptions may be overly idealized 3. **Insufficient auctioneer analysis**: Analysis of auctioneer utility is relatively brief 4. **Missing dynamic analysis**: Lacks analysis of dynamic adjustment processes when parameters change ### Impact 1. **Theoretical contribution**: Opens new research directions in auction theory 2. **Practical value**: Provides design guidance for digital platforms and blockchain applications 3. **Interdisciplinary impact**: Connects auction theory, Markov processes, and blockchain economics 4. **Policy implications**: Provides theoretical foundation for regulators to understand digital markets ### Applicable Scenarios 1. **Digital platform auctions**: Search engine ad bidding, cloud resource allocation 2. **Blockchain economics**: Transaction fee markets, MEV auctions 3. **Traditional continuous auctions**: Flower markets, fish markets and other periodic auctions 4. **Financial markets**: High-frequency trading, market-maker competition ## References 1. Milgrom, P., & Weber, R. (2000). A theory of auctions and competitive bidding II. 2. Krishna, V. (2009). Auction theory. Academic press. 3. Weber, R. J. (1981). Multiple-object auctions. 4. Ferreira, M. V. X., et al. (2021). Dynamic posted-price mechanisms for the blockchain transaction-fee market. 5. Nisan, N. (2023). Serial monopoly on blockchains. --- Through rigorous mathematical modeling and in-depth theoretical analysis, this paper provides an important theoretical foundation for understanding persistent auction mechanisms in the modern digital economy. The discovered beneficial effects of uncertainty on auction outcomes have significant implications for auction design.