Detailed Information on Publication Record
2019
Bidding Games on Markov Decision Processes
AVNI, Guy, Thomas A. HENZINGER, Rasmus IBSEN-JENSEN and Petr NOVOTNÝBasic information
Original name
Bidding Games on Markov Decision Processes
Authors
AVNI, Guy (376 Israel), Thomas A. HENZINGER (40 Austria), Rasmus IBSEN-JENSEN (208 Denmark) and Petr NOVOTNÝ (203 Czech Republic, guarantor, belonging to the institution)
Edition
Cham, Reachability Problems - 13th International Conference, RP 2019, Brussels, Belgium, September 11-13, 2019, Proceedings. p. 1-12, 12 pp. 2019
Publisher
Springer
Other information
Language
English
Type of outcome
Stať ve sborníku
Field of Study
10200 1.2 Computer and information sciences
Country of publisher
Switzerland
Confidentiality degree
není předmětem státního či obchodního tajemství
Publication form
printed version "print"
References:
Impact factor
Impact factor: 0.402 in 2005
RIV identification code
RIV/00216224:14330/19:00107914
Organization unit
Faculty of Informatics
ISBN
978-3-030-30805-6
ISSN
Keywords in English
Game theory; Markov processes; Stochastic systems; Bidding mechanism
Tags
Tags
International impact
Změněno: 17/4/2020 12:22, doc. RNDr. Petr Novotný, Ph.D.
Abstract
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.
Links
GA19-15134Y, interní kód MU |
| ||
GJ19-15134Y, research and development project |
|