Bidding Mechanisms in Graph Games

In two-player games on graphs, the players move a token through a graph to produce an infinite path, which determines the winner or payoff of the game. We study em bidding games in which the players bid for the right to move the token. Several bidding rules were studied previously. In em Richman bidding, in each round, the players simultaneously submit bids, and the higher bidder moves the token and pays the other player. em Poorman bidding is similar except that the winner of the bidding pays the "bank" rather than the other player. em Taxman bidding spans the spectrum between Richman and poorman bidding. They are parameterized by a constant τ ∈ [0,1]: portion τ of the winning bid is paid to the other player, and portion 1-τ to the bank. We present, for the first time, results on em infinite-duration taxman games. Our most interesting results concern quantitative taxman games, namely em mean-payoff games, where poorman and Richman bidding differ. A central quantity in these games is the em ratio between the two players' initial budgets. While in poorman mean-payoff games, the optimal payoff a player can guarantee depends on the initial ratio, in Richman bidding, the payoff depends only on the structure of the game. In both games the optimal payoffs can be found using (different) probabilistic connections with em random-turn based games in which in each turn, a coin is tossed to determine which player moves. The payoff with Richman bidding equals the payoff of a random-turn based game with an un-biased coin, and with poorman bidding, the coin is biased according to the initial budget ratio. We give a complete classification of mean-payoff taxman games using a probabilistic connection. Our results show that Richman bidding is the exception; namely, for every τ <1, the value of the game depends on the initial ratio.