Infinite-Duration Bidding Games

We consider two-player zero-sum ”graph games” which proceed as follows. A token is placed on one of the vertices of a graph, and the players move the token to produce an infinite path, which determines the winner or payoff of the game. Infinite-duration graph games have numerous applications in formal methods and AI, and have deep connections with foundations of logic. Traditional graph games are "turn based": the players alternate turns in moving the token (as in Chess or tic-tac-toe).

“Bidding games" are graph games in which in each turn, an 'auction' (bidding) determines which player moves the token. We consider several concrete bidding mechanisms and study their effect on the properties of the game. Specifically, we show equivalences between bidding games and “random-turn” games: in each turn, the player who moves is chosen randomly. Interestingly, while for finite-duration games, an equivalence is known only for one bidding mechanism called “Richman bidding”, for infinite-duration games, we observe intricate equivalences for a wide range of bidding mechanisms. Finally, I will present results on "discrete" bidding games in which bids are restricted to be integers (i.e., bids are given in coins). 

No prior knowledge will be assumed.