Reachability Poorman Discrete-Bidding Games

We consider "bidding games", a class of two-player zero-sum "graph games". The game proceeds as follows. Both players have bounded budgets. A token is placed on a vertex of a graph, in each turn the players simultaneously submit bids, and the higher bidder moves the token (ties are broken according to a predefined mechanism). Player 1 wins the game iff the token visits a designated target vertex. We consider, for the first time, "poorman discrete-bidding" in which the granularity of the bids is restricted and the higher bid is paid to the bank. In contrast, in "Richman continuous-bidding" bids can be arbitrarily small and are paid to the other player. While the latter mechanism is technically more accessible, the former is more appealing from a practical standpoint. Our study focuses on "threshold budgets", which is the necessary and sufficient initial budget required for Player 1 to ensure winning against a given Player 2 budget. We show existence of thresholds when Player 1 wins bidding ties. In DAGs, we show that threshold budgets can be approximated with error bounds by thresholds under continuous-bidding and that they exhibit a periodic behavior. We identify closed-form solutions in special cases. We implement and experiment with an algorithm to find threshold budgets. This is a joint work with Guy Avni, Tobias Meggendorfer, Josef Tkadlec, and Djordje Zikelic. Contributed talk given by Suman Sadhukhan

Authors

• Suman Sadhukhan University of Haifa

Keywords

No keywords are indexed for this paper.