Arrow Research search

Author name cluster

Marcin Jurdzinski

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

11 papers
2 author rows

Possible papers

11

SODA Conference 2019 Conference Paper

Universal trees grow inside separating automata: Quasi-polynomial lower bounds for parity games

  • Wojciech Czerwinski
  • Laure Daviaud
  • Nathanaël Fijalkow
  • Marcin Jurdzinski
  • Ranko Lazic 0001
  • Pawel Parys

Several distinct techniques have been proposed to design quasi-polynomial algorithms for solving parity games since the breakthrough result of Calude, Jain, Khoussainov, Li, and Stephan (2017): play summaries, progress measures and register games. We argue that all those techniques can be viewed as instances of the separation approach to solving parity games, a key technical component of which is constructing (explicitly or implicitly) an automaton that separates languages of words encoding plays that are (decisively) won by either of the two players. Our main technical result is a quasi-polynomial lower bound on the size of such separating automata that nearly matches the current best upper bounds. This forms a barrier that all existing approaches must overcome in the ongoing quest for a polynomial-time algorithm for solving parity games. The key and fundamental concept that we introduce and study is a universal ordered tree. The technical highlights are a quasi-polynomial lower bound on the size of universal ordered trees and a proof that every separating safety automaton has a universal tree hidden in its state space.

Details

IJCAI Conference 2015 Conference Paper

Approximate Nash Equilibria with Near Optimal Social Welfare

  • Artur Czumaj
  • Michail Fasoulakis
  • Marcin Jurdzinski

It is known that Nash equilibria and approximate Nash equilibria not necessarily optimize social optima of bimatrix games. In this paper, we show that for every fixed ε > 0, every bimatrix game (with values in [0, 1]) has an ε-approximate Nash equilibrium with the total payoff of the players at least a constant factor, (1 − √ 1 − ε)2, of the optimum. Furthermore, our result can be made algorithmic in the following sense: for every fixed 0 ≤ ε∗ < ε, if we can find an ε∗ -approximate Nash equilibrium in polynomial time, then we can find in polynomial time an ε-approximate Nash equilibrium with the total payoff of the players at least a constant factor of the optimum. Our analysis is especially tight in the case when ε ≥ 1 2. In this case, we show that for any bimatrix game there is an ε-approximate Nash equilibrium with constant size support whose social welfare is at least 2 √ ε − ε ≥ 0. 914 times the optimal social welfare. Furthermore, we demonstrate that our bound for the social welfare is tight, that is, for every ε ≥ 1 2 there is a bimatrix game for which every ε-approximate Nash equilibrium has social welfare at most 2 √ ε − ε times the optimal social welfare.

PDF Details

CSL Conference 2004 Conference Paper

On Nash Equilibria in Stochastic Games

  • Krishnendu Chatterjee
  • Rupak Majumdar
  • Marcin Jurdzinski

Abstract We study infinite stochastic games played by n -players on a finite graph with goals given by sets of infinite traces. The games are stochastic (each player simultaneously and independently chooses an action at each round, and the next state is determined by a probability distribution depending on the current state and the chosen actions), infinite (the game continues for an infinite number of rounds), nonzero sum (the players’ goals are not necessarily conflicting), and undiscounted. We show that if each player has a reachability objective, that is, if the goal for each player i is to visit some subset R i of the states, then there exists an ε -Nash equilibrium in memoryless strategies, for every ε >0. However, exact Nash equilibria need not exist. We study the complexity of finding such Nash equilibria, and show that the payoff of some ε -Nash equilibrium in memoryless strategies can be ε -approximated in NP. We study the important subclass of n -player turn-based probabilistic games, where at each state at most one player has a nontrivial choice of moves. For turn-based probabilistic games, we show the existence of ε -Nash equilibria in pure strategies for games where the objective of player i is a Borel set B i of infinite traces. However, exact Nash equilibria may not exist. For the special case of ω -regular objectives, we show exact Nash equilibria exist, and can be computed in NP when the ω -regular objectives are expressed as parity objectives.

Details

CSL Conference 2003 Conference Paper

Simple Stochastic Parity Games

  • Krishnendu Chatterjee
  • Marcin Jurdzinski
  • Thomas A. Henzinger

Abstract Many verification, planning, and control problems can be modeled as games played on state-transition graphs by one or two players whose conflicting goals are to form a path in the graph. The focus here is on simple stochastic parity games, that is, two-player games with turn-based probabilistic transitions and ω -regular objectives formalized as parity (Rabin chain) winning conditions. An efficient translation from simple stochastic parity games to nonstochastic parity games is given. As many algorithms are known for solving the latter, the translation yields efficient algorithms for computing the states of a simple stochastic parity game from which a player can win with probability 1. An important special case of simple stochastic parity games are the Markov decision processes with Büchi objectives. For this special case a first provably subquadratic algorithm is given for computing the states from which the single player has a strategy to achieve a Büchi objective with probability 1. For game graphs with m edges the algorithm works in time \(O(m \sqrt{m})\). Interestingly, a similar technique sheds light on the question of the computational complexity of solving simple Büchi games and yields the first provably subquadratic algorithm, with a running time of O ( n 2 / log n ) for game graphs with n vertices and O ( n ) edges.

Details

CSL Conference 2002 Conference Paper

Trading Probability for Fairness

  • Marcin Jurdzinski
  • Orna Kupferman
  • Thomas A. Henzinger

Abstract Behavioral properties of open systems can be formalized as objectives in two-player games. Turn-based games model asynchronous interaction between the players (the system and its environment) by interleaving their moves. Concurrent games model synchronous interaction: the players always move simultaneously. Infinitary winning criteria are considered: Büchi, co-Büchi, and more general parity conditions. A generalization of determinacy for parity games to concurrent parity games demands probabilistic (mixed) strategies: either player 1 has a mixed strategy to win with probability 1 (almost-sure winning), or player 2 has a mixed strategy to win with positive probability. This work provides efficient reductions of concurrent probabilistic Büchi and co-Büchi games to turn-based games with Büchi condition and parity winning condition with three priorities, respectively. From a theoretical point of view, the latter reduction shows that one can trade the probabilistic nature of almost-sure winning for a more general parity (fairness) condition. The reductions improve understanding of concurrent games and provide an alternative simple proof of determinacy of concurrent Büchi and co-Büchi games. From a practical point of view, the reductions turn solvers of turn-based games into solvers of concurrent probabilistic games. Thus improvements in the well-studied algorithms for the former carry over immediately to the latter. In particular, a recent improvement in the complexity of solving turn-based parity games yields an improvement in time complexity of solving concurrent probabilistic co-Büchi games from cubic to quadratic.

Details