An updated survey of bidding games on graphs
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.
Download
Conference Paper
| Published
| English
Scopus indexed
Author
Department
Abstract
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.
Publishing Year
Date Published
2022-08-22
Proceedings Title
47th International Symposium on Mathematical Foundations of Computer Science
Publisher
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Acknowledgement
Guy Avni: Work partially supported by the Israel Science Foundation, ISF grant agreement
no 1679/21.
Thomas A. Henzinger: This work was supported in part by the ERC-2020-AdG 101020093.
We 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.
Volume
241
Page
3:1-3:6
Conference
MFCS: Symposium on Mathematical Foundations of Computer Science
Conference Location
Vienna, Austria
Conference Date
2022-08-22 – 2022-08-26
ISBN
ISSN
IST-REx-ID
Cite this
Avni G, Henzinger TA. An updated survey of bidding games on graphs. In: 47th International Symposium on Mathematical Foundations of Computer Science. Vol 241. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2022:3:1-3:6. doi:10.4230/LIPIcs.MFCS.2022.3
Avni, G., & Henzinger, T. A. (2022). An updated survey of bidding games on graphs. In 47th International Symposium on Mathematical Foundations of Computer Science (Vol. 241, p. 3:1-3:6). Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.MFCS.2022.3
Avni, Guy, and Thomas A Henzinger. “An Updated Survey of Bidding Games on Graphs.” In 47th International Symposium on Mathematical Foundations of Computer Science, 241:3:1-3:6. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. https://doi.org/10.4230/LIPIcs.MFCS.2022.3.
G. Avni and T. A. Henzinger, “An updated survey of bidding games on graphs,” in 47th International Symposium on Mathematical Foundations of Computer Science, Vienna, Austria, 2022, vol. 241, p. 3:1-3:6.
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.
Avni, Guy, and Thomas A. Henzinger. “An Updated Survey of Bidding Games on Graphs.” 47th International Symposium on Mathematical Foundations of Computer Science, vol. 241, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022, p. 3:1-3:6, doi:10.4230/LIPIcs.MFCS.2022.3.
All files available under the following license(s):
Creative Commons Attribution 4.0 International Public License (CC-BY 4.0):
Main File(s)
File Name
2022_LIPICs_Avni.pdf
624.59 KB
Access Level
Open Access
Date Uploaded
2023-02-06
MD5 Checksum
1888ec9421622f9526fbec2de035f132