In discrete mathematics, a discrete fixed-point is a fixed-point for functions defined on finite sets, typically subsets of the integer grid .
Discrete fixed-point theorems were developed by Iimura, Murota and Tamura, Chen and Deng and others. Yang provides a survey.
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 , where the domain X is a nonempty subset of the Euclidean space . ch(X) denotes the convex hull of X.
Iimura-Murota-Tamura theorem: If X is a finite integrally-convex subset of , and is a hypercubic direction-preserving (HDP) function, then f has a fixed-point.
Chen-Deng theorem: If X is a finite subset of , and is simplicially direction-preserving (SDP), then f has a fixed-point.
Yang's 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:
Let X be a non-empty convex compact subset of . 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 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.: . 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.
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.