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

Introduction

Equilibria are paramount in economics, because guaranteeing their existence in a particular strategic or market-like framework enables one to consider “What happens at equilibrium?” without further analysis. Equilibrium existence theorems are nontrivial to prove. The best known example is Nash’s theorem , whose proof in 1950, based on Brouwer’s fixed point theorem, transformed game theory, and inspired the Arrow-Debreu price equilibrium results , among many others. Decades later, complexity analysis of these theorems and corresponding solution concepts by computer scientists has created a fertile and powerful field of research .

Not all equilibrium theorems in economics, however, rely on Brouwer’s fixed point theorem for their proof (even though, in a specific sense made clear and proved in this paper, they could have…). Many of the exceptions ultimately rely on Tarski’s fixed point theorem , stating that all monotone functions on a complete lattice have a fixed point — and in fact a whole sublattice of fixed points with a largest and smallest element . In contrast to the equilibrium theorems whose proof relies on Brouwer’s fixed point theorem, there has been relatively little complexity analysis of Tarski’s fixed point theorem and the equilibrium results it enables. (We discuss prior related work at the end of this introduction.)

Here we present several results in this direction. Let $[N]=\{1,\ldots,N\}$. To formulate the basic problem, we consider a monotone function $f$ on the $d$-dimensional grid $[N]^{d}$, that is, a function $f:[N]^{d}\mapsto[N]^{d}$ such that for all $x,y\in[N]^{d}$, $x\geq y$ implies $f(x)\geq f(y)$; in the black-box oracle model, we can query this function with specific vectors $x\in[N]^{d}$; in the white-box model we assume that the function is presented by a boolean circuitNaturally, one could have addressed the more general problem in which the lattice is itself presented in a general way through two functions meet and join;however, this framework (a) leads quickly and easily to intractability; and (b) does not capture any more applications in economics than the one treated here.. Thus, $d$ and $N$ are the basic parameters to our model; it is useful to think of $d$ as the dimensionality of the problem, while $N$ is something akin to the inverse of the desired approximation $\epsilon$.

Tarski’s theorem in the grid framework is easy to prove. Let $\bar{1}=(1,\ldots,1)$ denote the ($d$-dimensional) all-1 vector. Consider the sequence of grid points $\bar{1},f(\bar{1}),f(f(\bar{1})),\ldots,f^{i}(\bar{1}),\ldots$. From monotonicity of $f$, by induction on $i$ we get, for all $i\geq 0$, $f^{i}(\bar{1})\leq f^{i+1}(\bar{1})$. Unless a fixed point is arrived at, the sum of the coordinates must increase at each iteration. Therefore, after at most $dN$ iterations of $f$ applied to $\bar{1}$, a fixed point is found. In other words $f^{dN}(\bar{1})=f^{dN+1}(\bar{1})$.

This immediately suggests an $O(dN)$ algorithm. But an $O(\log^{d}N)$ algorithm is also knownThis algorithm appears to have been first observed in .: Consider the $(d-1)$-dimensional function obtained by fixing the “input value” in the $d$’th coordinate of the function $f$ with some value $r_{d}$ (initialize $r_{d}:=\lceil N/2\rceil$). Find a fixed point $z^{*}\in[N]^{d-1}$ of this $(d-1)$-dimensional monotone function $f(z,r_{d})$ (recursively). If the $d$th coordinate $f_{d}(z^{*},r_{d})$ of $f(z^{*},r_{d})$, is equal to $r_{d}$, then $(z^{*},r_{d})$ is a fixed point of the overall function $f$, and we are done. Otherwise, a binary search on the $d$’th coordinate is enabled: we need to look for a larger (smaller) value of $r_{d}$ if $f_{d}(z^{*},r_{d})>r_{d}$ (respectively, if $f_{d}(z^{*},r_{d})<r_{d}$). By an easy induction, this establishes the $O(\log^{d}N)$ upper bound ().

We conjecture that this algorithm is essentially optimal in the black box sense, for small fixed constant dimension $d$. In Theorem 4.1 we prove this result for the $d=2$ case. We provide a class of monotone functions that we call the herringbones: two monotonic paths, one starting from $\bar{1}$ and the other from $\bar{N}$, meeting at the fixed point, while all other points in the $N\times N$ grid are mapped diagonally: $f(x)=x+(-1,+1)$ or $x+(+1,-1)$, whichever of the points is closer to the monotonic path that contains the fixed point. We prove that any randomized algorithm needs to make $\Omega(\log^{2}N)$ queries (with high probability) to find the fixed point.

Can this lower bound result be generalized to fixed $d\geq 3$? This is a key question left open by this paper. There are several obstacles to a proof establishing, e.g., a $\Omega(\log^{3}N)$ lower bound in the 3-dimensional case ($d=3$), and some possible ways for overcoming them. First, it is not easy to identify a suitable “herringbone-like” function in three or more dimensions — a monotone family of functions built around a path from $\bar{1}$ to $\bar{N}$. It nevertheless seems plausible that $\log^{d}N$ should still be (close to) a lower bound on any such algorithm (assuming of course that $N$ is sufficiently larger than $d$, so that the $dN$ algorithm does not violate the lower bound). We prove one encouraging result in this context: We give an alternative proof of the $d=2$ lower bound, in which we establish that any deterministic black-box algorithm for Tarski in two dimensions must solve a sequence of $\Omega(\log N)$ one-dimensional problems (Theorem 4.7), a result pointing to a possible induction on $d$ (recall that this is precisely the form of the $\log^{d}N$ algorithm).

Tarski’s theorem further asserts that there is a greatest and a least fixed point, and these fixed points are especially useful in the economic applications of the result (see for example ). It is not hard to see, however, that finding these fixed points is NP-hard, and takes $\Omega(dN)$ time in the black box model (see Proposition 2.1).

In terms of complexity classes, the problem Tarski is obviously in the class TFNP of total function (total search) problems. But where exactly? We show (Theorem 3.2) that it belongs in the class $\mathsf{PLS}$ of local optimum search problems.

Surprisingly, Tarski is also in the class $P^{\mathsf{PPAD}}$ of problems reducible to a Brouwer fixed point problem (Theorem 3.3), and thus, by the known fact that the class $\mathsf{PPAD}$ is closed under polynomial time Turing reductions () it is in $\mathsf{PPAD}$ (Corollary 3.4). This result presents a heretofore unsuspected connection between two main sources of equilibrium results in economics.

Supermodular games — or games with strategic complementarities — comprise a large and important class of economic models, with complete lattices as strategy spaces, in which a player’s best response is a monotone function (or monotone correspondence) of the other player’s strategies. They always have pure Nash equilibria due to Tarski’s theorem. We show that finding an equilibrium for a supermodular game with (discrete) Euclidean grid strategy spaces is essentially computationally equivalent to the problem of finding a Tarski fixed point of a monotone map (Proposition 5.2 and Theorem 5.4). If there are two players and one of them has a one-dimensional strategy space, we show that a Nash equilibrium can be found in logarithmic time (in the size of the strategy spaces).

Stochastic games . We show that the problems of computing the (irrational) value of Shapley’s discounted stochastic games to desired accuracy, and computing the exact value of Condon’s simple stochastic games (SSG), are both P-time reducible to the Tarski problem. The proofs employ known characterizations of the value of both Shapley’s stochastic games and Condon’s SSGs in terms of monotone fixed point equations, which can also be viewed as monotone “polynomially contracting” maps with a unique fixed point, and from properties of polynomially contracting maps, see .

Prior related work: in recent years a number of technical reports and papers by Dang, Qi, and Ye, have considered the complexity of computational problems related to Tarski’s theorem . In particular, in the authors provided the already-mentioned $\log^{d}N$ algorithm for computing a Tarski fixed point for a discrete map, $f:[N]^{d}\rightarrow[N]^{d}$, which is monotone under the coordinate-wise order. In they also establish that determining the uniqueness of the fixed point of a monotone map under coordinate-wise order is coNP-hard, and that uniqueness under lexicographic order is also coNP-hard (already in one dimension). In the authors studied another variant of the Tarski problem, namely computing another fixed point of a monotone function in an expanded domain where the smallest point is a fixed point; this variant is NP-hard (the claim in the paper that this problem is in $\mathsf{PPA}{}$ has been withdrawn by the authors ). In earlier work, Echenique , studied algorithms for computing all pure Nash equilibria in supermodular games (and games with strategic complementaries) whose strategy spaces are discrete grids. Of course computing all pure equilibria is harder than computing some pure equilibrium; indeed, we show that computing the least (or greatest) pure equilibrium of such a supermodular game is already NP-hard (Corollary 5.5). In earlier work Chang, Lyuu, and Ti considered the complexity of Tarski’s fixed point theorem over a general finite lattice given via an oracle for its partial order (not given it explicitly) and given an oracle for the monotone function, and they observed that the total number of oracle queries required to find some fixed point in this model is linear in the number of elements of the lattice. They did not study monotone functions on euclidean grid lattices, and their results have no bearing on this setting.

Basics

A partial order $(L,\leq)$ is a complete lattice if every nonempty subset $S$ of $L$ has a least upper bound (or supremum or join, denoted $\sup S$ or $\lor S$) and a greatest lower bound (or infimum or meet, denoted $\inf S$ or $\land S$) in $L$. A function $f:L\rightarrow L$ is monotone if for all pairs of elements $x,y\in L$, $x\leq y$ implies $f(x)\leq f(y)$. A point $x\in L$ is a fixed point of $f$ if $f(x)=x$. Tarski’s theorem () states that the set $Fix(f)$ of fixed points of $f$ is a nonempty complete lattice under the same partial order $\leq$; in particular, $f$ has a greatest fixed point (GFP) and a least fixed point (LFP).

In this paper we will take as our underlying lattice $L$ a finite discrete Euclidean grid, which we fix for simplicity to be the integer grid $[N]^{d}$, for some positive integers $N,d$, where $[N]=\{1,\ldots,N\}$. Comparison of points is componentwise, i.e. $x\leq y$ if $x_{i}\leq y_{i}$ for all $i=1,\ldots,d$. We will also consider the corresponding continuous box, $[1,N]^{d}$ that includes all real points in the box. Both, the discrete and continuous box are clearly complete lattices.

Given a monotone function $f$ on the integer grid $[N]^{d}$, the problem is to compute a fixed point of $f$ (any point in $Fix(f)$). A generally harder problem is to compute specifically the LFP of $f$ or the GFP of $f$. We consider mostly the oracle model, in which the function $f$ is given by a black-box oracle, and the complexity of the algorithm is measured in terms of the number of queries to the oracle. Alternatively, we can consider also an explicit model in which $f$ is given explicitly by a polynomial-time algorithm (a polynomial-size Boolean circuit), and then the complexity of the algorithm is measured in the ordinary Turing model. Note that the number of bits needed to represent a point in the domain is $d\log N$, so polynomial time here means polynomial in $d$ and $n=\log N$. The number $N^{d}$ of points in the domain is exponential.

Tarski’s value iteration algorithm provides a simple way to compute the LFP of $f$: Starting from the lowest point of the lattice, which here is the all-1 vector $1$, apply repeatedly $f$. This generates a monotonically increasing sequence of points $1\leq f(1)\leq f^{2}(1)\leq\ldots$ until a fixed point is reached, which is the LFP of $f$. In every step of the sequence, at least one coordinate is strictly increased, therefore a fixed point is reached in at most $(N-1)d$ steps. In the worst case, the process may take that long, which is exponential in the bit size $d\log N$. Similarly, the GFP can be computed by applying repeatedly $f$ starting from the highest point of the lattice, i.e., from the all-$N$ point, until a fixed point is reached.

Another way to compute some fixed point of a monotone function $f$ (not necessarily the LFP or the GFP) is by a divide-and-conquer algorithm. In one dimension, we can use binary search: If the domain is the set $L(l,h)=\{x\in Z|l\leq x\leq h\}$ of integers between the lowest point $l$ and the highest point $h$, then compute the value of $f$ on the midpoint $m=(l+h)/2$. If $f(m)=m$ then $m$ is a fixed point; if $f(m)<m$ then recurse on the lower half $L(l,m)$, and if $f(m)>m$ then recurse on the upper half $L(m,h)$. The monotonicity of $f$ implies that $f$ maps the respective half interval into itself. Hence the algorithm correctly finds a fixed point in at most $\log N$ iterations, where $N$ is the number of points.

In the general $d$-dimensional case, suppose that the domain is the set of integer points in the box defined by the lowest point $l$ and the highest point $h$, i.e. $L(l,h)=\{x\in Z^{d}|l\leq x\leq h\}$. Consider the set of points with $d$-th coordinate equal to $m=(l+h)/2$; their first $d-1$ coordinates induce a $(d-1)$-dimensional lattice $L^{\prime}(l,h)=\{x\in Z^{d-1}|l_{i}\leq x_{i}\leq h_{i},i=1,\ldots d-1\}$. Define the function $g$ on $L^{\prime}(l,h)$ by letting $g(x)$ consist of the first $d-1$ components of $f(x,m)$. It is easy to see that $g$ is a monotone function on $L^{\prime}(l,h)$. Recursively, compute a fixed point $x^{*}$ of $g$. If $f_{d}(x^{*},m)=m$, then $(x^{*},m)$ is a fixed point of $f$ (this holds in particular if $l=h$). If $f_{d}(x^{*},m)>m$, then recurse on $L(f(x^{*},m),h)$. If $f_{d}(x^{*},m)<m$, then recurse on $L(l,f(x^{*},m))$. In either case, monotonicity implies that if the algorithm recurses, then $f$ maps the smaller box into itself and thus has a fixed point in it. An easy induction shows that the complexity of this algorithm is $O((\log N)^{d})$, ().

Computing the least or the greatest fixed point is in general hard, even in one dimension, both in the oracle and in the explicit model.

Computing the LFP or the GFP of an explicitly given polynomial-time monotone function in one dimension is NP-hard. In the oracle model, the problem requires $\Omega(N)$ queries for a domain of size $N$.

We prove the claim for the LFP; the GFP is similar. Reduction from Satisfiability. Given a Boolean formula $\phi$ in $n$ variables, let the domain $D=\{0,1,\ldots,2^{n}\}$, and define the function $f$ as follows. For $x\leq 2^{n}-1$, viewing $x$ as an $n$-bit binary number, it corresponds to an assignment to the $n$ variables of $\phi$; let $f(x)=x$ if the assignment $x$ satisfies $\phi$, and let $f(x)=x+1$ otherwise. Define $f(2^{n})=2^{n}$. Clearly $f$ is a monotone function and it can be computed in polynomial time. If $\phi$ is not satisfiable then the LFP of $f$ is $2^{n}$, while if $\phi$ is satisfiable then the LFP is not $2^{n}$.

For the oracle model, use the same domain $D$ and let $f$ map every $x\leq 2^{n}-1$ to $x$ or $x+1$, and $f(2^{n})=2^{n}$. The LFP is not $2^{n}$ iff there exists an $x\leq 2^{n}-1$ such that $f(x)=x$, which in the oracle model requires trying all possible $x\leq 2^{n}-1$. ∎

In the case of a continuous domain $[1,N]^{d}$, we may not be able to compute an exact fixed point, and thus we have to be content with approximation. Given an $\epsilon>0$, an $\epsilon$-approximate fixed point is a point $x$ such that $|f(x)-x|\leq\epsilon$, where we use the $L_{\infty}$ (max) norm, i.e. $|f(x)-x|=\max\{|f_{i}(x)-x_{i}||i=1,\ldots,d\}$. In this context, polynomial time means polynomial in $\log N,d,$ and $\log(1/\epsilon)$ (the number of bits of the approximation). An $\epsilon$-approximate fixed point need not be close to any actual fixed point of $f$. A problem that is generally harder is to compute a point that approximates some actual fixed point, and an even harder task is to approximate specifically the LFP or the GFP of $f$. Tarski’s value iteration algorithm, starting from the lowest point converges in the limit to the LFP (and if started from the highest point, it converges to the GFP), but there is no general bound on the number of iterations needed to get within $\epsilon$ of the LFP (or the GFP). The algorithm reaches however an $\epsilon$-approximate fixed point within $Nd/\epsilon$ iterations (note, this is exponential in $\log N,\log(1/\epsilon)$).

It is easy to see that the approximate fixed point problem for the continuous case reduces to the exact fixed point problem for the discrete case.

The problem of computing an $\epsilon$-approximate fixed point of a given monotone function on the continuous domain $[1,N]^{d}$ reduces to the exact fixed point problem on a discrete domain $[N/\epsilon]^{d}$.

Given the monotone function $f$ on the continuous domain $D_{1}=[1,N]^{d}$, consider the discrete domain $D_{2}=\{x\in Z^{d}|k\leq x_{i}\leq Nk,i=1,\ldots,d\}$, where $k=\lceil 1/\epsilon\rceil$, and define the function $g$ on $D_{2}$ as follows. For every $x\in D_{2}$, let $g(x)$ be obtained from $kf(x/k)$ by rounding each coordinate to the nearest integer, with ties broken (arbitrarily) in favor of the ceiling. Since $f$ is monotone, $g$ is also monotone. If $x^{*}$ is a fixed point of $g$, then $kf(x^{*}/k)$ is within 1/2 of $x^{*}$ in every coordinate, and hence $f(x^{*}/k)$ is within $1/2k<\epsilon$ of $x^{*}/k$. Thus $x^{*}/k$ is an $\epsilon$-approximate fixed point of $f$. ∎

Computing a Tarski fixed point is in 𝖯𝖫𝖲𝖯𝖫𝖲\mathsf{PLS} ∩\cap 𝖯𝖯𝖠𝖣𝖯𝖯𝖠𝖣\mathsf{PPAD}{}

Recall that a general discrete total search problem (with polynomially bounded outputs), $\Pi$, has a set of valid input instances $D_{\Pi}\subseteq\{0,1\}^{*}$, and associates with each valid input instance $I\in D_{\Pi}$, a non-empty set ${\mathcal{O}}_{I}\subseteq\{0,1\}^{p_{\Pi}(|I|)}$ of acceptable outputs, where $p_{\Pi}(\cdot)$ is some polynomial. (So the bit encoding length of every acceptable output is polynomially bounded in the bit encoding length of the input $I$.)

We are interested in the complexity of the following total search problem:

Input: A function $f:[N]^{d}\rightarrow[N]^{d}$ with $N=2^{n}$ for some $n\geq 1$, given by a boolean circuit, $C_{f}$, with $(d\cdot n)$ input gates and $(d\cdot n)$ output gates.

Note $\mathtt{Tarski}$ is a total search problem: If $f$ is monotone, it will contain a fixed point in $[N]^{d}$, and otherwise it will contain such a witness pair of vectors that exhibit non-monotonicity. (If it is non-monotone it may of course have both witnesses for non-monotonicity and fixed points.)

Recall that a total search problem, $\Pi$, is in the complexity class $\mathsf{PLS}$ (Polynomial Local Search) if it satisfies all of the following conditions (see ):

A solution $s\in S_{I}$ is called a local optimum (local maximum) if for all $s^{\prime}\in{\mathcal{N}}_{I}(s)$, $g_{I}(s)\geq g_{I}(s^{\prime})$. We let ${\mathcal{O}}_{I}$ denote the set of all local optima for instance $I$. (Clearly ${\mathcal{O}}_{I}$ is non-empty, because $S_{I}$ is non-empty.)

There is a polynomial time algorithm, $A_{\Pi}$, that given a string $I\in\{0,1\}^{*}$, decides whether $I$ is a valid input instance $I\in D_{\Pi}$, and if so outputs some solution $s_{0}\in S_{I}$.

There is a polynomial time algorithm, $B_{\Pi}$, that given valid instance $I\in D_{\Pi}$ and a string $s\in\{0,1\}^{p(|I|)}$, decides whether $s\in S_{I}$, and if so, outputs the payoff $g_{I}(s)$.

There is a polynomial time algorithm, $H_{\Pi}$, that given valid instance $I\in D_{\Pi}$ and $s\in S_{I}$, decides whether $s$ is a local optimum, i.e., whether $s\in{\mathcal{O}}_{I}$, and otherwise computes a strictly improving neighbor $s^{\prime}\in{\mathcal{N}}_{I}(s)$, such that $g_{I}(s^{\prime})>g_{I}(s)$.

Each valid input instance $I_{f}\in D_{\mathtt{Tarski}}\subseteq\{0,1\}^{*}$ of $\mathtt{Tarski}$ is an encoding of a function $f:[N]^{d}\rightarrow[N]^{d}$ via a boolean circuit $C_{f}$. We can view the problem $\mathtt{Tarski}{}$ as a polynomial local search problem, as follows:

There is a polynomial time algorithm $A_{\mathtt{Tarski}}$ that, given a string $I_{f}\in\{0,1\}^{*}$ first determines whether this is a valid input instance, by checking that it suitably encodes a boolean circuit (straight-line program) $C_{f}$ with $(d\log N)$ input gates and the same number of output gates, and thereby defines a function $f:[N]^{d}\rightarrow[N]^{d}$. If the input is a valid instance, then $A_{\mathtt{Tarski}}$ outputs a solution $s_{0}\in S_{I_{f}}$, by just letting $s_{0}:={\mathbf{1}}\in[N]^{d}$ be the all 1 vector. Clearly, ${\mathbf{1}}\leq f({\mathbf{1}})$, so indeed ${\mathbf{1}}\in S^{\prime}_{I_{f}}\subseteq S_{I_{f}}$.

There is a polynomial time algorithm $B_{\mathtt{Tarski}}$ that, given a valid instance $I_{f}$ and given a string $s\in\{0,1\}^{*}$, first decides whether $s\in S_{I_{f}}$. It does so as follows: if $s$ is (a binary encoding of) $x\in[N]^{d}$, then $B_{\mathtt{Tarski}}$ computes $f(x)$ using the given boolean circuit $C_{f}$ (encoded in instance $I_{f}$), and checking whether $x\leq f(x)$. If instead $s=(x,y)\in[N]^{d}\times[N]^{d}$, then it checks whether $(x,y)$ is a witness of non-monotonicity, by computing $f(x)$ and $f(y)$ using $C_{f}$, and checking that both $x\leq y$ and $f(x)\not\leq f(y)$ hold.

If $s\in S_{I_{f}}$, the algorithm can also easily output the value of the objective $g_{I_{f}}(s)$. Namely, if $s=x\in S^{\prime}_{I_{f}}$, then $g_{I_{f}}(s):=\sum_{i=1}^{d}x_{i}$, and if $s=(x,y)\in S^{\prime\prime}_{I_{f}}$ then $g_{I_{f}}(s):=dN+1$.

We have thus shown that $\mathtt{Tarski}{}$ satisfies all the conditions of being in $\mathsf{PLS}{}$. ∎

𝚃𝚊𝚛𝚜𝚔𝚒∈𝖯𝖯𝖠𝖣𝚃𝚊𝚛𝚜𝚔𝚒𝖯𝖯𝖠𝖣\mathtt{Tarski}{}\in\mathsf{PPAD}

Once we have established that $\mathtt{Tarski}\in P^{\mathsf{PPAD}}$, the fact that $\mathtt{Tarski}\in\mathsf{PPAD}$ will follow as a simple corollary, using a prior result of Buss and Johnson , who showed that $\mathsf{PPAD}$ is closed under polynomial-time Turing reductions.

There are a number of equivalent ways to define the total search complexity class $\mathsf{PPAD}$. Rather than give the original definition (), we will use an equivalent characterization of $\mathsf{PPAD}$ (a.k.a., $\mathsf{linear}$-$\mathsf{FIXP}$) from (see section 5 of ). Informally, according to this characterization, a discrete total search problem, $\Pi$, is in $\mathsf{PPAD}$ if and only if it can be reduced in P-time to computing a Brouwer fixed point of an associated “polynomial piecewise-linear” continuous function that maps a non-empty convex polytope to itself. More formally, $\Pi$ is in $\mathsf{PPAD}$ if it satisfies all of the following conditions:

There is a polynomial time oracle algorithm, $R^{2}_{\Pi}$, that “computes” the piecewise-linear function $F_{I}$ in the following sense.

Note that in this sense $R^{2}_{\Pi}$ does indeed define the piecewise-linear function $F_{I}:W(I)\rightarrow W(I)$. Specifically, for $x\in W(I)$, the sequence of (polynomially many) oracle queries made by $R^{2}_{\Pi}(I,O_{x})$ defines a system of linear inequalities (with rational, polynomially bounded, coefficients) satisfied by $x$ which define a “piece” or “cell” such that $x\in{\mathcal{C}}_{x}\subseteq W(I)$, and such that $F_{I}$ is linear on ${\mathcal{C}}_{x}$; specifically such that for any $y\in{\mathcal{C}}_{x}$, $F_{I}(y)=Cy+C^{\prime}$.

Suppose we are given an instance $I_{f}\in D_{\mathtt{Tarski}}$ of $\mathtt{Tarski}$, corresponding to a function $f:[N]^{d}\rightarrow[N]^{d}$ (given by a boolean circuit $C_{f}$).

Nevertheless, we will show that finding any such fixed point of $f^{\prime}$ allows us to make progress (via a divide and conquer binary search), towards either finding a discrete fixed point of $f$ (if it is monotone), or finding witnesses for a violation of monotonicity of $f$.

We now define $f^{\prime}$ in detail. Consider the following simplicial decompositionKnown as Freudenthal’s simplicial division . of $B(a,b)$. For each $i\in[d]$, let $e^{i}\in\{0,1\}^{d}$ denote the standard unit vector with ’s in every coordinate except a $1$ in the $i$’th coordinate. For each integer vector $y\in L(a,b-{\mathbf{1}})$, and for every permutation $\pi=(\pi_{1},\ldots,\pi_{d})$ of $[d]$, define the subsimplex $S^{y,\pi}$ as the convex hull of the following $d+1$ (affinely independent) vertices $y^{0},\ldots,y^{d+1}\in L(a,b)$, given by $y^{0}=y$, and for $i\in\{1,\ldots,d\}$, $y^{i}=y^{i-1}+e^{\pi_{i}}$.

The union of all $d!$ simplices \{S^{y,\pi}\mid\pi\ \mbox{is a permutation of[d]}\} constitutes a simplicial subdivision of the d-cube $B(y,y+{\mathbf{1}})$, and the union of all such simplices, for all $y\in L(a,b-{\mathbf{1}})$ constitutes a simplicial subdivision of $B(a,b)$. Note the following important property of this simplicial subdivision, which we exploit: the vertices $y^{0},y^{1},\ldots,y^{d}$ of each subsimplex $S^{y,\pi}$ are totally ordered with respect to coordinate-wise order: $y^{0}\leq y^{1}\leq y^{2}\leq\ldots\leq y^{d}$.

Given this simplicial subdivision of $B(a,b)$, we define $f^{\prime}:B(a,b)\rightarrow B(a,b)$ so that it linearly interpolates $f$ inside each subsimplex $S^{y,\pi}$. Specifically, for any point $x\in S^{y,\pi}$, there is a unique vector $\lambda=(\lambda_{0},\lambda_{1},\ldots,\lambda_{d})\in^{d+1}$, such that $\sum_{j=0}^{d}\lambda_{j}=1$, and such that $x=\sum_{j=0}^{d}\lambda_{j}y^{j}$. We define $f^{\prime}(x):=\sum_{j=0}^{d}\lambda_{j}f(y^{j})$. Note that $f^{\prime}$ agrees with $f$ on integer points in $L(a,b)$. Also if $x$ belongs to several $x\in S^{y,\pi}$ (i.e. lies on some common faces of the subsimplices), then only the common vertices will have nonzero coefficients in any subsimplex, thus they all yield the same value for $f^{\prime}(x)$.

Suppose, on the other hand, that the computed fixed point $x^{*}$ of $f^{\prime}$ is non-integer in some coordinate. It is still useful. Consider the cell $C\subseteq S^{y,\pi}$, defined as the convex hull of the unique subset $Y^{\prime}=\{y^{j_{1}},y^{j_{2}},\ldots,y^{j_{k}}\}$ of the vertices $Y=\{y^{0},\ldots,y^{d}\}$ of $S^{y,\pi}$, such that $C$ contains $x^{*}$ in its strict interior. In other words, $x^{*}=\sum_{r=1}^{k}\lambda_{j_{r}}y^{j_{r}}$, such that $0<\lambda_{j_{r}}<1$ for all $r\in\{1,\ldots,k\}$. Let $u=y^{j_{t}}$ be the maximum vertex of $C$, and let $v=y^{j_{q}}$ be the minimum vertex of $C$ (the vertices of $C$ are ordered since they are a subset of the vertices of $S^{y,\pi}$).

Suppose that $f$ is monotone and $f(u)_{i}<u_{i}$ for some coordinate $i$. Then $f(u)_{i}\leq u_{i}-1$ because $f(u)_{i}$ is an integer. Furthermore, for all vertices $y^{j_{r}}$ of $C$, since $y^{j_{r}}\leq u=y^{j_{t}}$, we must also have $f_{i}(y^{j_{r}})\leq f_{i}(u)\leq u_{i}-1\leq y^{j_{r}}_{i}$ (where the last inequality holds because two vertices of $C$ differ in any given coordinate by at most 1). But we have $\sum_{r=1}^{k}\lambda_{j_{r}}y^{j_{r}}_{i}=x^{*}_{i}=f^{\prime}(x^{*})_{i}=\sum_{r=1}^{k}\lambda_{j_{r}}f(y^{j_{r}})_{i}$, which is impossible, since $y^{j_{r}}_{i}\geq f(y^{j_{r}})_{i}$ for every $r$, and $y^{j_{t}}_{i}>f(y^{j_{t}})_{i}$, and $\lambda_{j_{t}}>0$. Thus, since $x^{*}$ is a fixed point of $f^{\prime}$, it can not be the case that $f$ is monotone and $f(u)_{i}<u_{i}$ for some coordinate $i$. Therefore, if $f$ is monotone, then $f(u)\geq u$ (in all coordinates). For a completely analogous reason, if $f$ is monotone, we also have $f(v)\leq v$.

Suppose, on the other hand we either find that $f(u)\not\geq u$, or that $f(v)\not\leq v$. Then necessarily, it must be the case that there are a pair of vertices $y^{j_{b}},y^{j_{e}}$ of the cell $C$ containing $x^{*}$ in its interior, such that $y^{j_{b}}\leq y^{j_{e}}$ but $f(y^{j_{b}})\not\leq f(y^{j_{e}})$. So, in this case, we examine all such pairs to find such a pair, we halt and output $(y^{j_{b}},y^{j_{e}})$ as a witness pair for the non-monotonicity of $f$.

Assume on the other hand that $f(u)\geq u$ and $f(v)\leq v$. Note that in that case, if $f$ is monotone, then it maps the sublattice $L(u,b)$ to itself, and it also maps the disjoint sublattice $L(a,v)$ to itself. Thus, if $f$ is monotone, $f$ must have an integer fixed point in both $L(a,v)$ and $L(u,b)$.

So, we can choose the smaller of these two sublattices, consider the function $f$ restricted to that sublattice, and continue recursively to find a fixed point in that sublattice (if $f$ is monotone) or a violation of monotonicity. If $f$ is not monotone, it is possible that it maps some points in the sublattice $L(a,v)$ (or $L(u,b)$) to points outside. Therefore, in the recursive call for the sublattice, when we define the piecewise-linear function $f^{\prime}$ on the corresponding box $B(a,v)$ (or $B(u,b)$) we take the maximum with $a$ and minimum with $v$ (or $u$ and $b$ respectively), i.e., threshold it, so that it maps the box to itself, and hence it is a Brouwer function. When the $\mathsf{PPAD}{}$ oracle gives us back a fixed point $x^{*}$ for this (possibly thresholded) function $f^{\prime}$, we find the vertices $y^{j_{r}}$ of the cell $C$ that contains $x^{*}$ in its strict interior (i.e. the ones that have nonzero coefficients in the convex combination) and test if $f$ maps all of them within the current box. If this is not the case then we get a violation of monotonicity: Suppose wlog that the current box is $B(a,v)$ (similarly if it is $B(u,b)$). If $f(y^{j_{r}})\not\geq a$ then $(a,y^{j_{r}})$ is a violating pair because $f(a)\geq a$; if $f(y^{j_{r}})\not\leq v$ then $(y^{j_{r}},v)$ is a violating pair because $f(v)\leq v$. Thus, if $f(y^{j_{r}})$ lies outside the current box, then we return the discovered violating pair and terminate. Otherwise, the thresholding did not affect the $f(y^{j_{r}})$ and $f^{\prime}(x^{*})$ and we proceed as explained above.

Every iteration decreases the total number of points in our current lattice by a factor of $2$, from the number of points in the original lattice $L(a,b)$. So after a polynomial number of iterations in $(d+\log N)$, we either find a fixed point of $f$, or we find a witness pair of integer vectors that witness the non-monotonicity of $f$. ∎

This follows immediately from Theorem 3.3, combined with a result due to Buss and Johnson (, Theorem 6.1), who showed that $\mathsf{PPAD}$ is closed under polynomial-time Turing reductions. ∎

The 2-dimensional lower bound

Consider a monotone function defined on the $N\times N$ grid $f:[N]^{2}\mapsto[N]^{2}$. Let $A$ be any (randomized) black-box algorithm for finding a fixed point of the function by computing a sequence of queries of the form $f(x,y)=?$; $A$ can of course be adaptive in that any query can depend in arbitrarily complex ways on the answers to the previous queries. For example, the divide-and-conquer algorithm described in the introduction is a black box algorithm. The following result suggests that this algorithm is optimal for two dimensions.

Given black-box access to a monotone function $f:\left[N\right]^{2}\rightarrow\left[N\right]^{2}$, finding a fixed point of $f$ requires $\Omega(\log^{2}N)$ queries (with high probability).

Below, we construct a hard distribution of such functions.

Given a monotone path from $\left(1,1\right)$ to $\left(N,N\right)$ on the $N\times N$ grid graph and a point $\left(i^{*},j^{*}\right)$ on the path, we construct $f$ as follows:

We let $\left(i^{*},j^{*}\right)$ be the unique fixed point of $f$, i.e. $f\left(i^{*},j^{*}\right)\triangleq\left(i^{*},j^{*}\right)$.

At all other points on the path, $f$ is directed towards the fixed point. For a point $\left(x,y\right)$ on the path that is dominated by $\left(i^{*},j^{*}\right)$, we let $f(x,y)$ be the next point on the path, i.e. $f(x,y)=\left(x+1,y\right)$ or $f(x,y)=\left(x,y+1\right)$. Similarly, for a point $(x,y)$ that is on the path and dominates $\left(i^{*},j^{*}\right)$, we let $f(x,y)$ be the previous point on the path.

For all points outside the path, $f$ is directed towards the path. Observe that the path partitions $\left[N\right]^{2}$ into three (possibly empty) subsets: below the path, the path, and above the path. For a point $\left(x,y\right)$ below the path, we set $f\left(x,y\right)\triangleq\left(x-1,y+1\right)$. Similarly, for a point $\left(x,y\right)$ above the path, $f\left(x,y\right)\triangleq\left(x+1,y-1\right)$.

An example of such a function $f:^{2}\rightarrow^{2}$ is given in Figure 1.

For any choice of path and point $\left(i^{*},j^{*}\right)$ on the path, $f$ constructed as above is monotone.

In our hard distribution, once we fix a path, we choose $\left(i^{*},j^{*}\right)$ uniformly at random among all points on the path.

Given oracle access to $f$ and the path, any (randomized) algorithm that finds a point $\left(i^{\prime},j^{\prime}\right)$ on the path that is within $\sqrt{N}$ (Manhattan distance) from $\left(i^{*},j^{*}\right)$ requires querying $f$ at $\Omega\left(\log N\right)$ points on the path that are at least $\sqrt{N}$ apart.

Observe that once we fix the path, the values of $f$ outside the path do not reveal information about the location of $\left(i^{*},j^{*}\right)$. The lower bound now follows from the standard lower bound for binary search. ∎

Choosing the central path

Our goal now is to prove that it is hard to find many distant points on the path. To simplify the analysis, we will only consider the special case where all points $\left(x,y\right)$ on the path satisfy $x-y\in\left[-N^{1/4},N^{1/4}\right]$. We partition the $N\times N$ grid into $\Theta\left(\sqrt{N}\right)$ regions of the form $R_{a}\triangleq\left\{\left(x,y\right)\mid x+y\in[a,a+\sqrt{N})\right\}$. Notice that each region intersects the path at exactly $\sqrt{N}$ points. The path enters each regionFor the first and last region, the path is obviously forced to start at $\left(1,1\right)$ (respectively end at $\left(N,N\right)$); but those two regions can only account for two of the $\Omega\left(\log N\right)$ distant path points required by Claim 4.3, so we can safely ignore them. at a point $\left(x,y\right)$ for a value $x-y$ chosen uniformly at random among $\left[-N^{1/4},N^{1/4}\right]$. We will argue (Lemma 4.6 below) that in order to find a point on the path in any region $R_{a}$, the algorithm must query the function at $\Omega\left(\log N\right)$ points in $R_{a}$ or its neighboring regions.

Each region is further partitioned into $\Theta\left(N^{1/4}\right)$ sub-regions $S_{a}\triangleq\left\{\left(x,y\right)\mid x+y\in[a,a+2N^{1/4})\right\}$. For each region, we choose a special sub-region uniformly at random. In all non-special sub-regions, the path proceeds while maintaining $x-y$ fixed, up to $\pm 1$. Inside the special sub-region, the value of $x-y$ for path points changes from the value chosen at random for the current region, to the value chosen at random for the next region.

Given a choice of random $x-y$ entry point for each region, and a random special sub-region for each region, we consider an arbitrary path that satisfies the description above. This completes the description of the construction.

Finding the special sub-region in region $R_{a}$ requires $\Omega\left(\log N\right)$ queries to points in $R_{a}$.

Let $S_{a}$ and $S_{b}$ be the special sub-regions of two consecutive regions. Let $T\triangleq\left\{\left(x,y\right)\mid x+y\in[a+2N^{1/4},b)\right\}$ be the union of all the sub-regions between $S_{a}$ and $S_{b}$. Observe that the value of $x-y$ remains fixed (up to $\pm 1$) for all points in the intersection of the path with $T$. Also, the construction of $f$ outside $S_{a}\cup T\cup S_{b}$ does not depend at all on this value.

In order to find any point in the intersection of the path and $T$, the algorithm must query either $\Omega\left(\log N\right)$ points from $T$, or at least one point from $S_{a}$ or $S_{b}$.

By Claim 4.4, finding $S_{a}$ or $S_{b}$ requires at least $\Omega\left(\log N\right)$ queries to the regions containing them. Therefore, the above two claims together imply:

In order to query a point in the intersection of the path and region $R_{a}$, any algorithm must query at least $\Omega\left(\log N\right)$ points in $R_{a}$ or its neighboring regions.

Therefore, in order to find $\Omega\left(\log N\right)$ points on the path that are at least $\sqrt{N}$ apart, the algorithm must make a total of $\Omega\left(\log^{2}N\right)$ queries, completing the proof of Theorem 4.1. ∎

1 An alternative proof

Any deterministic black box algorithm for finding a Tarski fixed point in two dimensions needs $\Omega(\log^{2}N)$ queries.

This proof appears to be more promising to generalize to more dimensions: its gist is that any such algorithm must solve $\Omega(\log N)$ independent one-dimensional problems.

We shall describe a simple strategy for the adversary that achieves this bound. The adversary’s strategy is to again commit to “herringbone” functions as in Figure 1: the function consists of a main path consisting of a monotonically increasing path from $(1,1)$ to a point $x^{*}$, and a monotonically decreasing path from $(N,N)$ to $x^{*}$, with each step along the path, except for $x^{*}$, changing one dimension of the argument by one unit. For all points $(x,y)$ off the main path, $f(x,y)$ is either $(x-1,y+1)$ or $(x+1,y-1)$, depending on whether $(x,y)$ is below or above the main path, respectively; thus, the graph of the function is again herringbone-like, consisting of the main path, plus $45^{\hbox{\rm o}}$ paths towards the main path (see Figure 1).

For the sake of exposition and geometric intuition, we shall use a simple notation based on the eight cardinal directionsWe will try to avoid confusion between the direction N (North), and the number $N$. That is why we use boldface for the basic directions.: N, S, E, W, NW, SE, SW, NE. Thus, the answer $(x-1,y+1)$ to the query $f(x,y)$ will be denoted NW. To summarize the adversary’s strategy, the answer to a query $f(x,y)$ is either SE or NW, thus declaring that $(x,y)$ is not on the path, unless both answers would contradict monotonicity, in which case the adversary must choose one of the principal directions, N, S, E, W. A query of the latter type is termed a decisive query. Note that the answer to any non-decisive query $f(x,y)$ effectively “removes from consideration” a rectangular area of the grid — if $f(x,y)=NW$, the block $\{(x^{\prime},y^{\prime}):x^{\prime}\geq x,y^{\prime}\leq y\}$, that is the whole block to the SE of $(x,y)$, is excluded for further consideration in the sense that the main path can no longer intersect it, and all points $(x^{\prime},y^{\prime})$ in this block must have $f(x^{\prime},y^{\prime})=NW$.Strictly speaking point on the block’s boundary do not have this restriction, but let us assume that they do, as this simplification favors the algorithm. At any time, the union of these forbidden rectangles consist of an upper left region that contains all points that are above and/or to the left of the query points $(x,y)$ that point SE (i.e. such that $f(x,y)=SE$) and a lower right region that contains all points that are below or to the right of query points that point NW. The two forbidden regions are bounded by monotone staircase curves, and the main path must lie strictly between these two curves.

A query at point $q=(x,y)$ is decisive precisely when both points $(x-1,y+1)$ and $(x+1,y-1)$ to the NW and SE of $q$ belong to the forbidden area, the first one to (the boundary of) the upper left region and the second one to the lower right region. Thus, the main path must pass through the query point $q$ and now the adversary must decide whether the fixed point $x^{*}$ is above or below $(x,y)$.

How is this decision, as well as the decisions off the path (the choice between NW and SE) made? At any query, the algorithm has effectively determined that the part of the main path of current interest (certain to include the fixed point) is one of the possible monotonically increasing paths from some point $(\underline{x},\underline{y})$ (the SW-most part of the domain), either the origin or a past decisive query, to some point $(\bar{x},\bar{y})>(\underline{x},\underline{y})$ (the NE-most point of the domain) that avoids all blocks removed by past non-decisive queries. We call this region the current domain. During a decisive query $q$, the algorithm has to choose: which of the two subdomains of the current domain, the one to the SW or the one to the NE, will be the new domain? The answer is whichever subdomain has the largest number of potential main paths. Since there is at least one potential main path remaining, at least one of the directions ${\bf S}$, ${\bf W}$ must be available at $q$ (i.e., the point below or to the left of $q=(x,y)$ is not forbidden - it is possible that both are available), and similarly at least one of the directions ${\bf N}$, ${\bf E}$ must be available at $q$. The adversary compares the number of feasible monotone paths in the lower and upper subdomain (i.e. the number of feasible monotone paths between $(\underline{x},\underline{y})$ and $q$, to the number between $q$ and $(\bar{x},\bar{y})$), continues in the subdomain with the largest number of paths, and if both choices for direction are available in this subdomain, then it chooses again the direction with the larger number of paths.

During any non-decisive query, the same criterion is used: The adversary will choose the answer among NW and SE that will result in a new domain (the previous domain with one block removed) with the largest number of paths that avoid all blocks, among the two possible choices. But there is an exception: If the domain is becoming very narrow — that is, if the NW or the SE forbidden region is very close to the query point $q$ - then a different rule is used. Specifically, if the NW-SE line through the query point $q$ hits the boundary of the forbidden region on either side within distance $\leq w/2=N^{\alpha}/2$, where $\alpha<1$ (for concreteness, assume for the rest of the proof that $\alpha=1/2$ and we measure for simplicity the length of diagonal paths in the $L_{\infty}$ metric), then the adversary chooses the direction NW or SE from $q$ that is furthest from the forbidden region (breaking ties arbitrarily). We call such queries short queries.

This completes the description of the adversary’s strategy. The potential function that will inform our lower bound is the logarithm of the number of main paths is the current domain. That is, for each time $t$, we define $L_{t}$ as the logarithm of the number of monotonically increasing paths in the domain at time $t$ (that is to say, just before the $t$-th query). In the beginning, $L_{1}\geq N$ — actually, it is $2N-{1\over 2}\log N+o(1)$, since the number of paths is ${2N}\choose{N}$. When the algorithm concludes, $L_{t}=0$ (since there is only one path left, the one containing the fixed point). If the $t$-th query is a decisive query, then $L_{t+1}\geq{L_{t}\over 2}-1$, since the number of main paths before query $t$ was precisely the product of the number of paths in the upper and lower subdomain, the adversary will choose to continue in the subdomain with the largest of the two (thus, with at least the square root of the number of paths), and if there are two available choices of direction in the subdomain, it chooses the direction with the larger number of paths.

If the $t$-th query $q$ is a non-decisive and non-short query, then all feasible paths, except for those that go through the query point $q$, belong obviously to either the feasible domain that results if $f(q)=NW$ or the domain that results if $f(q)=SE$. Since $q$ is not a short query, the number of feasible paths that go through $q$ is a small fraction of the total number of feasible paths. Since the adversary chooses the direction among NW, SE with the larger number of paths, it follows that this number is approximately at least one half of the paths, hence certainly $L_{t+1}\geq L_{t}-2$.

The following lemma describes what happens at short queries:

If $t$ is a short query, then $L_{t+1}\geq L_{t}-N^{\alpha}\log N$.

Consider a short query $q$ and the NW to SE line through it, which intersects the boundary of the upper left forbidden region at $a$ and the boundary of the lower right region at $b$. Suppose wlog that the adversary in this case chose $f(q)=NW$, that is, $|qa|\geq|qb|$, where $|qa|,|qb|$ is the length of the segments $qa,qb$ (in $L_{\infty}$ metric). Since $q$ is a short query, $d=|qb|\leq w/2$. Let $s$ be the minimum point of the current domain, and $u$ the maximum. For a point $p$ of the segment $ab$, we let $n_{p}$ denote the number of monotone feasible paths from $s$ to $u$ that go through $p$. Let $Q$ be the number of paths that go through a point in the $qa$ segment, and $Q^{\prime}$ the number of paths that go through a point in the $qb$ segment.