Tarski’s Theorem, Supermodular Games, and the Complexity of Equilibria

Abstract. 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 [Formula: see text]-dimensional grid with sides of length [Formula: see text], 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 [Formula: see text], and we show that it requires at least [Formula: see text] function evaluations already on the 2-dimensional grid, even for randomized algorithms. We show that the general [Formula: see text] problem of finding some fixed point, when the monotone function is given succinctly (by a Boolean circuit), is in the class [Formula: see text] of problems solvable by local search and, rather surprisingly, also in the class [Formula: see text]. Finding the greatest or least fixed point guaranteed by Tarski’s theorem, however, requires [Formula: see text] steps and is [Formula: see text]-hard in the white-box model. For supermodular games, we show that finding an equilibrium 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 [Formula: see text] steps. We also show that computing (approximating) the value of Condon’s (Shapley’s) stochastic games reduces to the [Formula: see text] problem. An important open problem highlighted by this work is proving better upper or lower bounds on the (black-box query) complexity of the Tarski problem.