Abstract
This paper introduces all-pay bidding games on graphs, a novel framework for modeling zero-sum contests where players expend non-refundable resources to influence the state of a game. Unlike traditional first-price bidding games, all-pay settings require every participant to pay their bid regardless of the outcome, mirroring real-world scenarios like patent races, political campaigning, and blockchain fee wars. We demonstrate that while these games exhibit significant complexity—often requiring probabilistic strategies with infinite support—they can be efficiently approximated on Directed Acyclic Graphs (DAGs) using a Fully Polynomial-Time Approximation Scheme (FPTAS).
Introduction
In many competitive environments, the cost of participation is incurred regardless of success. Examples abound in biological mate selection, patent races, and "war of attrition" scenarios in distributed systems. Despite their prevalence, formal models for such dynamic, stateful, all-pay contests have been lacking. This research addresses this gap by defining quantitative reachability games on graphs where two players bid from finite budgets to move a token toward their respective target leaf nodes.
Methodology
The study employs a combination of theoretical analysis and algorithmic development. The authors define a mathematical recurrence to identify the "surely-winning threshold ratio"—the minimum budget ratio required for Player 1 to guarantee a win with 100% certainty.
For games played on Directed Acyclic Graphs (DAGs), the authors developed an FPTAS that discretizes the continuous space of possible bids. By breaking budgets into small increments (of size $\epsilon$), the algorithm can approximate the game's value within a provable error margin. This is particularly useful as optimal strategies in all-pay games often involve complex probability distributions rather than single deterministic bids.
Key Insights: The Complexity of All-Pay Bidding
A central finding is the "complexity jump" when moving from first-price to all-pay bidding. In all-pay auctions, the loser's budget depletion is a strategic factor, turning every round into a potential war of attrition.
One of the most striking theoretical results is the existence of strategies with infinite support. In a simple "win three times in a row" game, the optimal strategy may require a player to select their bid from a distribution across an infinite set of values. Furthermore, the budget ratios needed to guarantee a win can be irrational numbers, complicating exact computational solutions.
Results and Evaluation
The authors evaluated their framework on several canonical game types, including Tic-Tac-Toe and synthetic "Win $n$ in a Row" (WnR) games.
- Computational Complexity: Finding the surely-winning threshold is linear time for DAGs but resides in PSPACE for general graphs using the existential theory of the reals.
- WnR(2) Solution: The authors provided a complete mathematical characterization for the "win twice in a row" game, proving that if Player 1's budget ratio is $1 + x$ (where $x \in (1/(n+1), 1/n]$), the value of the game is exactly $1/(n+1)$.
- Approximation Performance: The FPTAS implementation demonstrated high accuracy, with narrow gaps between upper and lower bounds on game values.
As shown in Figure 4, the game value functions for WnR games often exhibit step-wise behavior (e.g., $G(1,2)$), which transitions toward more continuous curves as the game complexity increases. This illustrates the deep mathematical "phase transition" that occurs as the number of required consecutive wins grows.
Conclusion
This work establishes a rigorous foundation for all-pay bidding games on graphs. While the transition from DAGs to general graphs with cycles remains a challenge, the developed FPTAS provides a practical tool for analyzing a wide class of competitive scenarios. Future research will focus on extending these results to infinite-duration games and further exploring the mathematical implications of irrational thresholds and infinite strategy support.
Summary updated