Infinite-duration Bidding Games

DOI10.1145/3340295MaRDI QIDQ5215460zbMATHOpenAlexFDO

Authors Guy Avni, Ventsislav Chonev, Thomas A. Henzinger

Publication date 11 February 2020

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1705.01433

zbMATH Keywords

parity gamesmean-payoff gamesRichman gamesbidding games

Mathematics Subject Classification ID

2-person games (91A05) Games on graphs (graph-theoretic aspects) (05C57) Stochastic games, stochastic differential games (91A15) Games involving graphs (91A43)

Abstract: Two-player games on graphs are widely studied in formal methods as they model the interaction between a system and its environment. The game is played by moving a token throughout a graph to produce an infinite path. There are several common modes to determine how the players move the token through the graph; e.g., in turn-based games the players alternate turns in moving the token. We study the {em bidding} mode of moving the token, which, to the best of our knowledge, has never been studied in infinite-duration games. The following bidding rule was previously defined and called Richman bidding. Both players have separate {em budgets}, which sum up to $1$. In each turn, a bidding takes place: Both players submit bids simultaneously, where a bid is legal if it does not exceed the available budget, and the higher bidder pays his bid to the other player and moves the token. The central question studied in bidding games is a necessary and sufficient initial budget for winning the game: a {em threshold} budget in a vertex is a value $tin[0,1]$ such that if Player $1$'s budget exceeds $t$, he can win the game, and if Player $2$'s budget exceeds $1-t$, he can win the game. Threshold budgets were previously shown to exist in every vertex of a reachability game, which have an interesting connection with {em random-turn} games -- a sub-class of simple stochastic games in which the player who moves is chosen randomly. We show the existence of threshold budgets for a qualitative class of infinite-duration games, namely parity games, and a quantitative class, namely mean-payoff games. The key component of the proof is a quantitative solution to strongly-connected mean-payoff bidding games in which we extend the connection with random-turn games to these games, and construct explicit optimal strategies for both players.

Recommendations

• Infinite-duration bidding games
• Infinite-duration poorman-bidding games
• Determinacy in discrete-bidding infinite-duration games
• scientific article; zbMATH DE number 7327943
• Infinite asymptotic games
• A differential game of unlimited duration
• Games of stopping with infinite horizon
• Discrete bidding games
• Capital accumulation games of infinite duration
• Infinite games on finite sets

Cited in

(9)

• Bidding games on Markov decision processes
• scientific article; zbMATH DE number 7561655 (Why is no real title available?)
• scientific article; zbMATH DE number 7327943 (Why is no real title available?)
• A Survey of Bidding Games on Graphs (Invited Paper)
• Infinite-duration bidding games
• Timed network games
• Bidding mechanisms in graph games
• Infinite-duration poorman-bidding games
• Multi-recastable e-bidding game with dual-blindness

This page was built for publication: Infinite-duration Bidding Games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5215460)