5 papers · 1 filter
Algorithms with Smoothed Polynomial-Time Complexity for Deterministic Discounted-sum and Mean-payoff Games
Ali Asadi, Krishnendu Chatterjee, Ruichen Luo
Turn-based deterministic games on graphs are two-player zero-sum games played on finite directed graphs, where the vertex set is partitioned between the Max and the adversarial Min…
Generalized Bidding Games: Where Bidding and Stochastic Games Meet
Ali Asadi, Thomas A. Henzinger, Ehsan Kafshdar Goharshady +2
Two-player games on graphs are a classical framework for analyzing strategic decision making. In turn-based games, two players move a token along the edges of the graph, and the ri…
ε-Stationary Nash Equilibria in Multi-player Stochastic Graph Games
Ali Asadi, Léonard Brice, Krishnendu Chatterjee +1
A strategy profile in a multi-player game is a Nash equilibrium if no player can unilaterally deviate to achieve a strictly better payoff. A profile is an -Nash equilibrium if n…
Deterministic Sub-exponential Algorithm for Discounted-sum Games with Unary Weights
Ali Asadi, Krishnendu Chatterjee, Raimundo Saona +1
Turn-based discounted-sum games are two-player zero-sum games played on finite directed graphs. The vertices of the graph are partitioned between player 1 and player 2. Plays are i…
Concurrent Stochastic Games with Stateful-discounted and Parity Objectives: Complexity and Algorithms
Ali Asadi, Krishnendu Chatterjee, Raimundo Saona +1
We study two-player zero-sum concurrent stochastic games with finite state and action space played for an infinite number of steps. In every step, the two players simultaneously an…