Publication Type

Conference Proceeding Article

Version

publishedVersion

Publication Date

2-2023

Abstract

Two-player zero-sum graph games are a central model, which proceeds as follows. A token is placed on a vertex of a graph, and the two players move it to produce an infinite play, 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 fullinformation 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 partialinformation setting, for others, the analysis is significantly more challenging, requires new techniques, and gives rise to interesting results. Specifically, we study games with meanpayoff 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.

Discipline

Graphics and Human Computer Interfaces

Research Areas

Intelligent Systems and Optimization

Areas of Excellence

Digital transformation

Publication

Proceedings of the 37th AAAI Conference on Artificial Intelligence, Washington, DC, 2023 February 7-14

Volume

37

First Page

5464

Last Page

5471

Identifier

10.1609/aaai.v37i5.25679

City or Country

Washington, DC

Copyright Owner and License

Authors

Additional URL

https://doi.org/10.1609/aaai.v37i5.25679

Download

Share

COinS