The Complexity of Computing a Fixed Point of a Monotone Function, and Some Applications

Kousha Etessami

The task of computing a fixed point of a monotone function arises in a variety of applications.

In this talk I shall describe some recent work in which we have studied the computational complexity of computing a (any) fixed point of a given monotone function that maps a finite $d$-dimensional grid lattice with sides of length $N=2^n$ to itself, where the monotone function is presented succinctly via a boolean circuit with $d \cdot n$ input gates and $d \cdot n$ output gates. The underlying ordering, $\leq$, of this lattice is the standard coordinate-wise partial order on $d$-dimensional vectors in $[N]^d$. By Tarski’s theorem, a function $f:[N]^d \rightarrow [N]^d$ always has a fixed points if it is monotone, or else it has a pair $x, y \in [N]^d$ that witness non-monotonicity, meaning where $x \leq y$ but $f(x) \not\leq f(y)$. We refer to the corresponding total search problem of either finding a fixed point or finding a witness pair for non-monotonicity, given such a succcinctly presented function $f:[N]^d \rightarrow [N]^d$, as the $\tt Tarski$ problem.

It turns out that $\tt Tarski$ subsumes a number of important computational problems. In particular, it is essentially computationally equivalent to the task of computing a pure Nash Equilibrium for (succinctly presented) supermodular games, or games with strategic complementarities, which are very widely studied classes of games in economics.

We also showed that computing the value of Condon’s turn-based simple stochastic (reachability) games, as well as the more general problem of computing, to within given desired accuracy $\epsilon > 0$, the value of Shapley’s original stochastic games, is reducible to $\tt Tarski$.

We showed that $\tt Tarski$ is contained in both the total search complexity classes $\mathsf{PLS}$ and $\mathsf{PPAD}$.

We also obtained some lower bounds in the black box oracle model for the 2-dimensional version of the Tarski problem.

Many questions remain open. I will discuss some of them.

(This talk describes joint work with C. Papadimitriou, A. Rubinstein, and M. Yannakakis, in a paper titled “Tarski’s theorem, supermodular games, and the complexity of equilibria”, that appeared in ITCS’2020.)

• Full paper

 Overview  Program