We study the complexity of finding the values and optimal strategies of mean payoff games
on graphs, a family of perfect information games introduced by Ehrenfeucht and Mycielski …

We observe that the problem of deciding the winner in mean payoff games is in the
complexity class UP∩ co-UP. We also show a simple reduction from parify games to mean …

Ye [2011] showed recently that the simplex method with Dantzig's pivoting rule, as well as
Howard's policy iteration algorithm, solve discounted Markov decision processes (MDPs) …

We show that several decision problems originating from max-plus or tropical convexity are
equivalent to zero-sum two player game problems. In particular, we set up an equivalence …

In this paper, we study algorithmic problems for quantitative models that are motivated by the
applications in modeling embedded systems. We consider two-player games played on a …

Given a directed graph G=(V, A) with a non-negative weight (length) function on its arcs w:
A→ ℝ+ and two terminals s, t∈ V, our goal is to destroy all short directed paths from s to t in …

We study the complexity of computing stationary Nash equilibrium (NE) in n-player infinite-
horizon general-sum stochastic games. We focus on the problem of computing NE in such …

We suggest the first strongly subexponential and purely combinatorial algorithm for solving
the mean payoff games problem. It is based on iteratively improving the longest shortest …

We consider some well-known families of two-player zero-sum perfect-information stochastic
games played on finite directed graphs. The families include stochastic parity games …

We develop a tropical analogue of the simplex algorithm for linear programming. In
particular, we obtain a combinatorial algorithm to perform one tropical pivoting step …