IE Seminar

Date & Location:

February 21, 12:45-13:30, Ci H327

Speaker:

Bodo Manthey

Affiliation:

UT-EWI-DMMP

Abstract:

Stochastic mean payoff games are a powerful class of two-player zero-sum

games that generalize, e.g., cyclic games, simple stochastic games, parity games, and Markov decision processes. A stochastic mean payoff game consists of a directed graph with black, white, and red vertices: Black and white vertices belong to the two players, red vertices are random vertices. The edges are labeled with rewards. During the game a token is moved along the edges, and the black player pays the white player the corresponding reward. The goal of the players is to optimize their average payment.

The question whether equilibrium strategies and game values of stochastic mean payoff games can be computed efficiently is a long-standing open problem. It is only known that this problem lies in the intersection of NP and co-NP, and there are pseudo-polynomial algorithms for some subclasses.

To get some more insights into the complexity of solving these games, we consider two relaxed concepts: Approximate Nash equilibria and smoothed analysis. In the former, players are happy with a strategy if they cannot gain too much by deviating. In the latter, we rule out pathological instances by perturbing the rewards. We prove that the existence of pseudo-polynomial algorithms implies the existence of approximation schemes and polynomial smoothed complexity.

(Joint work with Endre Boros, Khaled Elbassioni, Mahmoud Fouz, Vladimir

Gurvich, and Kazuhisa Makino.)