---
_id: '12509'
abstract:
- lang: eng
  text: A graph game is a two-player zero-sum game in which the players move a token
    throughout a graph to produce an infinite path, which determines the winner or
    payoff of the game. In bidding games, both players have budgets, and in each turn,
    we hold an "auction" (bidding) to determine which player moves the token. In this
    survey, we consider several bidding mechanisms and their effect on the properties
    of the game. Specifically, bidding games, and in particular bidding games of infinite
    duration, have an intriguing equivalence with random-turn games in which in each
    turn, the player who moves is chosen randomly. We summarize how minor changes
    in the bidding mechanism lead to unexpected differences in the equivalence with
    random-turn games.
acknowledgement: "Guy Avni: Work partially supported by the Israel Science Foundation,
  ISF grant agreement\r\nno 1679/21.\r\nThomas A. Henzinger: This work was supported
  in part by the ERC-2020-AdG 101020093.\r\nWe would like to thank all our collaborators
  Milad Aghajohari, Ventsislav Chonev, Rasmus Ibsen-Jensen, Ismäel Jecker, Petr Novotný,
  Josef Tkadlec, and Ðorđe Žikelić; we hope the collaboration was as fun and meaningful
  for you as it was for us."
article_processing_charge: No
author:
- first_name: Guy
  full_name: Avni, Guy
  id: 463C8BC2-F248-11E8-B48F-1D18A9856A87
  last_name: Avni
  orcid: 0000-0001-5588-8287
- first_name: Thomas A
  full_name: Henzinger, Thomas A
  id: 40876CD8-F248-11E8-B48F-1D18A9856A87
  last_name: Henzinger
  orcid: 0000-0002-2985-7724
citation:
  ama: 'Avni G, Henzinger TA. An updated survey of bidding games on graphs. In: <i>47th
    International Symposium on Mathematical Foundations of Computer Science</i>. Vol
    241. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany:
    Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2022:3:1-3:6. doi:<a href="https://doi.org/10.4230/LIPIcs.MFCS.2022.3">10.4230/LIPIcs.MFCS.2022.3</a>'
  apa: 'Avni, G., &#38; Henzinger, T. A. (2022). An updated survey of bidding games
    on graphs. In <i>47th International Symposium on Mathematical Foundations of Computer
    Science</i> (Vol. 241, p. 3:1-3:6). Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum
    für Informatik. <a href="https://doi.org/10.4230/LIPIcs.MFCS.2022.3">https://doi.org/10.4230/LIPIcs.MFCS.2022.3</a>'
  chicago: 'Avni, Guy, and Thomas A Henzinger. “An Updated Survey of Bidding Games
    on Graphs.” In <i>47th International Symposium on Mathematical Foundations of
    Computer Science</i>, 241:3:1-3:6. Leibniz International Proceedings in Informatics
    (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
    2022. <a href="https://doi.org/10.4230/LIPIcs.MFCS.2022.3">https://doi.org/10.4230/LIPIcs.MFCS.2022.3</a>.'
  ieee: G. Avni and T. A. Henzinger, “An updated survey of bidding games on graphs,”
    in <i>47th International Symposium on Mathematical Foundations of Computer Science</i>,
    Vienna, Austria, 2022, vol. 241, p. 3:1-3:6.
  ista: 'Avni G, Henzinger TA. 2022. An updated survey of bidding games on graphs.
    47th International Symposium on Mathematical Foundations of Computer Science.
    MFCS: Symposium on Mathematical Foundations of Computer ScienceLeibniz International
    Proceedings in Informatics (LIPIcs) vol. 241, 3:1-3:6.'
  mla: Avni, Guy, and Thomas A. Henzinger. “An Updated Survey of Bidding Games on
    Graphs.” <i>47th International Symposium on Mathematical Foundations of Computer
    Science</i>, vol. 241, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022,
    p. 3:1-3:6, doi:<a href="https://doi.org/10.4230/LIPIcs.MFCS.2022.3">10.4230/LIPIcs.MFCS.2022.3</a>.
  short: G. Avni, T.A. Henzinger, in:, 47th International Symposium on Mathematical
    Foundations of Computer Science, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
    Dagstuhl, Germany, 2022, p. 3:1-3:6.
conference:
  end_date: 2022-08-26
  location: Vienna, Austria
  name: 'MFCS: Symposium on Mathematical Foundations of Computer Science'
  start_date: 2022-08-22
date_created: 2023-02-05T17:26:01Z
date_published: 2022-08-22T00:00:00Z
date_updated: 2023-02-06T09:16:54Z
day: '22'
ddc:
- '000'
department:
- _id: ToHe
doi: 10.4230/LIPIcs.MFCS.2022.3
ec_funded: 1
file:
- access_level: open_access
  checksum: 1888ec9421622f9526fbec2de035f132
  content_type: application/pdf
  creator: dernst
  date_created: 2023-02-06T09:13:04Z
  date_updated: 2023-02-06T09:13:04Z
  file_id: '12519'
  file_name: 2022_LIPICs_Avni.pdf
  file_size: 624586
  relation: main_file
  success: 1
file_date_updated: 2023-02-06T09:13:04Z
has_accepted_license: '1'
intvolume: '       241'
language:
- iso: eng
month: '08'
oa: 1
oa_version: Published Version
page: 3:1-3:6
place: Dagstuhl, Germany
project:
- _id: 62781420-2b32-11ec-9570-8d9b63373d4d
  call_identifier: H2020
  grant_number: '101020093'
  name: Vigilant Algorithmic Monitoring of Software
publication: 47th International Symposium on Mathematical Foundations of Computer
  Science
publication_identifier:
  isbn:
  - '9783959772563'
  issn:
  - 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
series_title: Leibniz International Proceedings in Informatics (LIPIcs)
status: public
title: An updated survey of bidding games on graphs
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 241
year: '2022'
...