License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CONCUR.2021.27
URN: urn:nbn:de:0030-drops-144040
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14404/
Go to the corresponding LIPIcs Volume Portal

Bruyère, Véronique ; Raskin, Jean-François ; Tamines, Clément

Stackelberg-Pareto Synthesis

pdf-format:
LIPIcs-CONCUR-2021-27.pdf (0.7 MB)

Abstract

In this paper, we study the framework of two-player Stackelberg games played on graphs in which Player 0 announces a strategy and Player 1 responds rationally with a strategy that is an optimal response. While it is usually assumed that Player 1 has a single objective, we consider here the new setting where he has several. In this context, after responding with his strategy, Player 1 gets a payoff in the form of a vector of Booleans corresponding to his satisfied objectives. Rationality of Player 1 is encoded by the fact that his response must produce a Pareto-optimal payoff given the strategy of Player 0. We study the Stackelberg-Pareto Synthesis problem which asks whether Player 0 can announce a strategy which satisfies his objective, whatever the rational response of Player 1. For games in which objectives are either all parity or all reachability objectives, we show that this problem is fixed-parameter tractable and NEXPTIME-complete. This problem is already NP-complete in the simple case of reachability objectives and graphs that are trees.

BibTeX - Entry

@InProceedings{bruyere_et_al:LIPIcs.CONCUR.2021.27,
  author =	{Bruy\`{e}re, V\'{e}ronique and Raskin, Jean-Fran\c{c}ois and Tamines, Cl\'{e}ment},
  title =	{{Stackelberg-Pareto Synthesis}},
  booktitle =	{32nd International Conference on Concurrency Theory (CONCUR 2021)},
  pages =	{27:1--27:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-203-7},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{203},
  editor =	{Haddad, Serge and Varacca, Daniele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/14404},
  URN =		{urn:nbn:de:0030-drops-144040},
  doi =		{10.4230/LIPIcs.CONCUR.2021.27},
  annote =	{Keywords: Stackelberg non-zero sum games played on graphs, synthesis, parity objectives}
}

Keywords: Stackelberg non-zero sum games played on graphs, synthesis, parity objectives
Collection: 32nd International Conference on Concurrency Theory (CONCUR 2021)
Issue Date: 2021
Date of publication: 13.08.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI