2026-07-21T23:19:37Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18560 2024-03-06T11:02:07Z ddc:004 open_access

Rational Verification for Nash and Subgame-Perfect Equilibria in Graph Games Brice, Léonard Raskin, Jean-François van den Bogaard, Marie Games on graphs Nash equilibria subgame-perfect equilibria We study a natural problem about rational behaviors in multiplayer non-zero-sum sequential infinite duration games played on graphs: rational verification, that consists in deciding whether all the rational answers to a given strategy satisfy some specification. We give the complexities of that problem for two major concepts of rationality: Nash equilibria and subgame-perfect equilibria, and for three major classes of payoff functions: energy, discounted-sum, and mean-payoff. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Léonard Brice and Jean-François Raskin and Marie van den Bogaard 2023 Is Part Of LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2023.26 urn:nbn:de:0030-drops-185608 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.26 eng https://creativecommons.org/licenses/by/4.0/legalcode