A Quasipolynomial Algorithm for ContractionsResearch Paper
Many equilibrium and value computations reduce to finding the fixed point of a map that contracts the norm. Shapley's discounted stochastic games [Sha53], Condon's simple stochastic games [Con92], and, through the reductions of Andersson and Miltersen [AM09a], turn-based stochastic parity, mean-payoff and discounted-payoff games are all of this…