Bidding Games on Markov Decision Processes with Quantitative Reachability Objectives

Result code in 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>

Result on the web

<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

—

Result language

angličtina

Original language name

Bidding Games on Markov Decision Processes with Quantitative Reachability Objectives

Original language description

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.

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

—

OECD FORD branch

10200 - Computer and information sciences

Project

<a href="/en/project/GA23-06963S" target="_blank" >GA23-06963S: VESCAA: Verifiable and Efficient Synthesis of Controllers for Autonomous Agents</a><br>

Continuities

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

Publication year

2025

Confidentiality

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

Article name in the collection

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

ISBN

9798400714269

ISSN

—

e-ISSN

—

Number of pages

9

Pages from-to

161-169

Publisher name

International Foundation for Autonomous Agents and Multiagent Systems

Place of publication

Richland (SC)

Event location

Detroit

Event date

Jan 1, 2025

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—