Bidding Games on Markov Decision Processes

D 2019

Bidding Games on Markov Decision Processes

AVNI, Guy, Thomas A. HENZINGER, Rasmus IBSEN-JENSEN a Petr NOVOTNÝ

Základní údaje

Originální název

Bidding Games on Markov Decision Processes

Autoři

AVNI, Guy (376 Izrael), Thomas A. HENZINGER (40 Rakousko), Rasmus IBSEN-JENSEN (208 Dánsko) a Petr NOVOTNÝ (203 Česká republika, garant, domácí)

Vydání

Cham, Reachability Problems - 13th International Conference, RP 2019, Brussels, Belgium, September 11-13, 2019, Proceedings. od s. 1-12, 12 s. 2019

Nakladatel

Springer

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10200 1.2 Computer and information sciences

Stát vydavatele

Švýcarsko

Utajení

není předmětem státního či obchodního tajemství

Forma vydání

tištěná verze "print"

Odkazy

URL

Impakt faktor

Impact factor: 0.402 v roce 2005

Kód RIV

RIV/00216224:14330/19:00107914

Organizační jednotka

Fakulta informatiky

ISBN

978-3-030-30805-6

ISSN

DOI

http://dx.doi.org/10.1007/978-3-030-30806-3_1

Klíčová slova anglicky

Game theory; Markov processes; Stochastic systems; Bidding mechanism

Štítky

formela-ver

Příznaky

Mezinárodní význam

Změněno: 17. 4. 2020 12:22, doc. RNDr. Petr Novotný, Ph.D.

Anotace

V originále

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 bidder 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 random-turn 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 mean-payoff bidding games on MDPs and extend results from the deterministic bidding setting to the probabilistic one.

Návaznosti

GA19-15134Y, interní kód MU

Název: Verifikace a analýza pravděpodobnostních programů

Investor: Grantová agentura ČR, Verifikace a analýza pravděpodobnostních programů

GJ19-15134Y, projekt VaV

Název: Verifikace a analýza pravděpodobnostních programů

Citovat

AVNI, Guy, Thomas A. HENZINGER, Rasmus IBSEN-JENSEN a Petr NOVOTNÝ. Bidding Games on Markov Decision Processes. In Emmanuel Filiot, Raphaël M. Jungers, Igor Potapov. Reachability Problems - 13th International Conference, RP 2019, Brussels, Belgium, September 11-13, 2019, Proceedings. Cham: Springer, 2019, s. 1-12. ISBN 978-3-030-30805-6. Dostupné z: https://dx.doi.org/10.1007/978-3-030-30806-3_1.

@inproceedings{1598257,
   author = {Avni, Guy and Henzinger, Thomas A. and IbsenandJensen, Rasmus and Novotný, Petr},
   address = {Cham},
   booktitle = {Reachability Problems - 13th International Conference, RP 2019, Brussels, Belgium, September 11-13, 2019, Proceedings.},
   doi = {http://dx.doi.org/10.1007/978-3-030-30806-3_1},
   editor = {Emmanuel Filiot, Raphaël M. Jungers, Igor Potapov},
   keywords = {Game theory; Markov processes; Stochastic systems; Bidding mechanism},
   howpublished = {tištěná verze "print"},
   language = {eng},
   location = {Cham},
   isbn = {978-3-030-30805-6},
   pages = {1-12},
   publisher = {Springer},
   title = {Bidding Games on Markov Decision Processes},
   url = {https://link.springer.com/chapter/10.1007/978-3-030-30806-3_1},
   year = {2019}
}

TY  - JOUR
ID  - 1598257
AU  - Avni, Guy - Henzinger, Thomas A. - Ibsen-Jensen, Rasmus - Novotný, Petr
PY  - 2019
TI  - Bidding Games on Markov Decision Processes
PB  - Springer
CY  - Cham
SN  - 9783030308056
KW  - Game theory
KW  - Markov processes
KW  - Stochastic systems
KW  - Bidding mechanism
UR  - https://link.springer.com/chapter/10.1007/978-3-030-30806-3_1
L2  - https://link.springer.com/chapter/10.1007/978-3-030-30806-3_1
N2  - 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 bidder 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 random-turn 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 mean-payoff bidding games on MDPs and extend results from the deterministic bidding setting to the probabilistic one.
ER  -

AVNI, Guy, Thomas A. HENZINGER, Rasmus IBSEN-JENSEN a Petr NOVOTNÝ. Bidding Games on Markov Decision Processes. In Emmanuel Filiot, Rapha\"el M. Jungers, Igor Potapov. \textit{Reachability Problems - 13th International Conference, RP 2019, Brussels, Belgium, September 11-13, 2019, Proceedings.}. Cham: Springer, 2019, s.~1-12. ISBN~978-3-030-30805-6. Dostupné z: https://dx.doi.org/10.1007/978-3-030-30806-3\_{}1.

Podrobný výpis o publikaci