All

What are you looking for?

All
Projects
Results
Organizations

Quick search

  • Projects supported by TA ČR
  • Excellent projects
  • Projects with the highest public support
  • Current projects

Smart search

  • That is how I find a specific +word
  • That is how I leave the -word out of the results
  • “That is how I can find the whole phrase”

Bidding Games on Markov Decision Processes

The result's identifiers

  • Result code in IS VaVaI

    <a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F19%3A00107914" target="_blank" >RIV/00216224:14330/19:00107914 - isvavai.cz</a>

  • Result on the web

    <a href="https://link.springer.com/chapter/10.1007/978-3-030-30806-3_1" target="_blank" >https://link.springer.com/chapter/10.1007/978-3-030-30806-3_1</a>

  • DOI - Digital Object Identifier

    <a href="http://dx.doi.org/10.1007/978-3-030-30806-3_1" target="_blank" >10.1007/978-3-030-30806-3_1</a>

Alternative languages

  • Result language

    angličtina

  • Original language name

    Bidding Games on Markov Decision Processes

  • Original language description

    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.

  • Czech name

  • Czech description

Classification

  • Type

    D - Article in proceedings

  • CEP classification

  • OECD FORD branch

    10200 - Computer and information sciences

Result continuities

  • Project

    <a href="/en/project/GJ19-15134Y" target="_blank" >GJ19-15134Y: Verification and Analysis of Probabilistic Programs</a><br>

  • Continuities

    P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Others

  • Publication year

    2019

  • Confidentiality

    S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Data specific for result type

  • Article name in the collection

    Reachability Problems - 13th International Conference, RP 2019, Brussels, Belgium, September 11-13, 2019, Proceedings.

  • ISBN

    9783030308056

  • ISSN

    0302-9743

  • e-ISSN

  • Number of pages

    12

  • Pages from-to

    1-12

  • Publisher name

    Springer

  • Place of publication

    Cham

  • Event location

    Brusel

  • Event date

    Jan 1, 2019

  • Type of event by nationality

    WRD - Celosvětová akce

  • UT code for WoS article