Bidding Games with Rewards: Taming Infinite Configuration Space
TL;DR
A novel technique to eliminate plays with suboptimal infixes is introduced, which 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.
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.