Reaching Your Goal Optimally by Playing at Random with No Memory - MOVE Modélisation et Vérification - LIS Laboratoire d'Informatique et Systèmes de Marseille (UMR 7020) Accéder directement au contenu
Communication Dans Un Congrès Année : 2020

Reaching Your Goal Optimally by Playing at Random with No Memory

Résumé

Shortest-path games are two-player zero-sum games played on a graph equipped with integer weights. One player, that we call Min, wants to reach a target set of states while minimising the total weight, and the other one has an antagonistic objective. This combination of a qualitative reachability objective and a quantitative total-payoff objective is one of the simplest settings where Min needs memory (pseudo-polynomial in the weights) to play optimally. In this article, we aim at studying a tradeoff allowing Min to play at random, but using no memory. We show that Min can achieve the same optimal value in both cases. In particular, we compute a randomised memoryless ε-optimal strategy when it exists, where probabilities are parametrised by ε. We also show that for some games, no optimal randomised strategies exist. We then characterise, and decide in polynomial time, the class of games admitting an optimal randomised memoryless strategy.
Fichier principal
Vignette du fichier
LIPIcs-CONCUR-2020-26.pdf (610.64 Ko) Télécharger le fichier
Origine : Fichiers éditeurs autorisés sur une archive ouverte
Loading...

Dates et versions

hal-02925540 , version 1 (30-08-2020)

Identifiants

Citer

Benjamin Monmege, Julie Parreaux, Pierre-Alain Reynier. Reaching Your Goal Optimally by Playing at Random with No Memory. 31st International Conference on Concurrency Theory (CONCUR 2020), 2020, Vienna, Austria. ⟨10.4230/LIPIcs.CONCUR.2020.26⟩. ⟨hal-02925540⟩
78 Consultations
44 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More