Bidding Graph Games with Partially-Observed Budgets

In a two-player zero-sum graph game, the players move a token throughout a graph to produce an infinite path, which determines the winner or payoff of the game. {\em Bidding games} are graph games in which the players have budgets and in each turn, an auction determines which player moves the token. The motivation for this work arises from the potential of bidding games to model stateful and ongoing auctions. For example, online advertisement campaigns that run on multiple publishers (e. g. , New York Times or Washington Post) who auction their advertisement slots in an ongoing manner (e. g. , daily). Previously, bidding games were only studied as full-information games. In most auction domains, however, it is rarely the case that buyers have full information on the budgets of their opponents. We study, for the first time, bidding games in which the budgets of the players are drawn from a probability distribution, thus a player has only partial information on the opponent’s available budget. We stress that unlike partial-information graph games, we consider games in which there is full information regarding the position of the token. We study qualitative and quantitative objectives with the canonical bidding mechanisms. Our most interesting results are for {\em mean-payoff} games with {\em poorman} bidding: whenever a player wins a bidding, the bid is paid to the “bank”. Poorman bidding is interesting in the partial information setting since in the full-information setting, unlike other bidding mechanisms, the optimal payoff a player can guarantee in a mean-payoff poorman-bidding game is strictly increasing with the initial budget. We focus on the case of {\em one-sided} partial information, which is already both surprising and technically challenging. We classify the optimal expected payoff that the partially-informed player can guarantee with any initial budget in any strongly-connected game. In addition, we classify the optimal expected payoff that the fully-informed player can guarantee in a simple strongly-connected game, which reveals surprises. First, the optimal strategy of the fully-informed player reveals immediately her true initial budget. That is, the fully-informed player cannot use the partial information of her opponent to her advantage. Second, contrary to bidding, turn-based, and stochastic games, in partial-information {\em mean-payoff} bidding games the {\em value} does not necessarily exist under pure strategies: there are cases in which the optimal expected payoff that \Max can guarantee is strictly lower than the optimal payoff \Min can guarantee. Joint work with Isma\”el Jecker and {\DJ}or{\dj}e \v{Z}ikeli\’c.

Authors

• Guy Avni

Keywords

No keywords are indexed for this paper.