×

On the stability of finding approximate fixed points by simplicial methods. (English) Zbl 1354.55003

Summary: This paper reports some new results in relation to simplicial algorithms considering continuities of approximate fixed point sets. The upper semi-continuity of a set-valued mapping of approximate fixed points using vector-valued simplicial methods is proved, and thus one obtains the existence of finite essential connected components in approximate fixed point sets by vector-valued labels; examples are given to show that this is very different from the property for integer-valued labeling simplicial methods. The existence of essential sets is also proved focusing on both perturbations of domains and functions.

MSC:

55M20 Fixed points and coincidences in algebraic topology
55U10 Simplicial sets and complexes in algebraic topology
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Brouwer, LEJ: Über abbildung von mannigfaltigkeiten. Math. Ann. 71(1), 97-115 (1911) · JFM 42.0417.01 · doi:10.1007/BF01456931
[2] Nash, JF: Equilibrium points in n-person games. Proc. Natl. Acad. Sci. USA 36(1), 48-49 (1950) · Zbl 0036.01104 · doi:10.1073/pnas.36.1.48
[3] Arrow, K, Debreu, G: Existence of an equilibrium for a competitive economy. Econometrica 22, 265-290 (1954) · Zbl 0055.38007 · doi:10.2307/1907353
[4] Papadimitriou, CH, On graph-theoretic lemmata and complexity classes, 794-801 (1990), New York
[5] Cole, R.; Dodis, Y.; Roughgarden, T., Pricing network edges for heterogeneous selfish users, 521-530 (2003), New York · Zbl 1192.68032
[6] Low, SH: A duality model of TCP and queue management algorithms. IEEE/ACM Trans. Netw. 11(4), 525-536 (2003) · doi:10.1109/TNET.2003.815297
[7] Meinardus, G: Invarianz bei linearen Approximationen. Arch. Ration. Mech. Anal. 14(1), 301-303 (1963) · Zbl 0122.30801
[8] Spielmat, DA; Teng, SH, Spectral partitioning works: planar graphs and finite element meshes, 96-105 (1996), New York
[9] Scarf, H: The approximation of fixed points of a continuous mapping. SIAM J. Appl. Math. 15(5), 1328-1343 (1967) · Zbl 0153.49401 · doi:10.1137/0115116
[10] Kuhn, HW: Simplicial approximation of fixed points. Proc. Natl. Acad. Sci. USA 61(4), 1238-1242 (1968) · Zbl 0191.54904 · doi:10.1073/pnas.61.4.1238
[11] Kuhn, HW, MacKinnon, JG: Sandwich method for finding fixed points. J. Optim. Theory Appl. 17(3), 189-204 (1975) · Zbl 0299.65030 · doi:10.1007/BF00933874
[12] Merrill, OH: Applications and extensions of an algorithm that computes fixed points of certain upper semi-continuous point to set mappings. Technical report 71-7, University of Michigan (1972) · Zbl 1029.54050
[13] Van der Laan, G, Talman, A: A restart algorithm for computing fixed points without an extra dimension. Math. Program. 17(1), 74-84 (1979) · Zbl 0411.90061 · doi:10.1007/BF01588226
[14] Van der Laan, G, Talman, AJJ: A class of simplicial restart fixed point algorithms without an extra dimension. Math. Program. 20(1), 33-48 (1981) · Zbl 0441.90112 · doi:10.1007/BF01589331
[15] Talman, AJJ: Variable dimension fixed point algorithms and triangulations. Stat. Neerl. 35(1), 59 (1981) · doi:10.1111/j.1467-9574.1981.tb00713.x
[16] Eaves, BC: Homotopies for computation of fixed points. Math. Program. 3(1), 1-22 (1972) · Zbl 0276.55004 · doi:10.1007/BF01584975
[17] Herings, PJ-J, Peeters, R: Homotopy methods to compute equilibria in game theory. Econ. Theory 42(1), 119-156 (2010) · Zbl 1185.91028 · doi:10.1007/s00199-009-0441-5
[18] Fort, MK: Essential and nonessential fixed points. Am. J. Math. 72, 315-322 (1950) · Zbl 0036.13001 · doi:10.2307/2372035
[19] Kinoshita, S: On essential component of the set of fixed points. Osaka Math. J. 4, 19-22 (1952) · Zbl 0047.16204
[20] O’Neill, B: Essential sets and fixed points. Am. J. Math. 75, 497-509 (1953) · Zbl 0050.39202 · doi:10.2307/2372499
[21] McLennan, A: Selected topics in the theory of fixed points. University of Minnesota, Minneapolis (1989) · Zbl 0675.54041
[22] Tan, KK, Yu, J, Yuan, XZ: The stability of coincident points for multivalued mappings. Nonlinear Anal., Theory Methods Appl. 25, 163-168 (1995) · Zbl 0856.54045 · doi:10.1016/0362-546X(94)00223-5
[23] Isac, G, Yuan, GXZ: The essential components of coincident points for weakly inward and outward set-valued mappings. Appl. Math. Lett. 12, 121-126 (1999) · Zbl 0955.47040 · doi:10.1016/S0893-9659(99)00046-4
[24] Song, QQ: On essential sets of fixed points for functions. Numer. Funct. Anal. Optim. 36, 942-950 (2015) · Zbl 1356.54048 · doi:10.1080/01630563.2015.1043370
[25] Yu, J, Xiang, SW: The stability of the set of KKM points. Nonlinear Anal., Theory Methods Appl. 54, 839-844 (2003) · Zbl 1029.54050 · doi:10.1016/S0362-546X(03)00096-8
[26] Khanh, PQ, Quan, NH: Generic stability and essential components of generalized KKM points and applications. J. Optim. Theory Appl. 148, 488-504 (2011) · Zbl 1229.58016 · doi:10.1007/s10957-010-9764-4
[27] Yu, J: Essential equilibria of N-person noncooperative games. J. Math. Econ. 31, 361-372 (1999) · Zbl 0941.91006 · doi:10.1016/S0304-4068(97)00060-8
[28] Govindan, S, Wilson, R: Essential equilibria. Proc. Natl. Acad. Sci. USA 102, 15706-15711 (2005) · Zbl 1155.91304 · doi:10.1073/pnas.0506796102
[29] Carbonell-Nicolau, O: Essential equilibria in normal-form games. J. Econ. Theory 145, 421-431 (2010) · Zbl 1202.91009 · doi:10.1016/j.jet.2009.06.002
[30] Yang, H, Xiao, X: Essential components of Nash equilibria for games parametrized by payoffs and strategies. Nonlinear Anal., Theory Methods Appl. 71, e2322-e2326 (2009) · Zbl 1239.91007 · doi:10.1016/j.na.2009.05.029
[31] Song, QQ, Wang, LS: On the stability of the solution for multiobjective generalized games with the payoffs perturbed. Nonlinear Anal., Theory Methods Appl. 73, 2680-2685 (2010) · Zbl 1193.91031 · doi:10.1016/j.na.2010.06.048
[32] Yang, Z, Pu, YJ: Essential stability of solutions for maximal element theorem with applications. J. Optim. Theory Appl. 150, 284-297 (2011) · Zbl 1229.90267 · doi:10.1007/s10957-011-9812-8
[33] Hung, NV: Sensitivity analysis for generalized quasi-variational relation problems in locally G-convex spaces. Fixed Point Theory Appl. 2012, 158 (2012) · Zbl 1405.47026 · doi:10.1186/1687-1812-2012-158
[34] Yang, Z: On existence and essential stability of solutions of symmetric variational relation problems. J. Inequal. Appl. 2014, 5 (2014) · Zbl 1372.49023 · doi:10.1186/1029-242X-2014-5
[35] Hung, NV, Kieu, PT: On the existence and essential components of solution sets for systems of generalized quasi-variational relation problems. J. Inequal. Appl. 2014, 250 (2014) · Zbl 1472.47054 · doi:10.1186/1029-242X-2014-250
[36] Fort, MK: Points of continuity of semicontinuous function. Publ. Math. (Debr.) 2, 100-102 (1951) · Zbl 0044.05703
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.