Английская Википедия: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>\mathbb{Z}^n</math>.
Discrete fixed-point theorems were developed by Iimura,[1] Murota and Tamura,[2] Chen and Deng[3] and others. Yang[4] 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>f: X\to \mathbb{R}^n</math>, where the domain X is a nonempty subset of the Euclidean space <math>\mathbb{R}^n</math>. ch(X) denotes the convex hull of X.
Iimura-Murota-Tamura theorem:[2] If X is a finite integrally-convex subset of <math>\mathbb{Z}^n</math>, and <math>f: X\to \text{ch}(X)</math> is a hypercubic direction-preserving (HDP) function, then f has a fixed-point.
Chen-Deng theorem:[3] If X is a finite subset of <math>\mathbb{R}^n</math>, and <math>f: X\to \text{ch}(X)</math> is simplicially direction-preserving (SDP), then f has a fixed-point.
Yang's theorems:[4]
- [3.6] If X is a finite integrally-convex subset of <math>\mathbb{Z}^n</math>, <math>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>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>\mathbb{Z}^n</math>, with minimum point a and maximum point b, <math>f: X\to \mathbb{R}^n</math> is SGDP, and for any x in X: <math>f_i(x_1,\ldots,x_{i-1},a_i,x_{i+1},\ldots,x_n) \leq 0 </math> and <math>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>\mathbb{Z}^n</math>, and <math>f: X\to \text{ch}(X)</math> is such that <math>f(x)-x</math> is SGDP, then f has a fixed-point.[5] This is a discrete analogue of the Brouwer fixed-point theorem.
- [3.9] If X = <math>\mathbb{Z}^n</math>, <math>f: X\to \mathbb{R}^n</math> is bounded and <math>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>\mathbb{Z}^n</math> that bounds f).
- [3.10] If X is a finite integrally-convex subset of <math>\mathbb{Z}^n</math>, <math>F: X\to 2^X</math> a point-to-set mapping, and for all x in X: <math>F(x) = \text{ch}(F(x))\cap \mathbb{Z}^n</math> , and there is a function f such that <math>f(x)\in \text{ch}(F(x))</math> and <math>f(x)-x</math> is SGDP, then there is a point y in X such that <math>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>\mathbb{Z}^n</math>, and it is also symmetric in the sense that x is in X iff -x is in X. If <math>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>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[4] 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:[6]
Let X be a non-empty convex compact subset of <math>\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>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>(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.[7]Шаблон:RpNote 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.[8]
References
