Monotone Contractions

Batziou, Eleni ORCID: 0000-0003-0577-3419, Fearnley, John, Gordon, Spencer, Mehta, Ruta and Savani, Rahul ORCID: 0000-0003-1262-7831 (2025) Monotone Contractions In: Proceedings of the 57th Annual ACM Symposium on Theory of Computing.

Access the full-text of this item by clicking on the Open Access link.

Abstract

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 three-dimensional 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.

Item Type:	Conference Item (Unspecified)
Uncontrolled Keywords:	Contraction Maps, Fixed Point Computation, Shapley Games
Divisions:	Faculty of Science & Engineering Faculty of Science & Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User:	Symplectic Admin
Date Deposited:	17 Jun 2025 07:29
Last Modified:	22 May 2026 18:39
DOI:	10.1145/3717823.3718175
Open Access URL:	https://dl.acm.org/doi/pdf/10.1145/3717823.3718175
Related Websites:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3193268
Disclaimer:	The University of Liverpool is not responsible for content contained on other websites from links within repository metadata. Please contact us if you notice anything that appears incorrect or inappropriate.