Discrete Two Player All-Pay Auction with Complete Information

Marcin Dziubinski, Krzysztof JahnIJCAI 2023 · DOI

TL;DR

This paper tackles the complexities of all-pay auctions when players can only choose discrete effort levels, a more realistic scenario than continuous models. They provide a complete characterization of Nash equilibria, showing they are subsets of a related game and are generally not unique but interchangeable. The findings reveal how discreteness can benefit weaker players and offer insights into when continuous approximations hold.

What Problem Does This Paper Address?

All-pay auctions are fundamental models for understanding competition where everyone pays for their effort, but only the highest bidder wins. Think of political campaigns, R&D races, or even Bitcoin mining. While continuous models of effort have been well-studied, real-world scenarios often involve discrete choices – you can't spend half a dollar or a quarter of a computational cycle. This discreteness can significantly alter equilibrium behavior, potentially leading to inaccurate predictions if continuous models are naively applied. The paper aims to bridge this gap by fully characterizing the equilibria in discrete all-pay auctions and understanding how they differ from their continuous counterparts.

Methods

The authors leverage a clever connection between discrete all-pay auctions and discrete General Lotto games. They first establish that equilibria in the all-pay auction are a subset of equilibria in a corresponding General Lotto game. Then, they utilize existing complete characterizations of equilibria in discrete General Lotto games to derive the full characterization for the discrete all-pay auction. This involves analyzing specific probability distributions (like "uniform on odd numbers" and "uniform on even numbers") and their convex combinations, which form the building blocks of these equilibria. They present detailed theorems for different cases based on the players' valuations, particularly focusing on whether half of the weaker player's valuation is an integer.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Discreteness Matters: The paper demonstrates that discrete effort levels can lead to different equilibrium outcomes than continuous models, particularly affecting the weaker player.
  • Weaker Player Advantage: Discreteness can benefit the weaker player, allowing them to secure a positive payoff even when their valuation is close to the stronger player's.
  • Equilibria are Not Always Unique: While continuous models often yield unique equilibria, the discrete case can have a continuum of equilibria, though these are "interchangeable" (meaning players can't improve their payoff by unilaterally switching to another equilibrium strategy).
  • Connection to General Lotto Games: The paper elegantly shows that all-pay auction equilibria are a subset of General Lotto game equilibria, allowing them to leverage existing results.
  • Valuation Parity is Key: The nature of equilibria (unique vs. continuum, specific distributions) heavily depends on whether players' prize valuations are even or odd numbers.

Key Results

The paper provides a complete characterization of mixed strategy Nash equilibria for two-player discrete all-pay auctions with complete information. They detail specific equilibrium strategies and payoffs for various scenarios, particularly distinguishing cases where $v_2/2$ (half the weaker player's valuation) is an integer versus not.

For instance, when valuations are equal ($v_1 = v_2$), equilibria involve convex combinations of uniform distributions on odd and even numbers. When valuations differ, the weaker player often mixes between zero effort and a range of positive efforts, while the stronger player employs more complex mixed strategies.

The paper also shows that equilibrium payoffs are generically unique, unless at least one player's valuation is an even number, in which case a continuum of payoffs is possible.

Limitations and Future Work

The paper focuses on two-player discrete all-pay auctions. While it provides a comprehensive analysis for this setting, it acknowledges that real-world scenarios can involve more players. Future work could extend these findings to multi-player games. Additionally, the paper primarily deals with risk-neutral players; exploring the impact of risk aversion in discrete all-pay auctions would be a valuable extension. The authors also suggest further investigation into the comparative statics of these equilibria, particularly how changes in valuations affect payoffs and strategies.

Summary updated

BibTeX
@inproceedings{dziubinski2023discrete,
  author = {Marcin Dziubinski and Krzysztof Jahn},
  title = {{Discrete Two Player All-Pay Auction with Complete Information}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.24963/ijcai.2023/296},
}
Figure