---
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
    orcid: 0000-0001-5588-8287
  - 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_identifier:
  - UT:000487714900008
  dct_isPartOf:
  - http://id.crossref.org/issn/0004-5411
  - http://id.crossref.org/issn/1557-735X
  dct_language: eng
  dct_publisher: ACM@
  dct_title: Infinite-duration bidding games@
...