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 ℤn.

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 f:X→ℝn, where the domain X is a nonempty subset of the Euclidean space ℝn. ch(X) denotes the convex hull of X.

Iimura-Murota-Tamura theorem: If X is a finite integrally-convex subset of ℤn, and f:X→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 ℝn, and f:X→ch(X) is simplicially direction-preserving (SDP), then f has a fixed-point.

Yang's 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 ℝ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)⋅(f(z)−z)≥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.: 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.

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.