2026-07-22T11:19:25Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14385 2024-03-06T10:54:16Z ddc:004 open_access

Subgame-Perfect Equilibria in Mean-Payoff Games Brice, Léonard Raskin, Jean-François van den Bogaard, Marie Games on graphs subgame-perfect equilibria mean-payoff objectives. In this paper, we provide an effective characterization of all the subgame-perfect equilibria in infinite duration games played on finite graphs with mean-payoff objectives. To this end, we introduce the notion of requirement, and the notion of negotiation function. We establish that the plays that are supported by SPEs are exactly those that are consistent with the least fixed point of the negotiation function. Finally, we show that the negotiation function is piecewise linear, and can be analyzed using the linear algebraic tool box. As a corollary, we prove the decidability of the SPE constrained existence problem, whose status was left open in the literature. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Léonard Brice and Jean-François Raskin and Marie van den Bogaard 2021 Is Part Of LIPIcs, Volume 203, 32nd International Conference on Concurrency Theory (CONCUR 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CONCUR.2021.8 urn:nbn:de:0030-drops-143854 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2021.8 eng https://creativecommons.org/licenses/by/4.0/legalcode