Solving Mean-Payoff Games via Quasi Dominions

We propose a novel algorithm for the solution of mean-payoff games that merges together two seemingly unrelated concepts introduced in the context of parity games, small progress measures and quasi dominions. We show that the integration of the two notions can be highly beneficial and significantly...

Descripción completa

Detalles Bibliográficos
Autores principales: Benerecetti, Massimo, Dell’Erba, Daniele, Mogavero, Fabio
Formato: Online Artículo Texto
Lenguaje:English
Publicado: 2020
Materias:
Article
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7480681/
http://dx.doi.org/10.1007/978-3-030-45237-7_18
_version_ 1783580457994027008
author Benerecetti, Massimo
Dell’Erba, Daniele
Mogavero, Fabio
author_facet Benerecetti, Massimo
Dell’Erba, Daniele
Mogavero, Fabio
author_sort Benerecetti, Massimo
collection PubMed
description We propose a novel algorithm for the solution of mean-payoff games that merges together two seemingly unrelated concepts introduced in the context of parity games, small progress measures and quasi dominions. We show that the integration of the two notions can be highly beneficial and significantly speeds up convergence to the problem solution. Experiments show that the resulting algorithm performs orders of magnitude better than the asymptotically-best solution algorithm currently known, without sacrificing on the worst-case complexity.
format Online
Article
Text
id pubmed-7480681
institution National Center for Biotechnology Information
language English
publishDate 2020
record_format MEDLINE/PubMed
spelling pubmed-74806812020-09-10 Solving Mean-Payoff Games via Quasi Dominions Benerecetti, Massimo Dell’Erba, Daniele Mogavero, Fabio Tools and Algorithms for the Construction and Analysis of Systems Article We propose a novel algorithm for the solution of mean-payoff games that merges together two seemingly unrelated concepts introduced in the context of parity games, small progress measures and quasi dominions. We show that the integration of the two notions can be highly beneficial and significantly speeds up convergence to the problem solution. Experiments show that the resulting algorithm performs orders of magnitude better than the asymptotically-best solution algorithm currently known, without sacrificing on the worst-case complexity. 2020-03-13 /pmc/articles/PMC7480681/ http://dx.doi.org/10.1007/978-3-030-45237-7_18 Text en © The Author(s) 2020 Open Access This chapter is licensed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made. The images or other third party material in this chapter are included in the chapter's Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the chapter's Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder.
spellingShingle Article
Benerecetti, Massimo
Dell’Erba, Daniele
Mogavero, Fabio
Solving Mean-Payoff Games via Quasi Dominions
title Solving Mean-Payoff Games via Quasi Dominions
title_full Solving Mean-Payoff Games via Quasi Dominions
title_fullStr Solving Mean-Payoff Games via Quasi Dominions
title_full_unstemmed Solving Mean-Payoff Games via Quasi Dominions
title_short Solving Mean-Payoff Games via Quasi Dominions
title_sort solving mean-payoff games via quasi dominions
topic Article
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7480681/
http://dx.doi.org/10.1007/978-3-030-45237-7_18
work_keys_str_mv AT benerecettimassimo solvingmeanpayoffgamesviaquasidominions
AT dellerbadaniele solvingmeanpayoffgamesviaquasidominions
AT mogaverofabio solvingmeanpayoffgamesviaquasidominions

Ejemplares similares