DROPS

Document

DOI: 10.4230/LIPIcs.CSL.2023.7

A Lattice-Theoretical View of Strategy Iteration

Authors: Paolo Baldan, Richard Eggert, Barbara König, and Tommaso Padoan

Published in: LIPIcs, Volume 252, 31st EACSL Annual Conference on Computer Science Logic (CSL 2023)

Abstract

Strategy iteration is a technique frequently used for two-player games in order to determine the winner or compute payoffs, but to the best of our knowledge no general framework for strategy iteration has been considered. Inspired by previous work on simple stochastic games, we propose a general formalisation of strategy iteration for solving least fixpoint equations over a suitable class of complete lattices, based on MV-chains. We devise algorithms that can be used for non-expansive fixpoint functions represented as so-called min- respectively max-decompositions. Correspondingly, we develop two different techniques: strategy iteration from above, which has to solve the problem that iteration might reach a fixpoint that is not the least, and from below, which is algorithmically simpler, but requires a more involved correctness argument. We apply our method to solve energy games and compute behavioural metrics for probabilistic automata.

Cite as

Paolo Baldan, Richard Eggert, Barbara König, and Tommaso Padoan. A Lattice-Theoretical View of Strategy Iteration. In 31st EACSL Annual Conference on Computer Science Logic (CSL 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 252, pp. 7:1-7:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{baldan_et_al:LIPIcs.CSL.2023.7,
  author =	{Baldan, Paolo and Eggert, Richard and K\"{o}nig, Barbara and Padoan, Tommaso},
  title =	{{A Lattice-Theoretical View of Strategy Iteration}},
  booktitle =	{31st EACSL Annual Conference on Computer Science Logic (CSL 2023)},
  pages =	{7:1--7:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-264-8},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{252},
  editor =	{Klin, Bartek and Pimentel, Elaine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2023.7},
  URN =		{urn:nbn:de:0030-drops-174680},
  doi =		{10.4230/LIPIcs.CSL.2023.7},
  annote =	{Keywords: games, strategy iteration, fixpoints, energy games, behavioural metrics}
}

Search Results

Documents authored by Eggert, Richard

A Lattice-Theoretical View of Strategy Iteration

Abstract

Cite as

Thanks for your feedback!

Could not send message