Misplaced Pages

In discrete mathematics, a discrete fixed-point is a fixed-point for functions defined on finite sets, typically subsets of the integer grid ${\displaystyle \mathbb {Z} ^{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 ${\displaystyle f:X\to \mathbb {R} ^{n}}$, where the domain X is a nonempty subset of the Euclidean space ${\displaystyle \mathbb {R} ^{n}}$. ch(X) denotes the convex hull of X.

Iimura-Murota-Tamura theorem: If X is a finite integrally-convex subset of ${\displaystyle \mathbb {Z} ^{n}}$, and ${\displaystyle f:X\to {\text{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 ${\displaystyle \mathbb {R} ^{n}}$, and ${\displaystyle f:X\to {\text{ch}}(X)}$ is simplicially direction-preserving (SDP), then f has a fixed-point.

Yang's theorems:

• If X is a finite integrally-convex subset of ${\displaystyle \mathbb {Z} ^{n}}$, ${\displaystyle f:X\to \mathbb {R} ^{n}}$ is simplicially gross direction preserving (SGDP), and for all x in X there exists some g(x)>0 such that ${\displaystyle x+g(x)f(x)\in {\text{ch}}(X)}$, then f has a zero point.
• If X is a finite hypercubic subset of ${\displaystyle \mathbb {Z} ^{n}}$, with minimum point a and maximum point b, ${\displaystyle f:X\to \mathbb {R} ^{n}}$ is SGDP, and for any x in X: ${\displaystyle f_{i}(x_{1},\ldots ,x_{i-1},a_{i},x_{i+1},\ldots ,x_{n})\leq 0}$ and ${\displaystyle f_{i}(x_{1},\ldots ,x_{i-1},b_{i},x_{i+1},\ldots ,x_{n})\geq 0}$, then f has a zero point. This is a discrete analogue of the Poincaré–Miranda theorem. It is a consequence of the previous theorem.
• If X is a finite integrally-convex subset of ${\displaystyle \mathbb {Z} ^{n}}$, and ${\displaystyle f:X\to {\text{ch}}(X)}$ is such that ${\displaystyle f(x)-x}$ is SGDP, then f has a fixed-point. This is a discrete analogue of the Brouwer fixed-point theorem.
• If X = ${\displaystyle \mathbb {Z} ^{n}}$, ${\displaystyle f:X\to \mathbb {R} ^{n}}$ is bounded and ${\displaystyle f(x)-x}$ is SGDP, then f has a fixed-point (this follows easily from the previous theorem by taking X to be a subset of ${\displaystyle \mathbb {Z} ^{n}}$ that bounds f).
• If X is a finite integrally-convex subset of ${\displaystyle \mathbb {Z} ^{n}}$, ${\displaystyle F:X\to 2^{X}}$ a point-to-set mapping, and for all x in X: ${\displaystyle F(x)={\text{ch}}(F(x))\cap \mathbb {Z} ^{n}}$ , and there is a function f such that ${\displaystyle f(x)\in {\text{ch}}(F(x))}$ and ${\displaystyle f(x)-x}$ is SGDP, then there is a point y in X such that ${\displaystyle y\in F(y)}$. This is a discrete analogue of the Kakutani fixed-point theorem, and the function f is an analogue of a continuous selection function.
• Suppose X is a finite integrally-convex subset of ${\displaystyle \mathbb {Z} ^{n}}$, and it is also symmetric in the sense that x is in X iff -x is in X. If ${\displaystyle f:X\to \mathbb {R} ^{n}}$ 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 ${\displaystyle f(x)\cdot f(-y)\leq 0}$ 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 ${\displaystyle \mathbb {R} ^{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 ${\displaystyle 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.: ${\displaystyle (f(y)-y)\cdot (f(z)-z)\geq 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.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.

References

1. Iimura, Takuya (2003-09-01). "A discrete fixed point theorem and its applications". Journal of Mathematical Economics. 39 (7): 725–742. doi:10.1016/S0304-4068(03)00007-7. ISSN 0304-4068.
2. ^ Iimura, Takuya; Murota, Kazuo; Tamura, Akihisa (2005-12-01). "Discrete fixed point theorem reconsidered". Journal of Mathematical Economics. 41 (8): 1030–1036. doi:10.1016/j.jmateco.2005.03.001. ISSN 0304-4068.
3. ^ Chen, Xi; Deng, Xiaotie (2006). "A Simplicial Approach for Discrete Fixed Point Theorems". In Chen, Danny Z.; Lee, D. T. (eds.). Computing and Combinatorics. Lecture Notes in Computer Science. Vol. 4112. Berlin, Heidelberg: Springer. pp. 3–12. doi:10.1007/11809678_3. ISBN 978-3-540-36926-4.
4. ^ Yang, Zaifu (2009-12-01) . "Discrete fixed point analysis and its applications". Journal of Fixed Point Theory and Applications. 6 (2): 351–371. doi:10.1007/s11784-009-0130-9. ISSN 1661-7746. S2CID 122640338.
5. Yang, Zaifu (2008-11-01). "On the Solutions of Discrete Nonlinear Complementarity and Related Problems". Mathematics of Operations Research. 33 (4): 976–990. doi:10.1287/moor.1080.0343. ISSN 0364-765X.
6. Jean-Jacques Herings, P.; van der Laan, Gerard; Talman, Dolf; Yang, Zaifu (2008-01-01). "A fixed point theorem for discontinuous functions". Operations Research Letters. 36 (1): 89–93. doi:10.1016/j.orl.2007.03.008. hdl:10419/86189. ISSN 0167-6377. S2CID 14117444.
7. Bich, Philippe (2006). "Some fixed point theorems for discontinuous mappings". Cahiers de la Maison des Sciences Économiques.
8. Iimura, Takuya; Yang, Zaifu (2009-12-01). "A study on the demand and response correspondences in the presence of indivisibilities". Journal of Fixed Point Theory and Applications. 6 (2): 333–349. doi:10.1007/s11784-009-0131-8. ISSN 1661-7746. S2CID 121519442.

• Discrete mathematics
• Fixed-point theorems