Standard
Reachability Poorman Discrete-Bidding Games. / Avni, Guy
; Meggendorfer, Tobias; Sadhukhan, Suman et al.
ECAI 2023 - 26th European Conference on Artificial Intelligence, including 12th Conference on Prestigious Applications of Intelligent Systems, PAIS 2023 - Proceedings. ed. / Kobi Gal; Kobi Gal; Ann Nowe; Grzegorz J. Nalepa; Roy Fairstein; Roxana Radulescu. 2023. p. 141-148 (Frontiers in Artificial Intelligence and Applications; Vol. 372).
Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSN › Conference contribution/Paper › peer-review
Harvard
Avni, G
, Meggendorfer, T, Sadhukhan, S, Tkadlec, J & Žikelić, Đ 2023,
Reachability Poorman Discrete-Bidding Games. in K Gal, K Gal, A Nowe, GJ Nalepa, R Fairstein & R Radulescu (eds),
ECAI 2023 - 26th European Conference on Artificial Intelligence, including 12th Conference on Prestigious Applications of Intelligent Systems, PAIS 2023 - Proceedings. Frontiers in Artificial Intelligence and Applications, vol. 372, pp. 141-148.
https://doi.org/10.3233/FAIA230264APA
Avni, G.
, Meggendorfer, T., Sadhukhan, S., Tkadlec, J., & Žikelić, Đ. (2023).
Reachability Poorman Discrete-Bidding Games. In K. Gal, K. Gal, A. Nowe, G. J. Nalepa, R. Fairstein, & R. Radulescu (Eds.),
ECAI 2023 - 26th European Conference on Artificial Intelligence, including 12th Conference on Prestigious Applications of Intelligent Systems, PAIS 2023 - Proceedings (pp. 141-148). (Frontiers in Artificial Intelligence and Applications; Vol. 372).
https://doi.org/10.3233/FAIA230264Vancouver
Avni G
, Meggendorfer T, Sadhukhan S, Tkadlec J, Žikelić Đ.
Reachability Poorman Discrete-Bidding Games. In Gal K, Gal K, Nowe A, Nalepa GJ, Fairstein R, Radulescu R, editors, ECAI 2023 - 26th European Conference on Artificial Intelligence, including 12th Conference on Prestigious Applications of Intelligent Systems, PAIS 2023 - Proceedings. 2023. p. 141-148. (Frontiers in Artificial Intelligence and Applications). doi: 10.3233/FAIA230264
Author
Avni, Guy
; Meggendorfer, Tobias ; Sadhukhan, Suman et al. /
Reachability Poorman Discrete-Bidding Games. ECAI 2023 - 26th European Conference on Artificial Intelligence, including 12th Conference on Prestigious Applications of Intelligent Systems, PAIS 2023 - Proceedings. editor / Kobi Gal ; Kobi Gal ; Ann Nowe ; Grzegorz J. Nalepa ; Roy Fairstein ; Roxana Radulescu. 2023. pp. 141-148 (Frontiers in Artificial Intelligence and Applications).
Bibtex
@inproceedings{dbcb824d7f5747cda0730b6fc43065f5,
title = "Reachability Poorman Discrete-Bidding Games.",
abstract = "We consider bidding games, a class of two-player zero-sum graph games. The game proceeds as follows. Both players have bounded budgets. A token is placed on a vertex of a graph, in each turn the players simultaneously submit bids, and the higher bidder moves the token, where we break bidding ties in favor of Player 1. Player 1 wins the game iff the token visits a designated target vertex. We consider, for the first time, poorman discrete-bidding in which the granularity of the bids is restricted and the higher bid is paid to the bank. Previous work either did not impose granularity restrictions or considered Richman bidding (bids are paid to the opponent). While the latter mechanisms are technically more accessible, the former is more appealing from a practical standpoint. Our study focuses on threshold budgets, which is the necessary and sufficient initial budget required for Player 1 to ensure winning against a given Player 2 budget. We first show existence of thresholds. In DAGs, we show that threshold budgets can be approximated with error bounds by thresholds under continuous-bidding and that they exhibit a periodic behavior. We identify closed-form solutions in special cases. We implement and experiment with an algorithm to find threshold budgets.",
author = "Guy Avni and Tobias Meggendorfer and Suman Sadhukhan and Josef Tkadlec and {\D}or{\d}e {\v Z}ikeli{\'c}",
year = "2023",
month = sep,
day = "28",
doi = "10.3233/FAIA230264",
language = "English",
series = "Frontiers in Artificial Intelligence and Applications",
pages = "141--148",
editor = "Kobi Gal and Kobi Gal and Ann Nowe and Nalepa, {Grzegorz J.} and Roy Fairstein and Roxana Radulescu",
booktitle = "ECAI 2023 - 26th European Conference on Artificial Intelligence, including 12th Conference on Prestigious Applications of Intelligent Systems, PAIS 2023 - Proceedings",
}
RIS
TY - GEN
T1 - Reachability Poorman Discrete-Bidding Games.
AU - Avni, Guy
AU - Meggendorfer, Tobias
AU - Sadhukhan, Suman
AU - Tkadlec, Josef
AU - Žikelić, Đorđe
PY - 2023/9/28
Y1 - 2023/9/28
N2 - We consider bidding games, a class of two-player zero-sum graph games. The game proceeds as follows. Both players have bounded budgets. A token is placed on a vertex of a graph, in each turn the players simultaneously submit bids, and the higher bidder moves the token, where we break bidding ties in favor of Player 1. Player 1 wins the game iff the token visits a designated target vertex. We consider, for the first time, poorman discrete-bidding in which the granularity of the bids is restricted and the higher bid is paid to the bank. Previous work either did not impose granularity restrictions or considered Richman bidding (bids are paid to the opponent). While the latter mechanisms are technically more accessible, the former is more appealing from a practical standpoint. Our study focuses on threshold budgets, which is the necessary and sufficient initial budget required for Player 1 to ensure winning against a given Player 2 budget. We first show existence of thresholds. In DAGs, we show that threshold budgets can be approximated with error bounds by thresholds under continuous-bidding and that they exhibit a periodic behavior. We identify closed-form solutions in special cases. We implement and experiment with an algorithm to find threshold budgets.
AB - We consider bidding games, a class of two-player zero-sum graph games. The game proceeds as follows. Both players have bounded budgets. A token is placed on a vertex of a graph, in each turn the players simultaneously submit bids, and the higher bidder moves the token, where we break bidding ties in favor of Player 1. Player 1 wins the game iff the token visits a designated target vertex. We consider, for the first time, poorman discrete-bidding in which the granularity of the bids is restricted and the higher bid is paid to the bank. Previous work either did not impose granularity restrictions or considered Richman bidding (bids are paid to the opponent). While the latter mechanisms are technically more accessible, the former is more appealing from a practical standpoint. Our study focuses on threshold budgets, which is the necessary and sufficient initial budget required for Player 1 to ensure winning against a given Player 2 budget. We first show existence of thresholds. In DAGs, we show that threshold budgets can be approximated with error bounds by thresholds under continuous-bidding and that they exhibit a periodic behavior. We identify closed-form solutions in special cases. We implement and experiment with an algorithm to find threshold budgets.
U2 - 10.3233/FAIA230264
DO - 10.3233/FAIA230264
M3 - Conference contribution/Paper
T3 - Frontiers in Artificial Intelligence and Applications
SP - 141
EP - 148
BT - ECAI 2023 - 26th European Conference on Artificial Intelligence, including 12th Conference on Prestigious Applications of Intelligent Systems, PAIS 2023 - Proceedings
A2 - Gal, Kobi
A2 - Gal, Kobi
A2 - Nowe, Ann
A2 - Nalepa, Grzegorz J.
A2 - Fairstein, Roy
A2 - Radulescu, Roxana
ER -
