Computing Threshold Budgets in Discrete-Bidding Games

Abstract

In a two-player zero-sum graph game, the players move a token throughout the graph to produce an infinite play, which determines the winner of the game. Bidding games are graph games in which in each turn, an auction (bidding) determines which player moves the token: the players have budgets, and in each turn, both players simultaneously submit bids that do not exceed their available budgets, the higher bidder moves the token, and pays the bid to the lower bidder. We distinguish between continuous- and discrete-bidding games. In the latter, the granularity of the players' bids is restricted, e.g., bids must be given in cents. Continuous-bidding games are well understood, however, from a practical standpoint, discrete-bidding games are more appealing. 
In this paper we focus on discrete-bidding games. We study the problem of finding threshold budgets; namely, a necessary and sufficient initial budget for winning the game. Previously, the properties of threshold budgets were only studied for reachability games. For parity discrete-bidding games, thresholds were known to exist, but their structure was not understood. We describe two algorithms for finding threshold budgets in parity discrete-bidding games. The first algorithm is a fixed-point algorithm, and it reveals the structure of the threshold budgets in these games. Second, we show that the problem of finding threshold budgets is in NP and coNP for parity discrete-bidding games. Previously, only exponential-time algorithms where known for reachability and parity objectives. A corollary of this proof is a construction of strategies that use polynomial-size memory.