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.2023.19
URN: urn:nbn:de:0030-drops-190137
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/19013/
Go to the corresponding LIPIcs Volume Portal

Kupferman, Orna ; Shenwald, Noam

Games with Trading of Control

pdf-format:
LIPIcs-CONCUR-2023-19.pdf (1.0 MB)

Abstract

The interaction among components in a system is traditionally modeled by a game. In the turned-based setting, the players in the game jointly move a token along the game graph, with each player deciding where to move the token in vertices she controls. The objectives of the players are modeled by ω-regular winning conditions, and players whose objectives are satisfied get rewards. Thus, the game is non-zero-sum, and we are interested in its stable outcomes. In particular, in the rational-synthesis problem, we seek a strategy for the system player that guarantees the satisfaction of the system’s objective in all rational environments. In this paper, we study an extension of the traditional setting by trading of control. In our game, the players may pay each other in exchange for directing the token also in vertices they do not control. The utility of each player then combines the reward for the satisfaction of her objective and the profit from the trading. The setting combines challenges from ω-regular graph games with challenges in pricing, bidding, and auctions in classical game theory. We study the theoretical properties of parity trading games: best-response dynamics, existence and search for Nash equilibria, and measures for equilibrium inefficiency. We also study the rational-synthesis problem and analyze its tight complexity in various settings.

BibTeX - Entry

@InProceedings{kupferman_et_al:LIPIcs.CONCUR.2023.19,
  author =	{Kupferman, Orna and Shenwald, Noam},
  title =	{{Games with Trading of Control}},
  booktitle =	{34th International Conference on Concurrency Theory (CONCUR 2023)},
  pages =	{19:1--19:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-299-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{279},
  editor =	{P\'{e}rez, Guillermo A. and Raskin, Jean-Fran\c{c}ois},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/19013},
  URN =		{urn:nbn:de:0030-drops-190137},
  doi =		{10.4230/LIPIcs.CONCUR.2023.19},
  annote =	{Keywords: Parity Games, Rational Synthesis, Game Theory, Auctions}
}

Keywords: Parity Games, Rational Synthesis, Game Theory, Auctions
Collection: 34th International Conference on Concurrency Theory (CONCUR 2023)
Issue Date: 2023
Date of publication: 07.09.2023

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