License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CONCUR.2017.21
URN: urn:nbn:de:0030-drops-77741
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7774/
Avni, Guy ;
Henzinger, Thomas A. ;
Chonev, Ventsislav
Infinite-Duration Bidding Games
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 bidding mode of moving the token, which, to the best of our knowledge, has never been studied in infinite-duration games. Both players have separate budgets, which sum up to $1$. In each turn, a bidding takes place. Both players submit bids simultaneously, and a bid is legal if it does not exceed the available budget. The winner of the bidding pays his bid to the other player and moves the token. For reachability objectives, repeated bidding games have been studied and are called Richman games [Lazarus1999,Lazarus2012]. There, a central question is the existence and computation of threshold budgets; namely, a value t \in [0,1] such that if \PO's budget exceeds t, he can win the game, and if \PT's budget exceeds 1-t, he can win the game. We focus on parity games and mean-payoff games. We show the existence of threshold budgets in these games, and reduce the problem of finding them to Richman games. We also determine the strategy-complexity of an optimal strategy. Our most interesting result shows that memoryless strategies suffice for mean-payoff bidding games.
BibTeX - Entry
@InProceedings{avni_et_al:LIPIcs:2017:7774,
author = {Guy Avni and Thomas A. Henzinger and Ventsislav Chonev},
title = {{Infinite-Duration Bidding Games}},
booktitle = {28th International Conference on Concurrency Theory (CONCUR 2017)},
pages = {21:1--21:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-048-4},
ISSN = {1868-8969},
year = {2017},
volume = {85},
editor = {Roland Meyer and Uwe Nestmann},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7774},
URN = {urn:nbn:de:0030-drops-77741},
doi = {10.4230/LIPIcs.CONCUR.2017.21},
annote = {Keywords: Bidding Games, Parity Games, Mean-Payoff Games, Richman Games}
}
|
Keywords: |
|
Bidding Games, Parity Games, Mean-Payoff Games, Richman Games |
|
Collection: |
|
28th International Conference on Concurrency Theory (CONCUR 2017) |
|
Issue Date: |
|
2017 |
|
Date of publication: |
|
01.09.2017 |
