License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2022.30
URN: urn:nbn:de:0030-drops-174222
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17422/
Avni, Guy ;
Sadhukhan, Suman
Computing Threshold Budgets in Discrete-Bidding Games
Abstract
In a two-player zero-sum graph game, the players move a token throughout the graph to produce an infinite play, which determines the winner of the game. Bidding games are graph games in which in each turn, an auction (bidding) determines which player moves the token: the players have budgets, and in each turn, both players simultaneously submit bids that do not exceed their available budgets, the higher bidder moves the token, and pays the bid to the lower bidder. We distinguish between continuous- and discrete-bidding games. In the latter, the granularity of the players' bids is restricted, e.g., bids must be given in cents. Continuous-bidding games are well understood, however, from a practical standpoint, discrete-bidding games are more appealing.
In this paper we focus on discrete-bidding games. We study the problem of finding threshold budgets; namely, a necessary and sufficient initial budget for winning the game. Previously, the properties of threshold budgets were only studied for reachability games. For parity discrete-bidding games, thresholds were known to exist, but their structure was not understood. We describe two algorithms for finding threshold budgets in parity discrete-bidding games. The first algorithm is a fixed-point algorithm, and it reveals the structure of the threshold budgets in these games. Second, we show that the problem of finding threshold budgets is in NP and coNP for parity discrete-bidding games. Previously, only exponential-time algorithms where known for reachability and parity objectives. A corollary of this proof is a construction of strategies that use polynomial-size memory.
BibTeX - Entry
@InProceedings{avni_et_al:LIPIcs.FSTTCS.2022.30,
author = {Avni, Guy and Sadhukhan, Suman},
title = {{Computing Threshold Budgets in Discrete-Bidding Games}},
booktitle = {42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)},
pages = {30:1--30:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-261-7},
ISSN = {1868-8969},
year = {2022},
volume = {250},
editor = {Dawar, Anuj and Guruswami, Venkatesan},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17422},
URN = {urn:nbn:de:0030-drops-174222},
doi = {10.4230/LIPIcs.FSTTCS.2022.30},
annote = {Keywords: Discrete bidding games, Richman games, parity games, reachability games}
}
|
Keywords: |
|
Discrete bidding games, Richman games, parity games, reachability games |
|
Collection: |
|
42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
14.12.2022 |
