---
_id: '6822'
abstract:
- lang: eng
  text: "In two-player games on graphs, the players move a token through a graph to
    produce an infinite path, which determines the qualitative winner or quantitative
    payoff of the game. In bidding games, in each turn, we hold an auction between
    the two players to determine which player moves the token. Bidding games have
    largely been studied with concrete bidding mechanisms that are variants of a first-price
    auction: in each turn both players simultaneously submit bids, the higher\r\nbidder
    moves the token, and pays his bid to the lower bidder in Richman bidding, to the
    bank in poorman bidding, and in taxman bidding, the bid is split between the other
    player and the bank according to a predefined constant factor. Bidding games are
    deterministic games. They have an intriguing connection with a fragment of stochastic
    games called \r\n randomturn games. We study, for the first time, a combination
    of bidding games with probabilistic behavior; namely, we study bidding games that
    are played on Markov decision processes, where the players bid for the right to
    choose the next action, which determines the probability distribution according
    to which the next vertex is chosen. We study parity and meanpayoff bidding games
    on MDPs and extend results from the deterministic bidding setting to the probabilistic
    one."
alternative_title:
- LNCS
author:
- first_name: Guy
  full_name: Avni, Guy
  id: 463C8BC2-F248-11E8-B48F-1D18A9856A87
  last_name: Avni
  orcid: 0000-0001-5588-8287
- first_name: Thomas A
  full_name: Henzinger, Thomas A
  id: 40876CD8-F248-11E8-B48F-1D18A9856A87
  last_name: Henzinger
  orcid: 0000−0002−2985−7724
- first_name: Rasmus
  full_name: Ibsen-Jensen, Rasmus
  id: 3B699956-F248-11E8-B48F-1D18A9856A87
  last_name: Ibsen-Jensen
  orcid: 0000-0003-4783-0389
- first_name: Petr
  full_name: Novotny, Petr
  last_name: Novotny
citation:
  ama: 'Avni G, Henzinger TA, Ibsen-Jensen R, Novotny P. Bidding games on Markov decision
    processes. In: <i> Proceedings of the 13th International Conference of Reachability
    Problems</i>. Vol 11674. Springer; 2019:1-12. doi:<a href="https://doi.org/10.1007/978-3-030-30806-3_1">10.1007/978-3-030-30806-3_1</a>'
  apa: 'Avni, G., Henzinger, T. A., Ibsen-Jensen, R., &#38; Novotny, P. (2019). Bidding
    games on Markov decision processes. In <i> Proceedings of the 13th International
    Conference of Reachability Problems</i> (Vol. 11674, pp. 1–12). Brussels, Belgium:
    Springer. <a href="https://doi.org/10.1007/978-3-030-30806-3_1">https://doi.org/10.1007/978-3-030-30806-3_1</a>'
  chicago: Avni, Guy, Thomas A Henzinger, Rasmus Ibsen-Jensen, and Petr Novotny. “Bidding
    Games on Markov Decision Processes.” In <i> Proceedings of the 13th International
    Conference of Reachability Problems</i>, 11674:1–12. Springer, 2019. <a href="https://doi.org/10.1007/978-3-030-30806-3_1">https://doi.org/10.1007/978-3-030-30806-3_1</a>.
  ieee: G. Avni, T. A. Henzinger, R. Ibsen-Jensen, and P. Novotny, “Bidding games
    on Markov decision processes,” in <i> Proceedings of the 13th International Conference
    of Reachability Problems</i>, Brussels, Belgium, 2019, vol. 11674, pp. 1–12.
  ista: 'Avni G, Henzinger TA, Ibsen-Jensen R, Novotny P. 2019. Bidding games on Markov
    decision processes.  Proceedings of the 13th International Conference of Reachability
    Problems. RP: Reachability Problems, LNCS, vol. 11674, 1–12.'
  mla: Avni, Guy, et al. “Bidding Games on Markov Decision Processes.” <i> Proceedings
    of the 13th International Conference of Reachability Problems</i>, vol. 11674,
    Springer, 2019, pp. 1–12, doi:<a href="https://doi.org/10.1007/978-3-030-30806-3_1">10.1007/978-3-030-30806-3_1</a>.
  short: G. Avni, T.A. Henzinger, R. Ibsen-Jensen, P. Novotny, in:,  Proceedings of
    the 13th International Conference of Reachability Problems, Springer, 2019, pp.
    1–12.
conference:
  end_date: 2019-09-13
  location: Brussels, Belgium
  name: 'RP: Reachability Problems'
  start_date: 2019-09-11
date_created: 2019-08-19T07:58:10Z
date_published: 2019-09-06T00:00:00Z
date_updated: 2021-01-12T08:09:12Z
day: '06'
ddc:
- '000'
department:
- _id: ToHe
doi: 10.1007/978-3-030-30806-3_1
file:
- access_level: open_access
  checksum: 45ebbc709af2b247d28c7c293c01504b
  content_type: application/pdf
  creator: gavni
  date_created: 2019-08-19T07:56:40Z
  date_updated: 2020-07-14T12:47:41Z
  file_id: '6823'
  file_name: prob.pdf
  file_size: 436635
  relation: main_file
file_date_updated: 2020-07-14T12:47:41Z
has_accepted_license: '1'
intvolume: '     11674'
language:
- iso: eng
month: '09'
oa: 1
oa_version: Submitted Version
page: 1-12
project:
- _id: 264B3912-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: M02369
  name: Formal Methods meets Algorithmic Game Theory
- _id: 25F2ACDE-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: S11402-N23
  name: Rigorous Systems Engineering
- _id: 25F42A32-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: Z211
  name: The Wittgenstein Prize
publication: ' Proceedings of the 13th International Conference of Reachability Problems'
publication_identifier:
  isbn:
  - 978-303030805-6
  issn:
  - 0302-9743
publication_status: published
publisher: Springer
quality_controlled: '1'
scopus_import: 1
status: public
title: Bidding games on Markov decision processes
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 11674
year: '2019'
...