  We define the class of "simple recursive games". A simple recursive game isdefined as a simple stochastic game (a notion due to Anne Condon), except thatwe allow arbitrary real payoffs but disallow moves of chance. We study thecomplexity of solving simple recursive games and obtain an almost-linear timecomparison-based algorithm for computing an equilibrium of such a game. Theexistence of a linear time comparison-based algorithm remains an open problem.
We study the complexity of solving simple recursive games and obtain an almost-linear time comparison-based algorithm for computing an equilibrium of such a game.