Monotone Contractions

We study functions f : [0, 1]^d -> [0, 1]^d that are both monotone and contracting in the L-infinity norm, and we consider the problem of finding an epsilon-approximate fixed point of the function.
Monotone contractions are motivated by applications to Shapley stochastic games and simple-stochastic games. Our main results are

• Finding an approximate fixed point of a monotone contraction lies in the complexity class UEOPL.
• There is a polynomial-time algorithm that finds an epsilon-fixed point of a three-dimensional monotone contraction using O(log (1/epsilon)) queries to the function.
• There is a decomposition theorem that allows us to obtain a polynomial-time algorithm that finds an epsilon-fixed point of a d-dimensional monotone contraction using O(log (1/epsilon)^{d/3}) queries to the function.

All of our results also apply to Shapley stochastic games. Thus we put Shapley games in UEOPL, and we give a faster algorithm for approximating the value of a Shapley game.

This is joint work with Eleni Batziou, Spencer Gordon, Ruta Mehta, and Rahul Savani