Abstract
In a two-player zero-sum graph game the players move a token throughout a graph to produce an infinite path, which determines the winner or payoff of the game. Traditionally, the players alternate turns in moving the token. In bidding games, however, the players have budgets, and in each turn, we hold an "auction" (bidding) to determine which player moves the token: both players simultaneously submit bids and the higher bidder moves the token. The bidding mechanisms differ in their payment schemes. Bidding games were largely studied with variants of first-price bidding in which only the higher bidder pays his bid. We focus on all-pay bidding, where both players pay their bids. Finite-duration all-pay bidding games were studied and shown to be technically more challenging than their first-price counterparts. We study for the first time, infinite-duration all-pay bidding games. Our most interesting results are for mean-payoff objectives: we portray a complete picture for games played on strongly-connected graphs. We study both pure (deterministic) and mixed (probabilistic) strategies and completely characterize the optimal sure and almost-sure (with probability 1) payoffs that the players can respectively guarantee. We show that mean-payoff games under all-pay bidding exhibit the intriguing mathematical properties of their first-price counterparts; namely, an equivalence with random-turn games in which in each turn, the player who moves is selected according to a (biased) coin toss. The equivalences for all-pay bidding are more intricate and unexpected than for first-price bidding.
Introduction
Traditional graph games, fundamental to software verification and reactive synthesis, typically involve players alternating turns. Bidding games introduce a competitive resource-management layer: players possess finite budgets and auction for the right to move the token at each step. While first-price bidding (where only the winner pays) has been extensively studied, this work explores all-pay bidding. In this model, both players pay their bids regardless of the outcome, mirroring real-world scenarios like R&D races or political lobbying where resources are consumed simply by participating.
This paper provides the first complete characterization of infinite-duration all-pay bidding games, specifically focusing on mean-payoff objectives, where players aim to maximize the long-run average value of visited vertices.
Methodology: The Random-Turn Equivalence
The core discovery is that complex bidding games are mathematically equivalent to random-turn games. In these games, the player who moves is determined by a (possibly biased) coin toss rather than an auction.
To bridge these two worlds, the authors utilize:
- Martingale Theory: Using the Azuma-Hoeffding inequality, they prove that short-term "unlucky" bids in mixed strategies cancel out over an infinite timeline, allowing players to guarantee payoffs "almost surely."
- Potential Functions: Vertices are assigned "strength" values, and bids are scaled based on the relative importance of the current vertex to the overall objective.
- Shift Functions: A logarithmic shift function ($\lambda$) is used to construct strategies where bids depend on the current vertex and the remaining budget ratio.
Key Results and Characterization
The research reveals an elegant mathematical structure emerging at the limit of infinite duration. The "messiness" of finite games disappears, leading to clean equivalences with random-turn games ($RT(\mathcal{G}, p)$), where $p$ is the probability of the "Max" player moving.
Richman vs. Poorman Bidding
- Richman Bidding (Winner pays loser): Deterministic strategies are ineffective; an opponent can eventually deplete a fixed-strategy player's budget. Under optimal mixed play, the game becomes "fair" ($p=0.5$), regardless of the initial budget ratio.
- Poorman Bidding (Payments to a bank): Here, budget ratios grant a deterministic advantage. The payoff is strictly tied to the budget ratio $r$. For instance, if Max has a higher budget ($B_0 > C_0$), he can guarantee a payoff equivalent to a coin toss with probability $p = 1 - \frac{C_0}{2B_0}$.
The authors also demonstrate that deciding if a player can guarantee a certain payoff is in NP $\cap$ coNP, similar to standard stochastic games. Furthermore, they successfully reduced parity objectives to mean-payoff games.
Limitations and Future Outlook
While mean-payoff games on strongly-connected graphs are now well-understood, several challenges remain:
- Reachability Games: Determining the winner in games where the goal is simply to reach a target node remains an open problem for all-pay bidding.
- Discrete Bidding: Real-world money is discrete. The current continuous model avoids tie-breaking complexities that could significantly alter strategic landscapes in discrete settings.
- General Graphs: Extending these results beyond strongly-connected graphs requires first solving the reachability problem.
Summary updated