Publication Type

Conference Proceeding Article

Version

publishedVersion

Publication Date

10-2023

Abstract

We consider bidding games, a class of two-player zerosum 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. Weconsider, 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 f irst 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.

Discipline

Artificial Intelligence and Robotics

Research Areas

Intelligent Systems and Optimization

Areas of Excellence

Digital transformation

Publication

Proceedings of the 26th European Conference on Artificial Intelligence (ECAI 2023), Kraków, Poland, September 30 - October 4,

Volume

372

First Page

141

Last Page

148

ISBN

9781643684376

Identifier

10.3233/faia230264

Publisher

IOS Press

City or Country

Poland

Copyright Owner and License

Authors

Additional URL

https://doi.org/10.3233/faia230264

Download

Share

COinS