License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CSL.2015.504
URN: urn:nbn:de:0030-drops-54345
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5434/
Brihaye, Thomas ;
Bruyère, Véronique ;
Meunier, Noémie ;
Raskin, Jean-Francois
Weak Subgame Perfect Equilibria and their Application to Quantitative Reachability
Abstract
We study n-player turn-based games played on a finite directed graph. For each play, the players have to pay a cost that they want to minimize. Instead of the well-known notion of Nash equilibrium (NE), we focus on the notion of subgame perfect equilibrium (SPE), a refinement of NE well-suited in the framework of games played on graphs. We also study natural variants of SPE, named weak (resp. very weak) SPE, where players who deviate cannot use the full class of strategies but only a subclass with a finite number of (resp. a unique) deviation step(s).
Our results are threefold. Firstly, we characterize in the form of a Folk theorem the set of all plays that are the outcome of a weak SPE. Secondly, for the class of quantitative reachability games, we prove the existence of a finite-memory SPE and provide an algorithm for computing it (only existence was known with no information regarding the memory). Moreover, we show that the existence of a constrained SPE, i.e. an SPE such that each player pays a cost less than a given constant, can be decided. The proofs rely on our Folk theorem for weak SPEs (which coincide with SPEs in the case of quantitative reachability games) and on the decidability of MSO logic on infinite words. Finally with similar techniques, we provide a second general class of games for which the existence of a (constrained) weak SPE is decidable.
BibTeX - Entry
@InProceedings{brihaye_et_al:LIPIcs:2015:5434,
author = {Thomas Brihaye and V{\'e}ronique Bruy{\`e}re and No{\'e}mie Meunier and Jean-Francois Raskin},
title = {{Weak Subgame Perfect Equilibria and their Application to Quantitative Reachability}},
booktitle = {24th EACSL Annual Conference on Computer Science Logic (CSL 2015)},
pages = {504--518},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-90-3},
ISSN = {1868-8969},
year = {2015},
volume = {41},
editor = {Stephan Kreutzer},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/5434},
URN = {urn:nbn:de:0030-drops-54345},
doi = {10.4230/LIPIcs.CSL.2015.504},
annote = {Keywords: multi-player games on graphs, quantitative objectives, Nash equilibrium, subgame perfect equilibrium, quantitative reachability}
}
|
Keywords: |
|
multi-player games on graphs, quantitative objectives, Nash equilibrium, subgame perfect equilibrium, quantitative reachability |
|
Collection: |
|
24th EACSL Annual Conference on Computer Science Logic (CSL 2015) |
|
Issue Date: |
|
2015 |
|
Date of publication: |
|
07.09.2015 |
