DROPS

Document

DOI: 10.4230/LIPIcs.CONCUR.2026.14

Asymmetrically Discounted Stochastic Games

Authors: Sarvin Bahmani, Soumyajit Paul, Sven Schewe, Shadi Tasdighi Kalat, and Ashutosh Trivedi

Published in: LIPIcs, Volume 391, 37th International Conference on Concurrency Theory (CONCUR 2026)

Abstract

We study asymmetrically discounted stochastic games, in which players use distinct and reasonably apart discount factors. We show that optimal strategies in these games may require both memory and randomisation, in contrast to the classical symmetrically discounted setting. Our main technical contribution establishes that computing incentive Stackelberg equilibria - a variant of Stackelberg equilibria in which one player, called Player Max, can offer payments to the other player, called Player Min - is no harder than solving classical discounted games. We further show that optimal strategies in this setting can be realised by finite counting strategies, whereas restricting players to stationary strategies makes the problem computationally intractable. Finally, we establish that computing classical Stackelberg equilibria in these games under the constraint of memoryless strategies is NP-complete and remains NP-hard even when general or counting strategies are allowed.

Cite as

Sarvin Bahmani, Soumyajit Paul, Sven Schewe, Shadi Tasdighi Kalat, and Ashutosh Trivedi. Asymmetrically Discounted Stochastic Games. In 37th International Conference on Concurrency Theory (CONCUR 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 391, pp. 14:1-14:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bahmani_et_al:LIPIcs.CONCUR.2026.14,
  author =	{Bahmani, Sarvin and Paul, Soumyajit and Schewe, Sven and Kalat, Shadi Tasdighi and Trivedi, Ashutosh},
  title =	{{Asymmetrically Discounted Stochastic Games}},
  booktitle =	{37th International Conference on Concurrency Theory (CONCUR 2026)},
  pages =	{14:1--14:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-447-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{391},
  editor =	{Sokolova, Ana and Totzke, Patrick},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2026.14},
  URN =		{urn:nbn:de:0030-drops-273453},
  doi =		{10.4230/LIPIcs.CONCUR.2026.14},
  annote =	{Keywords: Stochastic Games, Asymmetric Discounting, Stackelberg Equilibrium}
}

Search Results

Documents authored by Kalat, Shadi Tasdighi

Asymmetrically Discounted Stochastic Games

Abstract

Cite as

Thanks for your feedback!

Could not send message