English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

The use of monotonicity and Tarski's theorem in existence proofs ofequilibria is very widespread in economics, while Tarski's theorem is alsooften used for similar purposes in the context of verification. However, therehas been relatively little in the way of analysis of the complexity of findingthe fixed points and equilibria guaranteed by this result. We study acomputational formalism based on monotone functions on the $d$-dimensional gridwith sides of length $N$, and their fixed points, as well as the closelyconnected subject of supermodular games and their equilibria. It is known thatfinding 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 evaluationsalready on the 2-dimensional grid, even for randomized algorithms. We show thatthe general Tarski problem of finding some fixed point, when the monotonefunction is given succinctly (by a boolean circuit), is in the class PLS ofproblems solvable by local search and, rather surprisingly, also in the classPPAD. 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. Forsupermodular games, we show that finding an equilibrium in such games isessentially computationally equivalent to the Tarski problem, and finding themaximum or minimum equilibrium is similarly harder. Interestingly, two-playersupermodular games where the strategy space of one player is one-dimensionalcan be solved in $O(\log N)$ steps. We also observe that computing(approximating) the value of Condon's (Shapley's) stochastic games reduces tothe Tarski problem. An important open problem highlighted by this work isproving a $\Omega(\log^d N)$ lower bound for small fixed dimension $d \geq 3$.

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