Infinite-Duration All-Pay Bidding Games

Guy Avni, Isma\"el Jecker and {\DJ}or{\dj}e \v{Z}ikeli\'c

Papers from arXiv.org

Abstract: 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. Traditionally, the players alternate turns in moving the token. In {\em bidding games}, however, the players have budgets, and in each turn, we hold an "auction" (bidding) to determine which player moves the token: both players simultaneously submit bids and the higher bidder moves the token. The bidding mechanisms differ in their payment schemes. Bidding games were largely studied with variants of {\em first-price} bidding in which only the higher bidder pays his bid. We focus on {\em all-pay} bidding, where both players pay their bids. Finite-duration all-pay bidding games were studied and shown to be technically more challenging than their first-price counterparts. We study for the first time, infinite-duration all-pay bidding games. Our most interesting results are for {\em mean-payoff} objectives: we portray a complete picture for games played on strongly-connected graphs. We study both pure (deterministic) and mixed (probabilistic) strategies and completely characterize the optimal sure and almost-sure (with probability $1$) payoffs that the players can respectively guarantee. We show that mean-payoff games under all-pay bidding exhibit the intriguing mathematical properties of their first-price counterparts; namely, an equivalence with {\em random-turn games} in which in each turn, the player who moves is selected according to a (biased) coin toss. The equivalences for all-pay bidding are more intricate and unexpected than for first-price bidding.

Date: 2020-05, Revised 2020-12
New Economics Papers: this item is included in nep-des, nep-gth and nep-mic
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://arxiv.org/pdf/2005.06636 Latest version (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:arx:papers:2005.06636

Access Statistics for this paper

More papers in Papers from arXiv.org
Bibliographic data for series maintained by arXiv administrators ().