Asymmetrically-Discounted Stochastic Games
Sarvin Bahmani, Soumyajit Paul, Sven Schewe, Shadi Tasdighi Kalat, Ashutosh Trivedi
We study asymmetrically discounted stochastic games, in which players use distinct discount factors. We show that optimal strategies in these games may require both memory and randomization, 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 realized 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.