56 citations · 307 across the 14 of their papers we have counts for
7 papers · 1 filter
Perfect Half Space Games
Thomas Colcombet, Marcin Jurdziński, Ranko Lazić +1
We introduce perfect half space games, in which the goal of Player 2 is to make the sums of encountered multi-dimensional weights diverge in a direction which is consistent with a…
Mean-Payoff Games on Timed Automata
Shibashis Guha, Marcin Jurdzinski, Krishna S. +1
Mean-payoff games on timed automata are played on the infinite weighted graph of configurations of priced timed automata between two players, Player Min and Player Max, by moving a…
Distributed Methods for Computing Approximate Equilibria
Artur Czumaj, Argyrios Deligkas, Michail Fasoulakis +3
We present a new, distributed method to compute approximate Nash equilibria in bimatrix games. In contrast to previous approaches that analyze the two payoff matrices at the same t…
Fixed-Dimensional Energy Games are in Pseudo-Polynomial Time
Marcin Jurdziński, Ranko Lazić, Sylvain Schmitz
We generalise the hyperplane separation technique (Chatterjee and Velner, 2013) from multi-dimensional mean-payoff to energy games, and achieve an algorithm for solving the latter…
Approximate well-supported Nash equilibria in symmetric bimatrix games
Artur Czumaj, Michail Fasoulakis, Marcin Jurdziński
The -well-supported Nash equilibrium is a strong notion of approximation of a Nash equilibrium, where no player has an incentive greater than to deviate…
Average-Time Games on Timed Automata
Marcin Jurdzinski, Ashutosh Trivedi
An average-time game is played on the infinite graph of configurations of a finite timed automaton. The two players, Min and Max, construct an infinite run of the automaton by taki…
Linear Complementarity Algorithms for Infinite Games
John Fearnley, Marcin Jurdziński, Rahul Savani
The performance of two pivoting algorithms, due to Lemke and Cottle and Dantzig, is studied on linear complementarity problems (LCPs) that arise from infinite games, such as parity…