• Stochastic mean payoff game: smoothed analysis and approximation schemes 

      [OWP-2010-22] Boros, Endre; Elbassioni, Khaled; Fouz, Mahmoud; Gurvich, Vladimir; Manthey, Bodo (Mathematisches Forschungsinstitut Oberwolfach, 2010-03-20)
      We consider two-person zero-sum stochastic mean payoff games with perfect information modeled by a digraph with black, white, and random vertices. These BWR-games games are polynomially equivalent with the classical Gillette ...