---
_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: Proceedings of the 13th International Conference of Reachability
Problems. Vol 11674. Springer; 2019:1-12. doi:10.1007/978-3-030-30806-3_1'
apa: 'Avni, G., Henzinger, T. A., Ibsen-Jensen, R., & Novotny, P. (2019). Bidding
games on Markov decision processes. In Proceedings of the 13th International
Conference of Reachability Problems (Vol. 11674, pp. 1–12). Brussels, Belgium:
Springer. https://doi.org/10.1007/978-3-030-30806-3_1'
chicago: Avni, Guy, Thomas A Henzinger, Rasmus Ibsen-Jensen, and Petr Novotny. “Bidding
Games on Markov Decision Processes.” In Proceedings of the 13th International
Conference of Reachability Problems, 11674:1–12. Springer, 2019. https://doi.org/10.1007/978-3-030-30806-3_1.
ieee: G. Avni, T. A. Henzinger, R. Ibsen-Jensen, and P. Novotny, “Bidding games
on Markov decision processes,” in Proceedings of the 13th International Conference
of Reachability Problems, 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.” Proceedings
of the 13th International Conference of Reachability Problems, vol. 11674,
Springer, 2019, pp. 1–12, doi:10.1007/978-3-030-30806-3_1.
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'
...