  The use of monotonicity and Tarski's theorem in existence proofs of
equilibria is very widespread in economics, while Tarski's theorem is also
often used for similar purposes in the context of verification. However, there
has been relatively little in the way of analysis of the complexity of finding
the fixed points and equilibria guaranteed by this result. We study a
computational formalism based on monotone functions on the $d$-dimensional grid
with sides of length $N$, and their fixed points, as well as the closely
connected subject of supermodular games and their equilibria. It is known that
finding some (any) fixed point of a monotone function can be done in time
$\log^d N$, and we show it requires at least $\log^2 N$ function evaluations
already on the 2-dimensional grid, even for randomized algorithms. We show that
the general Tarski problem of finding some fixed point, when the monotone
function is given succinctly (by a boolean circuit), is in the class PLS of
problems solvable by local search and, rather surprisingly, also in the class
PPAD. Finding the greatest or least fixed point guaranteed by Tarski's theorem,
however, requires $d\cdot N$ steps, and is NP-hard in the white box model. For
supermodular games, we show that finding an equilibrium in such games is
essentially computationally equivalent to the Tarski problem, and finding the
maximum or minimum equilibrium is similarly harder. Interestingly, two-player
supermodular games where the strategy space of one player is one-dimensional
can be solved in $O(\log N)$ steps. We also observe that computing
(approximating) the value of Condon's (Shapley's) stochastic games reduces to
the Tarski problem. An important open problem highlighted by this work is
proving a $\Omega(\log^d N)$ lower bound for small fixed dimension $d \geq 3$.
