---
res:
bibo_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. The following bidding rule was previously
defined and called Richman bidding. Both players have separate 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 threshold budget in a vertex is a value t ∈ [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
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.@eng'
bibo_authorlist:
- foaf_Person:
foaf_givenName: Guy
foaf_name: Avni, Guy
foaf_surname: Avni
foaf_workInfoHomepage: http://www.librecat.org/personId=463C8BC2-F248-11E8-B48F-1D18A9856A87
- foaf_Person:
foaf_givenName: Thomas A
foaf_name: Henzinger, Thomas A
foaf_surname: Henzinger
foaf_workInfoHomepage: http://www.librecat.org/personId=40876CD8-F248-11E8-B48F-1D18A9856A87
orcid: 0000−0002−2985−7724
- foaf_Person:
foaf_givenName: Ventsislav K
foaf_name: Chonev, Ventsislav K
foaf_surname: Chonev
foaf_workInfoHomepage: http://www.librecat.org/personId=36CBE2E6-F248-11E8-B48F-1D18A9856A87
bibo_doi: 10.1145/3340295
bibo_issue: '4'
bibo_volume: 66
dct_date: 2019^xs_gYear
dct_isPartOf:
- http://id.crossref.org/issn/00045411
- http://id.crossref.org/issn/1557735X
dct_language: eng
dct_publisher: ACM@
dct_title: Infinite-duration bidding games@
...