8 papers
Automata-Theoretic Verification of Interval Markov Decision Processes
Sarvin Bahmani, Soumyajit Paul, Sven Schewe +2
Interval Markov decision processes (IMDPs) provide a natural framework for modeling stochastic systems with uncertain transition probabilities, represented by probability intervals…
Generalised Reachability Games
Sougata Bose, Nathanael Fijalkow, Daniel Hausmann +4
We study two-player zero-sum turn-based games played on graphs with multiple reachability objectives called generalised reachability games. In classic reachability games the goal o…
Social Welfare under Heterogeneous Time Preferences
Sarvin Bahmani, Soumyajit Paul, Sven Schewe +2
In several socioeconomic-critical decision-making settings, such as fair resource allocation, climate policy, or AI alignment, multiple principals interact within a common arena. W…
The Complexity of Games with Randomised Control
Sarvin Bahmani, Rasmus Ibsen-Jensen, Soumyajit Paul +5
We study the complexity of solving two-player infinite duration games played on a fixed finite graph, where the control of a node is not predetermined but rather assigned randomly.…
Generalised Reachability Games Revisited
Sougata Bose, Daniel Hausmann, Soumyajit Paul +2
Classic reachability games on graphs are zero-sum games, where the goal of one player, Eve, is to visit a vertex from a given target set, and that of other player, Adam, is to prev…
On the Complexity of the Optimal Correlated Equilibria in Extensive-Form Games
Vincent Cheval, Florian Horn, Soumyajit Paul +1
A major open question in algorithmic game theory is whether normal-form correlated equilibria (NFCE) can be computed efficiently in succinct games such as extensive-form games. Mot…
Resolving Nondeterminism by Chance
Soumyajit Paul, David Purser, Sven Schewe +3
History-deterministic automata are those in which nondeterministic choices can be correctly resolved stepwise: there is a strategy to select a continuation of a run given the next…
Simplifying imperfect recall games
Hugo Gimbert, Soumyajit Paul, B. Srivathsan
In games with imperfect recall, players may forget the sequence of decisions they made in the past. When players also forget whether they have already encountered their current dec…