Bidding Games on Markov Decision Processes with Quantitative
Reachability Objectives

D 2025

Bidding Games on Markov Decision Processes with Quantitative Reachability Objectives

AVNI, Guy; Martin KUREČKA; Kaushik MALLIK; Petr NOVOTNÝ; Suman SADHUKHAN et al.

Základní údaje

Originální název

Bidding Games on Markov Decision Processes with Quantitative Reachability Objectives

Autoři

AVNI, Guy; Martin KUREČKA; Kaushik MALLIK; Petr NOVOTNÝ a Suman SADHUKHAN

Vydání

Richland (SC), Proceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems, od s. 161-169, 9 s. 2025

Nakladatel

International Foundation for Autonomous Agents and Multiagent Systems

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10200 1.2 Computer and information sciences

Stát vydavatele

Spojené státy

Utajení

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

Forma vydání

tištěná verze "print"

Odkazy

URL

Označené pro přenos do RIV

Ano

Kód RIV

RIV/00216224:14330/25:00141809

Organizační jednotka

Fakulta informatiky

ISBN

979-8-4007-1426-9

EID Scopus

2-s2.0-105009844746

Klíčová slova anglicky

Markov decision processes; bidding games; graph games

Štítky

core_A, firank_1

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 9. 4. 2026 12:02, RNDr. Pavel Šmerk, Ph.D.

Anotace

V originále

Graph games are fundamental in strategic reasoning of multi-agent systems and their environments. We study a new family of graph games which combine stochastic environmental uncertainties and auction-based interactions among the agents, formalized as bidding games on (finite) Markov decision processes (MDP). Normally, on MDPs, a single decision-maker chooses a sequence of actions, producing a probability distribution over infinite paths. In bidding games on MDPs, two players---called the reachability and safety players---bid for the privilege of choosing the next action at each step. The reachability player's goal is to maximize the probability of reaching a given target vertex, whereas the safety player's goal is to minimize it. These games generalize traditional bidding games on graphs, and the existing analysis techniques do not extend. For instance, the central property of bidding games on graphs is the existence of a threshold budget, which is the necessary and sufficient budget to guarantee winning for the reachability player. For MDPs, the threshold becomes a relation between budgets and probabilities of reaching the target. We devise value-iteration algorithms that approximate thresholds and optimal policies for general MDPs, and compute the exact solutions for acyclic MDPs, and show that finding thresholds is at least as hard as simple-stochastic games.

Návaznosti

GA23-06963S, projekt VaV

Název: VESCAA: Verifikovatelná a efektivní syntéza kontrolerů pro autonomní agenty

Investor: Grantová agentura ČR, VESCAA: Verifikovatelná a efektivní syntéza kontrolerů pro autonomní agenty

MUNI/A/1600/2024, interní kód MU

Název: Modelování, analýza a verifikace (2025)

Investor: Masarykova univerzita, Modelování, analýza a verifikace (2025)

MUNI/A/1666/2024, interní kód MU

Název: Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity 25

Investor: Masarykova univerzita, Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity 25

Citovat

AVNI, Guy; Martin KUREČKA; Kaushik MALLIK; Petr NOVOTNÝ a Suman SADHUKHAN. Bidding Games on Markov Decision Processes with Quantitative Reachability Objectives. In Proceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems. Richland (SC): International Foundation for Autonomous Agents and Multiagent Systems, 2025, s. 161-169. ISBN 979-8-4007-1426-9.

@inproceedings{2513138,
   author = {Avni, Guy and Kurečka, Martin and Mallik, Kaushik and Novotný, Petr and Sadhukhan, Suman},
   address = {Richland (SC)},
   booktitle = {Proceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems},
   keywords = {Markov decision processes; bidding games; graph games},
   howpublished = {tištěná verze "print"},
   language = {eng},
   location = {Richland (SC)},
   isbn = {979-8-4007-1426-9},
   pages = {161-169},
   publisher = {International Foundation for Autonomous Agents and Multiagent Systems},
   title = {Bidding Games on Markov Decision Processes with Quantitative Reachability Objectives},
   url = {https://www.ifaamas.org/Proceedings/aamas2025/pdfs/p161.pdf},
   year = {2025}
}

TY  - CONF
ID  - 2513138
AU  - Avni, Guy - Kurečka, Martin - Mallik, Kaushik - Novotný, Petr - Sadhukhan, Suman
PY  - 2025
TI  - Bidding Games on Markov Decision Processes with Quantitative Reachability Objectives
PB  - International Foundation for Autonomous Agents and Multiagent Systems
CY  - Richland (SC)
SN  - 9798400714269
KW  - Markov decision processes
KW  - bidding games
KW  - graph games
UR  - https://www.ifaamas.org/Proceedings/aamas2025/pdfs/p161.pdf
N2  - Graph games are fundamental in strategic reasoning of multi-agent systems and their environments. We study a new family of graph games which combine stochastic environmental uncertainties and auction-based interactions among the agents, formalized as bidding games on (finite) Markov decision processes (MDP). Normally, on MDPs, a single decision-maker chooses a sequence of actions, producing a probability distribution over infinite paths. In bidding games on MDPs, two players---called the reachability and safety players---bid for the privilege of choosing the next action at each step. The reachability player's goal is to maximize the probability of reaching a given target vertex, whereas the safety player's goal is to minimize it. These games generalize traditional bidding games on graphs, and the existing analysis techniques do not extend. For instance, the central property of bidding games on graphs is the existence of a threshold budget, which is the necessary and sufficient budget to guarantee winning for the reachability player. For MDPs, the threshold becomes a relation between budgets and probabilities of reaching the target. We devise value-iteration algorithms that approximate thresholds and optimal policies for general MDPs, and compute the exact solutions for acyclic MDPs, and show that finding thresholds is at least as hard as simple-stochastic games.
ER  -

AVNI, Guy; Martin KUREČKA; Kaushik MALLIK; Petr NOVOTNÝ a Suman SADHUKHAN. Bidding Games on Markov Decision Processes with Quantitative Reachability Objectives. In \textit{Proceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems}. Richland (SC): International Foundation for Autonomous Agents and Multiagent Systems, 2025, s.~161-169. ISBN~979-8-4007-1426-9.

Přehled o publikaci