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 .

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

edit

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

edit

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:[2] 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:[3] If X is a finite subset of  , and   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  ,   is simplicially gross direction preserving (SGDP), and for all x in X there exists some g(x)>0 such that  , then f has a zero point.
  • [3.7] If X is a finite hypercubic subset of  , with minimum point a and maximum point b,   is SGDP, and for any x in X:   and  , 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  , and   is such that   is SGDP, then f has a fixed-point.[5] This is a discrete analogue of the Brouwer fixed-point theorem.
  • [3.9] If X =  ,   is bounded and   is SGDP, then f has a fixed-point (this follows easily from the previous theorem by taking X to be a subset of   that bounds f).
  • [3.10] If X is a finite integrally-convex subset of  ,   a point-to-set mapping, and for all x in X:   , and there is a function f such that   and   is SGDP, then there is a point y in X such that  . 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  , and it is also symmetric in the sense that x is in X iff -x is in X. If   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   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

edit

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  . Let f: XX 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.[7]: 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.

Applications

edit

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

edit
  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. ^ a b 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. ^ a b 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. ^ a b c 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. 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.