
arXiv: 1905.03835
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 $τ\in [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.
FOS: Computer and information sciences, bidding games, Computer Science - Logic in Computer Science, Bidding games, taxman bidding, Auctions, bargaining, bidding and selling, and other market models, parity games, Mean-payoff games, Poorman bidding, Computer Science - Computer Science and Game Theory, Richman bidding, stochastic games, graph games, Games involving graphs, random-turn games, Graph games, 000 Computer science, knowledge, general works, Theory and Algorithms, Parity games, 2-person games, 004, poorman bidding, Logic in Computer Science (cs.LO), Stochastic games, stochastic differential games, meanpayoff games, Graphics and Human Computer Interfaces, Computer Science, mean-payoff games, Random-turn games, Stochastic games, Computer Science and Game Theory (cs.GT), ddc: ddc:004
FOS: Computer and information sciences, bidding games, Computer Science - Logic in Computer Science, Bidding games, taxman bidding, Auctions, bargaining, bidding and selling, and other market models, parity games, Mean-payoff games, Poorman bidding, Computer Science - Computer Science and Game Theory, Richman bidding, stochastic games, graph games, Games involving graphs, random-turn games, Graph games, 000 Computer science, knowledge, general works, Theory and Algorithms, Parity games, 2-person games, 004, poorman bidding, Logic in Computer Science (cs.LO), Stochastic games, stochastic differential games, meanpayoff games, Graphics and Human Computer Interfaces, Computer Science, mean-payoff games, Random-turn games, Stochastic games, Computer Science and Game Theory (cs.GT), ddc: ddc:004
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 2 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
