License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CONCUR.2020.26
URN: urn:nbn:de:0030-drops-128381
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12838/
Go to the corresponding LIPIcs Volume Portal

Monmege, Benjamin ; Parreaux, Julie ; Reynier, Pierre-Alain

Reaching Your Goal Optimally by Playing at Random with No Memory

pdf-format:
LIPIcs-CONCUR-2020-26.pdf (0.6 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{monmege_et_al:LIPIcs:2020:12838,
  author =	{Benjamin Monmege and Julie Parreaux and Pierre-Alain Reynier},
  title =	{{Reaching Your Goal Optimally by Playing at Random with No Memory}},
  booktitle =	{31st International Conference on Concurrency Theory (CONCUR 2020)},
  pages =	{26:1--26:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-160-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{171},
  editor =	{Igor Konnov and Laura Kov{\'a}cs},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12838},
  URN =		{urn:nbn:de:0030-drops-128381},
  doi =		{10.4230/LIPIcs.CONCUR.2020.26},
  annote =	{Keywords: Weighted games, Algorithmic game theory, Randomisation}
}

Keywords: Weighted games, Algorithmic game theory, Randomisation
Collection: 31st International Conference on Concurrency Theory (CONCUR 2020)
Issue Date: 2020
Date of publication: 26.08.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI