Bidding graph games with partially-observable budgets

conference paper Bidding graph games with partially-observable budgets published yes Guy Avni author 463C8BC2-F248-11E8-B48F-1D18A9856A870000-0001-5588-8287 Ismael R Jecker author 85D7C63E-7D5D-11E9-9C0F-98C4E5697425 Dorde Zikelic author 294AA7A6-F248-11E8-B48F-1D18A9856A870000-0002-4681-1699 ToHe department KrCh department AAAI: Conference on Artificial Intelligence Formal Methods for Stochastic Models: Algorithms and Applications project International IST Doctoral Program project 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. 2023Washington, DC, United States eng Proceedings of the 37th AAAI Conference on Artificial Intelligence 9781577358800 2211.1362610.1609/aaai.v37i5.25679 3755464-5471 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. <a href="https://doi.org/10.1609/aaai.v37i5.25679">https://doi.org/10.1609/aaai.v37i5.25679</a> 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. <a href="https://doi.org/10.1609/aaai.v37i5.25679">https://doi.org/10.1609/aaai.v37i5.25679</a>. 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:<a href="https://doi.org/10.1609/aaai.v37i5.25679">10.1609/aaai.v37i5.25679</a> 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:<a href="https://doi.org/10.1609/aaai.v37i5.25679">10.1609/aaai.v37i5.25679</a>. 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. G. Avni, I.R. Jecker, D. Zikelic, in:, Proceedings of the 37th AAAI Conference on Artificial Intelligence, 2023, pp. 5464–5471. 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. 142432023-08-27T22:01:18Z2025-03-31T16:01:08Z