Monotone Contractions

We study functions f : [0, 1] d → [0, 1] d that are both monotone and contracting, and we consider the problem of finding an ε-approximate fixed point of f . We show that the problem lies in the complexity class UEOPL. We give an algorithm that finds an ε-approximate fixed point of a threedimensional monotone contraction using O(log(1/ε)) queries to f . We also give a decomposition theorem that allows us to use this result to obtain an algorithm that finds an ε-approximate fixed point of a d-dimensional monotone contraction using O((c • log(1/ε)) ⌈d/3⌉ ) queries to f for some constant c. Moreover, each step of both of our algorithms takes time that is polynomial in the representation of f . These results are strictly better than the best-known results for functions that are only monotone, or only contracting. All of our results also apply to Shapley stochastic games, which are known to be reducible to the monotone contraction problem. Thus we put Shapley games in UEOPL, and we give a faster algorithm for approximating the value of a Shapley game. The current best-known algorithm for monotone functions was given by Chen et al. [3] . Internally, the algorithm of Fearnley et al. works by solving a relaxed problem for two-dimensional instances, and Chen et al. [3] call this problem Tarski*. They gave a decomposition theorem for Tarski*, and applying this to the original algorithm of Fearnley et al. gives an algorithm that solves the problem using O((c • log n) ⌈(d+1)/2⌉ ) queries, for some constant c. Recently, Chen at al. [4] showed that the query complexity of finding Tarski fixed points is the same as the query complexity of finding fixed points when the Tarski instance is promised to have a unique solution, and it is also promised that all sub-instances have unique solutions. Contracting functions. There has also been considerable interest in the problem of finding the fixed point of a contracting function. Our focus in this paper is on functions that are contracting with respect to the infinity norm, since it is this type of contraction that arises from Shapley and Simple stochastic games [9] . As mentioned previously, there are infinity norm contraction maps whose fixed point uses irrational numbers, so the focus has been on finding an ε-approximate fixed point of a contraction map The problem naturally lies in PPAD, because it is a special case of finding a Brouwer fixed point, and also PLS, because xf (x) ∞ gives a natural potential function for the problem. The problem therefore lies in CLS [7, 11] . Fearnley et al. [14] studied contractions defined by piecewise linear arithmetic circuits (PL-contraction), which capture the problem of simple stochastic games, but not Shapley games. They showed that finding an exact fixed point of a PL-contraction lies in the complexity class UEOPL, which is a subclass of CLS that contains problems that have unique solutions. It remains open whether the contraction problem itself lies in UEOPL. Shellman and Sikorski proved that the query complexity of finding an ε-fixed point of a contraction map in dimension two is log( 1 ε ) [23, 24] ; they left it as an open problem to extend their algorithm for 2 dimensions to more dimensions. In other work, they game a polynomial-time algorithm for general dimension d with query complexity log d ( 1 ε ) [22, 25] . In a striking recent result, Chen et al. [5] showed that the query complexity of finding an ε-fixed-point of a contraction map under the infinity norm is actually O(d 2 log( 1 ε )), so the query complexity of contraction is polynomial in d. However this result does come with a drawback: the time complexity of the algorithm is not polynomial, meaning that although the algorithm makes polynomially many queries, it may spend exponential time in between each of those queries. While our focus here is on the ℓ ∞ -norm, due to the importance of this setting for game theory, we note that finding fixed points of contractions or non-expansions under other norms has also received considerable attention. Sikorski provides a survey of results for both the ℓ ∞ and ℓ 2 (Euclidean) norms in [26] . In the Euclidean norm, it is known that a fixed point of a contraction or non-expansion can be found in polynomial time even in non-constant dimension using algorithms based on the ellipsoid method [2, 18] . Fearnley et al. [13] gave a polynomial-time algorithm for finding an approximate fixed point of any contraction in the ℓ p -norm with p < ∞ in any constant dimension. The problem of finding an approximate fixed point of a contracting function has also been studied in the case where the function is contracting not with respect to the metric induced by a fixed norm, but where a metric or meta-metric is itself input to the problem. In those cases the problem is known to be CLS-complete [8, 12] . Our contribution. While both monotone and contracting functions have received a considerable amount of attention recently, monotone contractions hav