Source-linked AI summary
Bidding Games with Rewards: Taming Infinite Configuration Space
Matan Pinkas
TL;DR
Bidding games with rewards introduce budget replenishment into discrete poorman bidding, creating infinitely many possible configurations and new threshold-computation challenges. The paper eliminates plays with disadvantaged loops, analyzes a finite exponential segment via approximation to continuous poorman bidding, and studies a subclass with B-growth strategies. It proves an EXP threshold-solving result and reports that some arenas give the reachability player a substantial advantage.
Problem
Rewards can make budgets grow, so DPBGr may visit infinitely many configurations and lose the polynomial play-length bound available without rewards.
Method
The paper eliminates disadvantaged loops, restricts analysis to a finite segment of the configuration graph, and uses long-play approximations to continuous poorman bidding strategies.
Results
The reachability threshold problem for DPBGr is in EXP, and some arenas give the reachability player a substantial advantage.
Takeaways & Limitations
A finite exponential analysis can solve threshold questions despite the infinite configuration space, while B-growth strategies guarantee wins in a subclass of games.
Takeaways & Limitations
The analysis assumes players avoid disadvantaged loops when possible, although some games can force a player to form one.
Abstract
from arXiv · showhide
Bidding games are graph games in which a token is placed on a vertex, each player starts with an initial budget, and a simultaneous auction determines which player moves the token; the players' budgets are then updated accordingly. Motivated by scenarios such as resource-allocation systems in which agents receive periodic rewards (e.g., credits, energy) while competing for control, we introduce and study bidding games with rewards, in which, at each vertex, players may receive additional budget, incentivizing desired behaviors. We focus on reachability discrete poorman bidding games with rewards (DPBGr). The main challenge when compared to discrete bidding games without rewards is that the configuration graph is infinite. To this end we introduce a novel technique to eliminate plays with suboptimal infixes. This enables focusing on a finite part of the infinite configuration graph in order to solve the game via approximation to continuous bidding games with overall complexity in EXP. Finally, we discuss a new type of strategy, usable on a subclass of DPBGr, which guarantee a winning strategy for the reachability player. Membership in this subclass is shown to be in NP.
1 Introduction
The paper introduces bidding games with rewards, focusing on reachability discrete poorman bidding games where budgets can be replenished. Rewards can change both game outcomes and optimal strategies, while making threshold computation harder because infinitely many configurations may be visited.
- Motivation: Bidding games resolve graph traversal through simultaneous bids, with the winner selecting the next vertex and budgets updated by the bidding mechanism.The paper distinguishes discrete and continuous bids and several update mechanisms, including poorman bidding, where the winner pays the bank.
- Motivation: Bidding games with rewards let players receive additional budget at vertices, modeling resource-allocation settings with replenished credits, energy, or tokens.The paper focuses on discrete poorman bidding with rewards and reachability objectives.
- Examples: Rewards may change the winner: Sam can sustain an indefinitely repeating cycle because he receives rewards along the loop.The example specifically gives Sam a reward at v1, enabling repeated cycling between v0 and v1.
- Examples: Rewards may also change the optimal strategy: without rewards Roxy wins through v4, but with rewards she must use v1 to gain enough budget for three consecutive wins.The rewarded strategy makes the former v4 route losing because Roxy cannot outbid Sam there.
- Challenges: Unlike reward-free discrete poorman games, DPBGr budgets may grow, so plays can visit infinitely many configurations and need not reach targets within a polynomial number of steps.The configuration graph includes the current vertex and both budgets; rewards remove the finite-play bound used without rewards.
- Approach: The paper computes reachability thresholds by restricting attention to reasonably optimal plays, then analyzing a finite exponential segment whose long-play bids approximate continuous poorman strategies.The authors introduce disadvantaged loops to eliminate suboptimal infixes and establish an EXP upper bound, while noting the bound may not be tight.
2 Preliminaries
The preliminaries formalize bidding games, their configurations, bidding mechanisms, strategies, and threshold questions. They distinguish discrete bidding from continuous bidding and budget thresholds from threshold ratios.
- Game model: A bidding game consists of a directed graph, a winning objective, and a bidding mechanism specifying bid granularity, budget updates, and tie breaking.Discrete bids range over N, whereas continuous bids range over nonnegative real numbers.
- Tie breaking: Tie breaking is necessary in discrete games and can affect determinacy, so the paper assumes mechanisms for which the relevant games are determined.Continuous games may avoid ties because arbitrarily small bids are allowed.
- Configurations and bids: A configuration records the current vertex and the two players’ budgets, while a bid selects a successor and an amount not exceeding the bidder’s budget.A bidding round determines the winner, successor, and updated budgets.
- Budget updates: Under poorman bidding, the winning player pays the bid to the bank and the losing player’s budget remains unchanged.The update mechanism determines the new budgets after each round.
- Strategies: A strategy specifies both the desired successor and the bid as a function of play history, and it is winning when every compatible play satisfies the player’s objective.The framework defines histories, consistency of plays with strategies, and winning strategies for both players.
- Threshold problems: The threshold budget is the minimum budget player 0 needs against a fixed opponent budget, whereas continuous games use a threshold ratio because budgets scale linearly.The threshold ratio is the minimum fraction of total budget required from a vertex.
3 Bidding Games with rewards
The paper defines bidding games with rewards by adding vertex-based budget increases to the bidding update. It then specializes to reachability DPBGr and outlines a solution based on disadvantaged loops and finite configuration segments.
- Definition: A bidding game with rewards augments the ordinary game tuple with reward functions rι: V → N for both players.Rewards are assigned to vertices and added after bidding updates the token position and budgets.
- Configuration space: The paper models games on an infinite configuration graph whose vertices include the graph position and both budgets.Rewards can cause infinitely many configurations to be visited because budgets may grow.
- Motivation: Reward updates can increase total budgets in mechanisms such as poorman bidding, counteracting the budget decay that occurs without rewards.This makes objectives such as Büchi objectives more meaningful in some discrete poorman games.
- Scope: The analysis focuses on discrete poorman bidding games with rewards and a reachability objective, with Roxy as the reachability player and Sam as the safety player.The target is assumed to be a single self-looping vertex with reward −1 for each player.
- Solution outline: The threshold-solving plan first excludes disadvantaged loops, then studies sufficiently large budgets and uses a finite segment to compute thresholds in EXP.The paper presents this as the route to solving the reachability threshold problem.
4 Disadvantaged loops
The section identifies disadvantaged loops as cycles that favor one player and shows that, when alternatives exist, forming one reflects suboptimal play. Avoiding such loops makes sufficiently long plays analyzable through growing budgets and continuous-game reasoning.
- Definitions: A disadvantaged loop is a repeated-vertex segment whose budget changes favor Sam or Roxy under the stated inequalities.Sam-disadvantaged loops compare Bs[i] and Bs[j] against Br[i] and Br[j]; Roxy’s definition is symmetric and also treats unchanged budgets as disadvantaged for her reachability objective.
- Suboptimal play: If an alternative strategy avoids a player’s disadvantaged loop, the strategy producing that loop is suboptimal.The comparison follows because the favored player has no fewer options after the loop, while repeating an unchanged loop benefits the safety objective.
- Suboptimal play: The analysis requires alternative strategies because some games can force one player to form a disadvantaged loop.When no alternative exists, the paper determines the outcome from whether the target remains reachable or a player can force the opponent’s disadvantaged loops.
- Consequences: Avoiding disadvantaged loops implies that sufficiently long plays produce very large player budgets, while non-disadvantaged cycles are classified as upward or downward loops.The paper uses this growth behavior to reason about repeated vertices and later extend the loop analysis to continuous poorman bidding games.
- Continuous extension: In continuous poorman bidding games, the ratio-shift of a repeated-vertex segment determines which player is disadvantaged.A nonpositive ratio-shift yields a Roxy-disadvantaged loop, while a positive ratio-shift yields a Sam-disadvantaged loop; consequently, every loop is disadvantaged for one player except the zero-budget case.
5 Approximation of DPBGr via CPBG
The paper approximates reachability DPBGr with continuous poorman bidding games after sufficiently long, well-behaved play causes budgets to grow. This supports winner determination within an exponential number of rounds and an EXP decision procedure.
- Approximation framework: After sufficiently long play without disadvantaged loops, DPBGr budgets grow and optimal bids become more predictable through approximation to continuous poorman bidding games.The continuous game uses the same graph and objective but replaces discrete bids with continuous bidding.
- Away from the threshold: For sufficiently large Br, Br/(Br+Bs) ≥ ThGC(v)+ε gives Roxy a winning DPBGr strategy within exp(n) bidding rounds.The required budget is at most exponential in the number of vertices when ε is specified with at most linearly many bits in n.
- Away from the threshold: For sufficiently large Br, Br/(Br+Bs) ≤ ThGC(v)−ε gives Sam a winning strategy.These two share conditions cover cases where Roxy’s budget share is separated from the continuous-game threshold by ε.
- Near the threshold: When the budget share is close to ThGC(v), loop analysis and reasonable play establish a ceiling on both players’ budgets.The paper combines upward-loop analysis with the fact that players must eventually spend more than their rewards or lose.
- Complexity: The resulting DPBGr winning-strategy verification and threshold computation are in EXP when bids and budgets are binary-encoded.The verification procedure explores configurations through the exponential duration bound and propagates outcomes backward.
6 Growth-Strategy
Growth strategies let Roxy accumulate budget while controlling play, and in reachability DPBGr this yields winning strategies from sufficiently large initial budgets. The subclass is structurally restricted and can be recognized in NP.
- Growth-Strategy: A B-growth strategy starts from a budget bound B and guarantees bounded growth behavior across extended plays, regardless of Sam’s initial budget.The definition quantifies over every x ∈ N and requires the play to satisfy the growth conditions after some m > 1.
- Growth-Strategy: Growth conditions constrain loops by requiring Roxy’s budget not to decrease, bounding its multiplicative increase, and forcing Sam’s budget to decrease when Roxy’s budget stagnates.The paper also assumes the target has only self-edges and reward rs(t) = −1.
- Growth-Strategy: A 2-growth strategy can move from v0 to v1 with bid 2 and then to t with bid 3, while deviations by Sam produce loops satisfying the growth bounds.In the example, one loop has ratio growth m = 3, and any other loop has that ratio or worse.
- Growth-Strategy: If some vertex reachable from u cannot reach the target, then no B-growth strategy exists for u.Sam can repeatedly win bids to visit that vertex when his initial budget is sufficiently large relative to B.
- Growth-Strategy: If Roxy has a B-growth strategy from v0, she has a winning strategy from every configuration (v0, Br, Bs) with Br ≥ B.The construction first builds Roxy’s budget and then forces Sam to deplete his budget faster.
- Growth-Strategy: When every vertex reaches t and Roxy receives positive rewards, her threshold is zero at every vertex; deciding whether a B-growth strategy exists is in NP.The always-zero bidding strategy witnesses growth under these conditions.
7 Discussion
The discussion reports results for reachability DPBGr, including EXP threshold complexity and an NP-recognizable subclass with winning growth strategies. It also presents disadvantaged loops as a reusable technique for broader bidding-game generalizations.
- Discussion: The reachability threshold problem for DPBGr is in EXP, using finite analysis after excluding plays with suboptimal infixes and approximating continuous bidding games.The authors note that EXP may not be a lower bound because sufficiently large budgets should make discrete bids more similar to CPBG bids.
- Discussion: Disadvantaged loops provide a technique for enforcing reasonably optimal play that may apply to other bidding-game generalizations and objectives.The paper explicitly identifies applicability beyond the setting studied here.
- Discussion: In some arenas, the reachability player has a substantial advantage.
A Omitted Proofs
The omitted proofs establish determinacy for relevant DPBGr settings and develop budget-based strategies that approximate continuous-game strategies. They also show that growth strategies yield winning strategies and that deciding whether one exists is in NP.
- Determinacy: Tie-unaware transducers make Müller DPBGr determined through an R-concurrent-game argument.The proof uses the corresponding determinacy result for locally determined R-concurrent games.
- Growth strategies: Each repeated shortest-path attempt decreases Sam’s budget faster than Roxy’s, causing Roxy’s slush fund to grow until the strategy remains well defined.The proof states that Sam’s budget decreases at least 3 times faster than Roxy’s in the discrete approximation.
- Large-budget approximation: Large budgets let Roxy transfer continuous reachability strategies to discrete bidding games with rewards.The approximation adjusts bids for integer constraints and rewards, requiring budgets at most exponential in the number of vertices.
- Growth strategies: A B-growth strategy guarantees a winning strategy from every initial configuration whose reachability budget satisfies Br ≥ B.The construction first grows Roxy’s budget to the threshold, then follows an escalating-bid shortest-path strategy toward the target.
- Complexity: Every reachability DPBGr position admits a positional growth strategy with a threshold bounded by B + Rr.This positional form supplies the witness used in the NP-membership proof.
- Complexity: Deciding whether Roxy has a B-growth strategy from a vertex is in NP.Verification uses a witness threshold and positional strategy, then checks weighted graph paths by breadth-first search.