Discrete fixed-point theorem

Continuous fixed-point theorems often require a continuous function. Since continuity is not meaningful for functions on discrete sets, it is replaced by conditions such as a direction-preserving function. Such conditions imply that the function does not change too drastically when moving between neighboring points of the integer grid. There are various direction-preservation conditions, depending on whether neighboring points are considered points of a hypercube (HGDP), of a simplex (SGDP) etc. See the page on direction-preserving function for definitions.

Continuous fixed-point theorems often require a convex set. The analogue of this property for discrete sets is an integrally-convex set.

A fixed point of a discrete function f is defined exactly as for continuous functions: it is a point x for which f(x)=x.

We focus on functions $f:\; X\backslash to\; \backslash mathbb\{R\}^n$, where the domain X is a nonempty subset of the Euclidean space $\backslash mathbb\{R\}^n$. ch(X) denotes the convex hull of X.

Iimura-Murota-Tamura theorem: If X is a finite integrally-convex subset of $\backslash mathbb\{Z\}^n$, and $f:\; X\backslash to\; \backslash text\{ch\}(X)$ is a hypercubic direction-preserving (HDP) function, then f has a fixed-point.

Chen-Deng theorem: If X is a finite subset of $\backslash mathbb\{R\}^n$, and $f:\; X\backslash to\; \backslash text\{ch\}(X)$ is simplicially direction-preserving (SDP), then f has a fixed-point.

Yang's theorems:

• [3.6] If X is a finite integrally-convex subset of $\backslash mathbb\{Z\}^n$, $f:\; X\backslash to\; \backslash mathbb\{R\}^n$ is simplicially gross direction preserving (SGDP), and for all x in X there exists some g(x)>0 such that $x+g(x)f(x)\backslash in\; \backslash text\{ch\}(X)$, then f has a zero point.
• [3.7] If X is a finite hypercubic subset of $\backslash mathbb\{Z\}^n$, with minimum point a and maximum point b, $f:\; X\backslash to\; \backslash mathbb\{R\}^n$ is SGDP, and for any x in X: $f\_i(x\_1,\backslash ldots,x\_\{i-1\},a\_i,x\_\{i+1\},\backslash ldots,x\_n)\; \backslash leq\; 0$ and $f\_i(x\_1,\backslash ldots,x\_\{i-1\},b\_i,x\_\{i+1\},\backslash ldots,x\_n)\; \backslash geq\; 0$, then f has a zero point. This is a discrete analogue of the Poincaré–Miranda theorem. It is a consequence of the previous theorem.
• [3.8] If X is a finite integrally-convex subset of $\backslash mathbb\{Z\}^n$, and $f:\; X\backslash to\; \backslash text\{ch\}(X)$ is such that $f(x)-x$ is SGDP, then f has a fixed-point.{{Cite journal|last=Yang|first=Zaifu|date=2008-11-01|title=On the Solutions of Discrete Nonlinear Complementarity and Related Problems|journal=Mathematics of Operations Research|volume=33|issue=4|pages=976–990|doi=10.1287/moor.1080.0343|issn=0364-765X}} This is a discrete analogue of the Brouwer fixed-point theorem.
• [3.9] If X = $\backslash mathbb\{Z\}^n$, $f:\; X\backslash to\; \backslash mathbb\{R\}^n$ is bounded and $f(x)-x$ is SGDP, then f has a fixed-point (this follows easily from the previous theorem by taking X to be a subset of $\backslash mathbb\{Z\}^n$ that bounds f).
• [3.10] If X is a finite integrally-convex subset of $\backslash mathbb\{Z\}^n$, $F:\; X\backslash to\; 2^X$ a point-to-set mapping, and for all x in X: $F(x)\; =\; \backslash text\{ch\}(F(x))\backslash cap\; \backslash mathbb\{Z\}^n$ , and there is a function f such that $f(x)\backslash in\; \backslash text\{ch\}(F(x))$ and $f(x)-x$ is SGDP, then there is a point y in X such that $y\; \backslash in\; F(y)$. This is a discrete analogue of the Kakutani fixed-point theorem, and the function f is an analogue of a continuous selection function.
• [3.12] Suppose X is a finite integrally-convex subset of $\backslash mathbb\{Z\}^n$, and it is also symmetric in the sense that x is in X iff -x is in X. If $f:\; X\backslash to\; \backslash mathbb\{R\}^n$ is SGDP w.r.t. a weakly-symmetric triangulation of ch(X) (in the sense that if s is a simplex on the boundary of the triangulation iff -s is), and $f(x)\backslash cdot\; f(-y)\; \backslash leq\; 0$ for every pair of simplicially-connected points x, y in the boundary of ch(X), then f has a zero point.
• See the survey for more theorems.

Discrete fixed-point theorems are closely related to fixed-point theorems on discontinuous functions. These, too, use the direction-preservation condition instead of continuity.

Herings-Laan-Talman-Yang fixed-point theorem:{{Cite journal|last1=Jean-Jacques Herings|first1=P.|last2=van der Laan|first2=Gerard|last3=Talman|first3=Dolf|last4=Yang|first4=Zaifu|date=2008-01-01|title=A fixed point theorem for discontinuous functions|url=http://www.sciencedirect.com/science/article/pii/S0167637707000570|journal=Operations Research Letters|language=en|volume=36|issue=1|pages=89–93|doi=10.1016/j.orl.2007.03.008|s2cid=14117444 |issn=0167-6377|hdl=10419/86189|hdl-access=free}}

Let X be a non-empty convex compact subset of $\backslash mathbb\{R\}^n$. Let f: X → X be a locally gross direction preserving (LGDP) function: at any point x that is not a fixed point of f, the direction of $f(x)-x$ is grossly preserved in some neighborhood of x, in the sense that for any two points y, z in this neighborhood, its inner product is non-negative, i.e.: $(f(y)-y)\backslash cdot\; (f(z)-z)\; \backslash geq\; 0$. Then f has a fixed point in X.

The theorem is originally stated for polytopes, but Philippe Bich extends it to convex compact sets.{{Cite journal |last=Bich |first=Philippe |date=2006 |title=Some fixed point theorems for discontinuous mappings |url=https://shs.hal.science/halshs-00119033 |journal=Cahiers de la Maison des Sciences Économiques |language=en}}{{Rp|location=Thm.3.7}}Note that every continuous function is LGDP, but an LGDP function may be discontinuous. An LGDP function may even be neither upper nor lower semi-continuous. Moreover, there is a constructive algorithm for approximating this fixed point.

Discrete fixed-point theorems have been used to prove the existence of a Nash equilibrium in a discrete game, and the existence of a Walrasian equilibrium in a discrete market.{{Cite journal|last1=Iimura|first1=Takuya|last2=Yang|first2=Zaifu|date=2009-12-01|title=A study on the demand and response correspondences in the presence of indivisibilities|journal=Journal of Fixed Point Theory and Applications|language=en|volume=6|issue=2|pages=333–349|doi=10.1007/s11784-009-0131-8|s2cid=121519442|issn=1661-7746}}

{{reflist}}

Category:Discrete mathematics

Category:Fixed-point theorems