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 formula_1.
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.
For functions on discrete sets.
We focus on functions formula_2, where the domain X is a nonempty subset of the Euclidean space formula_3. ch("X") denotes the convex hull of "X".
Iimura-Murota-Tamura theorem: If "X" is a finite integrally-convex subset of formula_1, and formula_5 is a "hypercubic direction-preserving (HDP)" function, then "f" has a fixed-point.
Chen-Deng theorem: If "X" is a finite subset of formula_3, and formula_5 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 polytope in formula_3. 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 formula_17 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.: formula_33. 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. Then "f" has a fixed point in "X". 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.