From the 1 of 7 linked papers with an AI index.
7 papers
Generalised Reachability Games
Sougata Bose, Nathanael Fijalkow, Daniel Hausmann +4
The paper investigates two-player turn-based games on graphs where a player must visit multiple target sets (generalised reachability), analyzing the computational complexity, para…
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…
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…
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…