Bidding Games with Rewards: Taming Infinite Configuration Space
2026-08-31 • Computer Science and Game Theory
Computer Science and Game Theory
AI summaryⓘ
The authors study a type of game where two players bid with budgets to move a token on a graph, and players can earn more budget as rewards at certain positions. This creates an infinite number of game states because budgets can keep changing, making it hard to analyze. They developed a new method to ignore less useful parts of the game to focus on a manageable, finite subset and approximate the solution. They also identify a special case where a winning strategy can be found efficiently.
bidding gamesgraph gamesdiscrete poorman biddingreachabilityinfinite configuration graphapproximationcontinuous bidding gamesstrategyNP complexityEXP complexity
Authors
Matan Pinkas
Abstract
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.