Bidding graph games with partially-observable budgets

Avni G, Jecker IR, Zikelic D. 2023. Bidding graph games with partially-observable budgets. Proceedings of the 37th AAAI Conference on Artificial Intelligence. AAAI: Conference on Artificial Intelligence vol. 37, 5464–5471.

Download (ext.)

Conference Paper | Published | English

Scopus indexed
Abstract
Two-player zero-sum "graph games" are central in logic, verification, and multi-agent systems. The game proceeds by placing a token on a vertex of a graph, and allowing the players to move it 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, an auction (bidding) determines which player moves the token. So far, bidding games have only been studied as full-information games. In this work we initiate the study of partial-information bidding games: we study bidding games in which a player's initial budget is drawn from a known probability distribution. We show that while for some bidding mechanisms and objectives, it is straightforward to adapt the results from the full-information setting to the partial-information setting, for others, the analysis is significantly more challenging, requires new techniques, and gives rise to interesting results. Specifically, we study games with "mean-payoff" objectives in combination with "poorman" bidding. We construct optimal strategies for a partially-informed player who plays against a fully-informed adversary. We show that, somewhat surprisingly, the "value" under pure strategies does not necessarily exist in such games.
Publishing Year
Date Published
2023-06-27
Proceedings Title
Proceedings of the 37th AAAI Conference on Artificial Intelligence
Acknowledgement
This research was supported in part by ISF grant no.1679/21, by the ERC CoG 863818 (ForM-SMArt), and the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement No. 665385.
Volume
37
Issue
5
Page
5464-5471
Conference
AAAI: Conference on Artificial Intelligence
Conference Location
Washington, DC, United States
Conference Date
2023-02-07 – 2023-02-14
IST-REx-ID

Cite this

Avni G, Jecker IR, Zikelic D. Bidding graph games with partially-observable budgets. In: Proceedings of the 37th AAAI Conference on Artificial Intelligence. Vol 37. ; 2023:5464-5471. doi:10.1609/aaai.v37i5.25679
Avni, G., Jecker, I. R., & Zikelic, D. (2023). Bidding graph games with partially-observable budgets. In Proceedings of the 37th AAAI Conference on Artificial Intelligence (Vol. 37, pp. 5464–5471). Washington, DC, United States. https://doi.org/10.1609/aaai.v37i5.25679
Avni, Guy, Ismael R Jecker, and Dorde Zikelic. “Bidding Graph Games with Partially-Observable Budgets.” In Proceedings of the 37th AAAI Conference on Artificial Intelligence, 37:5464–71, 2023. https://doi.org/10.1609/aaai.v37i5.25679.
G. Avni, I. R. Jecker, and D. Zikelic, “Bidding graph games with partially-observable budgets,” in Proceedings of the 37th AAAI Conference on Artificial Intelligence, Washington, DC, United States, 2023, vol. 37, no. 5, pp. 5464–5471.
Avni G, Jecker IR, Zikelic D. 2023. Bidding graph games with partially-observable budgets. Proceedings of the 37th AAAI Conference on Artificial Intelligence. AAAI: Conference on Artificial Intelligence vol. 37, 5464–5471.
Avni, Guy, et al. “Bidding Graph Games with Partially-Observable Budgets.” Proceedings of the 37th AAAI Conference on Artificial Intelligence, vol. 37, no. 5, 2023, pp. 5464–71, doi:10.1609/aaai.v37i5.25679.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data ISTA Research Explorer

Sources

arXiv 2211.13626

Search this title in

Google Scholar
ISBN Search