Computing Threshold Budgets in Discrete-Bidding Games

In a two-player zero-sum graph game, the players move a token throughout the graph to produce a finite or infinite path, which determines the winner of the game. Bidding games are graph games in which the players have budgets, and in each turn, an auction determines which player moves the token. One characterisation of bidding games refers to the allowed bids: in continuous bidding, bids can be arbitrarily small, whereas in discrete bidding, the granularity of the bids is restricted. Discrete bidding is thus more appropriate for most practical applications. We focus on qualitative objectives. Both continuous- and discrete-bidding games are known to be determined, which in bidding games is captured by the concept of a threshold budget: roughly, a budget that is necessary and sufficient for a player to win the game from a given vertex. We study the complexity of computing the threshold budgets in discrete-bidding games. For reachability objectives, threshold budgets in continuous-bidding games satisfy an average property: the budget at a vertex is the average of two of its neighbours. Moreover, there is a unique function with the average property. Uniqueness immediately implies that the complexity of finding threshold budgets is in NP and coNP. Under discrete-bidding, threshold budgets are known to satisfy a discrete version of the average property. We show, somewhat surprisingly, that there can be more than one function satisfying the average property. This complicates the search for threshold budgets. We study, for the first, time, discrete-bidding games in which the sum of budgets is given in binary and show that finding threshold budgets is in NP and NP. Our algorithm uses a careful reduction to turn-based reachability games that is based on an intricate analysis of the optimal strategies of the players. We turn to parity and B{\"u}chi objectives. Under continuous bidding, parity bidding games reduce easily to reachability games. Under discrete-bidding, however, it was known that a key property of the reduction fails. We develop a fixed-point algorithm that takes a very different approach from the one in continuous-bidding games. The algorithm reveals the structure of threshold budgets in discrete-bidding games. We are currently working on employing this structure in order to show membership in NP and coNP. In the future, we expect that our techniques will be useful in studying other variants of discrete bidding games, e. g. mean-payoff games, which exhibit interesting properties under continuous bidding but have never been studied under discrete bidding. Joint work with Guy Avni.

Authors

• Guy Avni

Keywords

No keywords are indexed for this paper.