Bidding Games on Markov Decision Processes with Quantitative Reachability Objectives

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F25%3A00141809" target="_blank" >RIV/00216224:14330/25:00141809 - isvavai.cz</a>

Výsledek na webu

<a href="https://www.ifaamas.org/Proceedings/aamas2025/pdfs/p161.pdf" target="_blank" >https://www.ifaamas.org/Proceedings/aamas2025/pdfs/p161.pdf</a>

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Bidding Games on Markov Decision Processes with Quantitative Reachability Objectives

Popis výsledku v původním jazyce

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ázev v anglickém jazyce

Bidding Games on Markov Decision Processes with Quantitative Reachability Objectives

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10200 - Computer and information sciences

Projekt

<a href="/cs/project/GA23-06963S" target="_blank" >GA23-06963S: VESCAA: Verifikovatelná a efektivní syntéza kontrolerů pro autonomní agenty</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2025

Kód důvěrnosti údajů

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

Název statě ve sborníku

Proceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems

ISBN

9798400714269

ISSN

—

e-ISSN

—

Počet stran výsledku

9

Strana od-do

161-169

Název nakladatele

International Foundation for Autonomous Agents and Multiagent Systems

Místo vydání

Richland (SC)

Místo konání akce

Detroit

Datum konání akce

1. 1. 2025

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—