Discrete fixed-point theorem explained

In discrete mathematics, a discrete fixed-point is a fixed-point for functions defined on finite sets, typically subsets of the integer grid

Z ^{n} .

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

f: X\to R ^{n} , where the domain X is a nonempty subset of the Euclidean space R ^{n} . ch(X) denotes the convex hull of X.

Iimura-Murota-Tamura theorem: If X is a finite integrally-convex subset of

Z ^{n} , and f: X\to 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

R ^{n} , and f: X\to ch (X) is simplicially direction-preserving (SDP), then f has a fixed-point.

Yang's theorems:

• [3.6] If X is a finite integrally-convex subset of

Z ^{n} , f: X\to R ^{n} is simplicially gross direction preserving (SGDP), and for all x in X there exists some g(x)>0 such that x + g(x)f(x)\in ch (X) , then f has a zero point.

• [3.7] If X is a finite hypercubic subset of

Z ^{n} , with minimum point a and maximum point b, f: X\to R ^{n} is SGDP, and for any x in X: f _{i(x} _{1,\ldots,x} _{i-1} ,a _{i,x} _{i+1} ,\ldots,x _{n)} \leq 0 and 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.

• [3.8] If X is a finite integrally-convex subset of

Z ^{n} , and f: X\to ch (X) is such that f(x) - x is SGDP, then f has a fixed-point.^[5] This is a discrete analogue of the Brouwer fixed-point theorem.

• [3.9] If X =

Z ^{n} , f: X\to R ^{n} is bounded and 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 Z ^{n} that bounds f).

• [3.10] If X is a finite integrally-convex subset of

Z ^{n} , F: X\to 2 ^{X} a point-to-set mapping, and for all x in X: F(x) = ch (F(x))\cap Z ^{n} , and there is a function f such that f(x)\in ch (F(x)) and f(x) - x is SGDP, then there is a point y in X such that 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.

• [3.12] Suppose X is a finite integrally-convex subset of

Z ^{n} , and it is also symmetric in the sense that x is in X iff -x is in X. If f: X\to 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 f(x) ⋅ 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:^[6]

Let X be a non-empty convex compact subset of

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 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) \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.^[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.^[8]

Notes and References

1. Iimura. Takuya. 2003-09-01. A discrete fixed point theorem and its applications. Journal of Mathematical Economics. en. 39. 7. 725–742. 10.1016/S0304-4068(03)00007-7. 0304-4068.
2. Iimura. Takuya. Murota. Kazuo. Tamura. Akihisa. 2005-12-01. Discrete fixed point theorem reconsidered. Journal of Mathematical Economics. en. 41. 8. 1030–1036. 10.1016/j.jmateco.2005.03.001. 0304-4068.
3. Book: Chen. Xi. Deng. Xiaotie. 2006. Chen. Danny Z.. Lee. D. T.. A Simplicial Approach for Discrete Fixed Point Theorems. Computing and Combinatorics. Lecture Notes in Computer Science. 4112. en. Berlin, Heidelberg. Springer. 3–12. 10.1007/11809678_3. 978-3-540-36926-4.
4. Yang. Zaifu. 2009-12-01. 2004 (FBA working paper no. 210, Yokohama National University). Discrete fixed point analysis and its applications. Journal of Fixed Point Theory and Applications. en. 6. 2. 351–371. 10.1007/s11784-009-0130-9. 122640338. 1661-7746.
5. Yang. Zaifu. 2008-11-01. On the Solutions of Discrete Nonlinear Complementarity and Related Problems. Mathematics of Operations Research. 33. 4. 976–990. 10.1287/moor.1080.0343. 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. en. 36. 1. 89–93. 10.1016/j.orl.2007.03.008. 14117444 . 0167-6377. 10419/86189. free.
7. Bich . Philippe . 2006 . Some fixed point theorems for discontinuous mappings . Cahiers de la Maison des Sciences Économiques . en.
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. en. 6. 2. 333–349. 10.1007/s11784-009-0131-8. 121519442. 1661-7746.