---
_id: '10694'
abstract:
- lang: eng
  text: '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 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
    first-price bidding in which only the higher bidder pays his bid. We focus on
    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 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 and
    almost-sure (with probability 1) payoffs 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 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.'
acknowledgement: This research was supported in part by the Austrian Science Fund
  (FWF) under grant Z211-N23 (Wittgenstein Award), ERC CoG 863818 (FoRM-SMArt), and
  by the European Union's Horizon 2020 research and innovation programme under the
  Marie Skłodowska-Curie Grant Agreement No. 665385.
article_processing_charge: No
arxiv: 1
author:
- first_name: Guy
  full_name: Avni, Guy
  id: 463C8BC2-F248-11E8-B48F-1D18A9856A87
  last_name: Avni
  orcid: 0000-0001-5588-8287
- first_name: Ismael R
  full_name: Jecker, Ismael R
  id: 85D7C63E-7D5D-11E9-9C0F-98C4E5697425
  last_name: Jecker
- first_name: Dorde
  full_name: Zikelic, Dorde
  id: 294AA7A6-F248-11E8-B48F-1D18A9856A87
  last_name: Zikelic
  orcid: 0000-0002-4681-1699
citation:
  ama: 'Avni G, Jecker IR, Zikelic D. Infinite-duration all-pay bidding games. In:
    Marx D, ed. <i>Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms</i>.
    Society for Industrial and Applied Mathematics; 2021:617-636. doi:<a href="https://doi.org/10.1137/1.9781611976465.38">10.1137/1.9781611976465.38</a>'
  apa: 'Avni, G., Jecker, I. R., &#38; Zikelic, D. (2021). Infinite-duration all-pay
    bidding games. In D. Marx (Ed.), <i>Proceedings of the 2021 ACM-SIAM Symposium
    on Discrete Algorithms</i> (pp. 617–636). Virtual: Society for Industrial and
    Applied Mathematics. <a href="https://doi.org/10.1137/1.9781611976465.38">https://doi.org/10.1137/1.9781611976465.38</a>'
  chicago: Avni, Guy, Ismael R Jecker, and Dorde Zikelic. “Infinite-Duration All-Pay
    Bidding Games.” In <i>Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms</i>,
    edited by Dániel Marx, 617–36. Society for Industrial and Applied Mathematics,
    2021. <a href="https://doi.org/10.1137/1.9781611976465.38">https://doi.org/10.1137/1.9781611976465.38</a>.
  ieee: G. Avni, I. R. Jecker, and D. Zikelic, “Infinite-duration all-pay bidding
    games,” in <i>Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms</i>,
    Virtual, 2021, pp. 617–636.
  ista: 'Avni G, Jecker IR, Zikelic D. 2021. Infinite-duration all-pay bidding games.
    Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium
    on Discrete Algorithms, 617–636.'
  mla: Avni, Guy, et al. “Infinite-Duration All-Pay Bidding Games.” <i>Proceedings
    of the 2021 ACM-SIAM Symposium on Discrete Algorithms</i>, edited by Dániel Marx,
    Society for Industrial and Applied Mathematics, 2021, pp. 617–36, doi:<a href="https://doi.org/10.1137/1.9781611976465.38">10.1137/1.9781611976465.38</a>.
  short: G. Avni, I.R. Jecker, D. Zikelic, in:, D. Marx (Ed.), Proceedings of the
    2021 ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied
    Mathematics, 2021, pp. 617–636.
conference:
  end_date: 2021-01-13
  location: Virtual
  name: 'SODA: Symposium on Discrete Algorithms'
  start_date: 2021-01-10
date_created: 2022-01-27T12:11:23Z
date_published: 2021-01-01T00:00:00Z
date_updated: 2025-07-14T09:10:12Z
day: '01'
department:
- _id: GradSch
- _id: KrCh
doi: 10.1137/1.9781611976465.38
ec_funded: 1
editor:
- first_name: Dániel
  full_name: Marx, Dániel
  last_name: Marx
external_id:
  arxiv:
  - '2005.06636'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/2005.06636
month: '01'
oa: 1
oa_version: Preprint
page: 617-636
project:
- _id: 25F42A32-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: Z211
  name: The Wittgenstein Prize
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
  call_identifier: H2020
  grant_number: '863818'
  name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
- _id: 2564DBCA-B435-11E9-9278-68D0E5697425
  call_identifier: H2020
  grant_number: '665385'
  name: International IST Doctoral Program
publication: Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms
publication_identifier:
  isbn:
  - 978-1-61197-646-5
publication_status: published
publisher: Society for Industrial and Applied Mathematics
quality_controlled: '1'
scopus_import: '1'
status: public
title: Infinite-duration all-pay bidding games
type: conference
user_id: 8b945eb4-e2f2-11eb-945a-df72226e66a9
year: '2021'
...