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.
Solving Mean-Payoff Games via Quasi Dominions / Benerecetti, M.; Dell'Erba, D.; Mogavero, F.. - 12079:(2020), pp. 289-306. [10.1007/978-3-030-45237-7_18]
Solving Mean-Payoff Games via Quasi Dominions
Benerecetti M.
;Dell'Erba D.
;Mogavero F.
2020
Abstract
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.File | Dimensione | Formato | |
---|---|---|---|
bdm(tacas20).pdf
accesso aperto
Tipologia:
Documento in Pre-print
Licenza:
Creative commons
Dimensione
623.51 kB
Formato
Adobe PDF
|
623.51 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.