Abstract
This paper investigates bidding graph games under partial information, where players bid from finite budgets to move a token on a graph. We focus on one-sided partial information where one player's budget is drawn from a known distribution. We provide optimal strategies for both Richman and Poorman bidding mechanisms and reveal a significant theoretical result: these games do not necessarily possess a single value under pure strategies, highlighting a gap between what players can guarantee and prevent.
Introduction
Graph games are a foundational tool in computer science, particularly for reactive synthesis—the process of automatically creating a controller that satisfies a specification regardless of an adversarial environment's actions. While traditional models assume full information, real-world scenarios like advertising auctions or resource competition often involve uncertainty. This work addresses "one-sided partial information," where Player 1 (the controller) knows only the probability distribution of Player 2's budget.
Methodology and the Bowtie Game
The authors analyze two main bidding mechanisms: Richman Bidding (winner pays the loser) and Poorman Bidding (winner pays the bank). To solve these games, they leverage an equivalence between bidding games and random-turn games, where a coin flip determines the next mover.
A central tool in this analysis is the "bowtie" game, a minimal two-vertex graph that serves as a benchmark for illustrating complex dynamics in bidding games.
In the Poorman setting, the authors introduce a "wallet" strategy. The partially informed player (Max) partitions their budget into virtual accounts, using them sequentially to play optimally against increasing levels of the opponent's possible budget. This hedging ensures a "floor" payoff for every possible budget the opponent might have.
Key Insights
The transition from full to partial information varies significantly by bidding type:
- Richman Bidding: The optimal payoff is independent of the initial budget ratio, making the extension to partial information mathematically straightforward.
- Poorman Bidding: The budget ratio is critical. Partial information leads to potential resource waste (overbidding) or lost turns (underbidding) due to misjudging the opponent's funds.
- Strategy Revelation: Surprisingly, for the fully informed player (Min), the optimal strategy is often to "reveal" their budget immediately by playing as if the opponent knows everything. They gain nothing by trying to hide their wealth.
Key Results: The Value Gap
The most significant theoretical finding is that these games lack a unique "value" under pure strategies. In the bowtie game with a specific budget distribution, the partially informed player can guarantee a payoff of 1/3, but the fully informed player can only guarantee the payoff stays below 5/12. This gap between what Player 1 can guarantee and what Player 2 can prevent is a rare property in zero-sum games, highlighting how partial information fundamentally changes the game's nature.
Limitations and Future Work
The current results are primarily for strongly-connected graphs. Extending this to general directed graphs is significantly more complex. Additionally, the authors suggest that the "gap" in the game's value might disappear if players use mixed strategies (randomizing their bids). Finally, games with two-sided uncertainty—where neither player knows the other's budget—remain an open challenge.
Summary updated