5 citations · 13 across the 15 of their papers we have counts for
18 papers
Algorithms for Equilibria in Concurrent Stopping Games
Léonard Brice, Thomas A. Henzinger, K. S. Thejaswini
Concurrent games are a standard model for multi-agent systems, with Nash equilibrium as their central solution concept. The associated \emph{constrained existence problem}---does a…
Decoupled Planning for Multiple Omega-Regular Objectives
Guy Avni, Thomas A. Henzinger, Kaushik Mallik +2
We study the problem of generating paths on a graph that satisfy a collection of ω-regular objectives. We propose a decoupled framework in which each objective is assigned to an in…
Sharing The Secret: Distributed Privacy-Preserving Monitoring
Mahyar Karimi, K. S. Thejaswini, Roderick Bloem +1
In traditional runtime verification, a system is typically observed by a monolithic monitor. Enforcing privacy in such settings is computationally expensive, as it necessitates hea…
History-Deterministic Büchi Automata are Succinct
Antonio Casares, Keya Prakash, K. S. Thejaswini
We describe a history-deterministic Büchi automaton that has strictly less states than every language-equivalent deterministic Büchi automaton. This solves a problem that had been…
Randomise Alone, Reach as a Team
Léonard Brice, Thomas A. Henzinger, Alipasha Montaseri +2
We study concurrent graph games where n players cooperate against an opponent to reach a set of target states. Unlike traditional settings, we study distributed randomisation: team…
Dicey Games: Shared Sources of Randomness in Distributed Systems
Léonard Brice, Thomas A. Henzinger, K. S. Thejaswini
Consider a 4-player version of Matching Pennies where a team of three players competes against the Devil. Each player simultaneously says "Heads" or "Tails". The team wins if all f…
ε-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…
Privacy-Preserving Runtime Verification
Thomas A. Henzinger, Mahyar Karimi, K. S. Thejaswini
Runtime verification offers scalable solutions to improve the safety and reliability of systems. However, systems that require verification or monitoring by a third party to ensure…
Resolving Nondeterminism with Randomness
Thomas A. Henzinger, Keya Prakash, K. S. Thejaswini
In automata theory, while determinisation provides a standard route to solving many common problems in automata theory, some weak forms of nondeterminism can be dealt with in some…
Finding equilibria: simpler for pessimists, simplest for optimists
Léonard Brice, Thomas Henzinger, K. S. Thejaswini
We consider simple stochastic games with terminal-node rewards and multiple players, who have differing perceptions of risk. Specifically, we study risk-sensitive equilibria (RSEs)…
Rabin Games and Colourful Universal Trees
Rupak Majumdar, Irmak Saglam, K. S. Thejaswini
We provide an algorithm to solve Rabin and Streett games over graphs with vertices, edges, and colours that runs in time and $O…
Simple and tight complexity lower bounds for solving Rabin games
Antonio Casares, Marcin Pilipczuk, Michał Pilipczuk +2
We give a simple proof that assuming the Exponential Time Hypothesis (ETH), determining the winner of a Rabin game cannot be done in time , where $k…
Solving Two-Player Games under Progress Assumptions
Anne-Kathrin Schmuck, K. S. Thejaswini, Irmak Sağlam +1
This paper considers the problem of solving infinite two-player games over finite graphs under various classes of progress assumptions motivated by applications in cyber-physical s…
On History-Deterministic One-Counter Nets
Keya Prakash, K. S. Thejaswini
We consider the model of history-deterministic one-counter nets (OCNs). History-determinism is a property of transition systems that allows for a limited kind of non-determinism wh…
Adaptive Synchronisation of Pushdown Automata
A. R. Balasubramanian, K. S. Thejaswini
We introduce the notion of adaptive synchronisation for pushdown automata, in which there is an external observer who has no knowledge about the current state of the pushdown autom…
A symmetric attractor-decomposition lifting algorithm for parity games
Marcin Jurdziński, Rémi Morvan, Pierre Ohlmann +1
Progress-measure lifting algorithms for solving parity games have the best worst-case asymptotic runtime, but are limited by their asymmetric nature, and known from the work of Cze…
The Strahler number of a parity game
Laure Daviaud, Marcin Jurdziński, K. S. Thejaswini
The Strahler number of a rooted tree is the largest height of a perfect binary tree that is its minor. The Strahler number of a parity game is proposed to be defined as the smalles…
Universal Algorithms for Parity Games and Nested Fixpoints
Marcin Jurdziński, Rémi Morvan, K. S. Thejaswini
An attractor decomposition meta-algorithm for solving parity games is given that generalises the classic McNaughton-Zielonka algorithm and its recent quasi-polynomial variants due…