Discrete fixed-point theorem

In discrete mathematics, a discrete fixed-point is a fixed-point for functions defined on finite sets, typically subsets of the integer grid [math]\displaystyle{ \mathbb{Z}^n }[/math]. Discrete fixed-point theorems were developed by Iimura, Murota and Tamura, Chen and Deng and others. Yang provides a survey.

Basic concepts

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.

For functions on discrete sets

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

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

Chen-Deng theorem: If X is a finite subset of [math]\displaystyle{ \mathbb{R}^n }[/math], and [math]\displaystyle{ f: X\to \text{ch}(X) }[/math] 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 [math]\displaystyle{ \mathbb{Z}^n }[/math], [math]\displaystyle{ f: X\to \mathbb{R}^n }[/math] is simplicially gross direction preserving (SGDP), and for all x in X there exists some g(x)>0 such that [math]\displaystyle{ x+g(x)f(x)\in \text{ch}(X) }[/math], then f has a zero point.
• [3.7] If X is a finite hypercubic subset of [math]\displaystyle{ \mathbb{Z}^n }[/math], with minimum point a and maximum point b, [math]\displaystyle{ f: X\to \mathbb{R}^n }[/math] is SGDP, and for any x in X: [math]\displaystyle{ f_i(x_1,\ldots,x_{i-1},a_i,x_{i+1},\ldots,x_n) \leq 0 }[/math] and [math]\displaystyle{ f_i(x_1,\ldots,x_{i-1},b_i,x_{i+1},\ldots,x_n) \geq 0 }[/math], 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 [math]\displaystyle{ \mathbb{Z}^n }[/math], and [math]\displaystyle{ f: X\to \text{ch}(X) }[/math] is such that [math]\displaystyle{ f(x)-x }[/math] is SGDP, then f has a fixed-point. This is a discrete analogue of the Brouwer fixed-point theorem.
• [3.9] If X = [math]\displaystyle{ \mathbb{Z}^n }[/math], [math]\displaystyle{ f: X\to \mathbb{R}^n }[/math] is bounded and [math]\displaystyle{ f(x)-x }[/math] is SGDP, then f has a fixed-point (this follows easily from the previous theorem by taking X to be a subset of [math]\displaystyle{ \mathbb{Z}^n }[/math] that bounds f).
• [3.10] If X is a finite integrally-convex subset of [math]\displaystyle{ \mathbb{Z}^n }[/math], [math]\displaystyle{ F: X\to 2^X }[/math] a point-to-set mapping, and for all x in X: [math]\displaystyle{ F(x) = \text{ch}(F(x))\cap \mathbb{Z}^n }[/math] , and there is a function f such that [math]\displaystyle{ f(x)\in \text{ch}(F(x)) }[/math] and [math]\displaystyle{ f(x)-x }[/math] is SGDP, then there is a point y in X such that [math]\displaystyle{ y \in F(y) }[/math]. 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 [math]\displaystyle{ \mathbb{Z}^n }[/math], and it is also symmetric in the sense that x is in X iff -x is in X. If [math]\displaystyle{ f: X\to \mathbb{R}^n }[/math] 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 [math]\displaystyle{ f(x)\cdot f(-y) \leq 0 }[/math] 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.

For discontinuous functions on continuous sets

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:

Let X be a non-empty convex compact subset of [math]\displaystyle{ \mathbb{R}^n }[/math]. 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 [math]\displaystyle{ f(x)-x }[/math] 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.: [math]\displaystyle{ (f(y)-y)\cdot (f(z)-z) \geq 0 }[/math]. Then f has a fixed point in X.

The theorem is originally stated for polytopes, but Philippe Bich extends it to convex compact sets.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.

Applications

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.