Discrete Fixed Points: Models, Complexities, and Applications

References

• Arrow K., Debreu G. Existence of an equilibrium for a competetive economy. Econometrica (1954) 22:265–290Crossref, Google Scholar
• Bapat R. B. A constructive proof of a permutation-based generalization of Sperner's lemma. Math. Programming (1989) 44:1–3Crossref, Google Scholar
• Brin S., Page L. The anatomy of a large-scale hypertextual Web search engine. Proc. 7th World Wide Web Conf. (1998) Brisbane, Australia:107–117Crossref, Google Scholar
• Brouwer L. E. J. Ueber eineindeutige, stetige Transformationen von Flächen in sich. Mathematische Annalen (1910) 69:176–180Crossref, Google Scholar
• Chen X., Deng X. Settling the complexity of two-player nash equilibrium. Proc. 47th Annual IEEE Symp. Foundations Comput. Sci. (2006) Berkeley, CA:261–272Crossref, Google Scholar
• Chen X., Teng S.-H. Paths beyond local search: A tight bound for randomized fixed-point computation. 48th Annual IEEE Symp. Foundations Comput. Sci. (2007) Providence, RI:124–134Crossref, Google Scholar
• Chen X., Deng X. Matching algorithmic bounds for finding a Brouwer fixed point. J. ACM (2008) 55(3):13:1–13:26Crossref, Google Scholar
• Chen X., Deng X. On the complexity of 2D discrete fixed point problem. Theoret. Comput. Sci. (2009a) 410(44):4448–4456Crossref, Google Scholar
• Chen X., Deng X. A simplicial approach for discrete fixed point theorems. Algorithmica (2009b) 53(2):3–12Crossref, Google Scholar
• Chen X., Deng X., Teng S.-H. Computing Nash equilibria: Approximation and smoothed complexity. 47th Annual IEEE Symp. Foundations Comput. Sci. (2006) Berkeley, CA:603–612Crossref, Google Scholar
• Chen X., Sun X., Teng S.-H. Quantum separation of local search and fixed point Computation. Proc. 14th Annual Internat. Comput. Combinatorics Conf. (2008) Dalian, China:170–179Crossref, Google Scholar
• Chen X., Deng X., Teng S.-H. Settling the complexity of computing two-player Nash equilibria. J. ACM (2009) 56(3):14:1–14:57Crossref, Google Scholar
• Cohen D. I. A. On the combinatorial antipodal-point lemmas. J. Combin. Theory (Ser. B) (1979) 27:87–91Crossref, Google Scholar
• Cole R., Dodis Y., Roughgarden T. Pricing network edges for heterogeneous selfish users. Proc. 35th Annual ACM Symp. Theory Comput. (2003) San Diego:521–530Crossref, Google Scholar
• Crescenzi P., Silvestri R. Sperner's lemma and robust machines. Comput. Complexity (1998) 7(2):163–173Crossref, Google Scholar
• Daskalakis C., Goldberg P. W., Papadimitriou C. H. The complexity of computing a Nash equilibrium. 38th ACM Symp. Theory Comput. (2006) Seattle, WA:71–78Crossref, Google Scholar
• Deng X., Qi Q., Saberi A. On the complexity of envy-free cake cutting. (2009) . http://arxiv.org/abs/0907.1334Google Scholar
• Eaves B. C. On the basic theorem of complementarity. Math. Programming (1971) 1(1):68–75Crossref, Google Scholar
• Fan K. A generalization of Tucker's combinatorial lemma with topological applications. Ann. Math. (Second Ser.) (1952) 56(3):431–437Crossref, Google Scholar
• Friedl K., Ivanyos G., Santha M., Verhoeven F. On the black-box complexity of sperner's lemma. Proc. 15th Internat. Symp. Fundamentals Comput. Theory (2005) Lübeck, Germany:245–257Crossref, Google Scholar
• Freund R. M. Variable dimension complexes Part I: Basic theory. Math. Oper. Res. (1984a) 9(4):479–497Link, Google Scholar
• Freund R. M. Variable dimension complexes Part II: A unified approach to some combinatorial lemmas in topology. Math. Oper. Res. (1984b) 9(4):498–509Link, Google Scholar
• Fujimoto T. An extension of Tarski's fixed point theorem and its application to isotone complementarity problems. Math. Programming (1984) 28(1):116–118Crossref, Google Scholar
• Herings J. J., Talman D., Yang Z. The computation of a continuum of constrained equilibria. Math. Oper. Res. (1996) 21(3Link, Google Scholar
• Hirsch M. D., Papadimitriou C. H., Vavasis S. Exponential lower bounds for finding brouwer fixed points. J. Complexity (1989) 5:379–416Crossref, Google Scholar
• Hyvärinen A., Oja E. Fast and robust fixed-point algorithms for independent component analysis. Neural Comput. (1997) 9:1483–1492Crossref, Google Scholar
• Iimura T. A discrete fixed point theorem and its applications. J. Math. Econom. (2003) 39:725–742Crossref, Google Scholar
• Kleinberg J. Authoritative sources in a hyperlinked environment. J. ACM (1998) 46(5):604–632Crossref, Google Scholar
• Kintali S., Poplawski L. J., Rajaraman R., Sundaram R., Teng S.-H. Reducibility among fractional stability problems. Proc. 50th Annual Symp. Foundations Comput. Sci. (2009) Atlanta:283–292Crossref, Google Scholar
• Kuhn K. W. Some combinatorial lemmas in topology. IBM J. Res. Development (1960) 4(5):518–524Crossref, Google Scholar
• Laan G. V. D., Talman A. J. J., Yang Z. Solving discrete zero point problems. Math. Programming (2006) 108(1):127–134Crossref, Google Scholar
• Lemke C. E., Howson J. T. Equilibrium points of bimatrix games. J. Soc. Indust. Appl. Math. (1964) 12:413–423Crossref, Google Scholar
• Longueville M., Živaljević R. T. The Borsuk-Ulam-property, Tucker-property and constructive proofs in combinatorics. J. Combin. Theory (Ser. A) (2006) 113:839–850Crossref, Google Scholar
• Low S. A duality model of tcp and queue management algorithms. IEEE/ACM Trans. Networking (2003) 11(4):525–536Crossref, Google Scholar
• Matoušek J. A combinatorial proof of Kneser's conjecture. Combinatorica (2004) 24:163–170Crossref, Google Scholar
• Mehta A., Shenker S., Vazirani V. Profit-maximizing multicast pricing by approximating fixed points. Proc. ACM Conf. Electronic Commerce (2003) San Diego:218–219Google Scholar
• Megiddo N., Papadimitriou C. H. A Note on total functions, existence theorems and computational complexity. Theoret. Comput. Sci. (1991) 81:317–324Crossref, Google Scholar
• Meinardus G. Invarianz bei linearen approximationen. Archive Rational Mech. Anal. (1663) 14:301–303Crossref, Google Scholar
• Meunier F. Discrete splittings of the necklace. Math. Oper. Res. (2008) 33(3):678–688Link, Google Scholar
• Nash J. Equilibrium points in n-person games. Proc. National Acad. (1950) 36(1):48–49Crossref, Google Scholar
• Pálvölgyi D. 2D-TUCKER is PPAD-complete. Proc. 5th Internat. Workshop Internet Network Econom. (2009) Rome, Italy:569–574Crossref, Google Scholar
• Papadimitriou C. H. On the complexity of the parity argument and other inefficient proofs of existence. J. Comput. System Sci. (1994) 48:498–532Crossref, Google Scholar
• Robinson C.Dynamical Systems, Stability, Symbolic Dynamics, and Chaos (1999) (CRC Press, Boca Raton, FL) Google Scholar
• Savani R., von Stengel B. Hard-to-solve bimatrix games. Econometrica (2006) 74:397–429Crossref, Google Scholar
• Scarf H. E. The approximation of fixed points of a continuous mapping. SIAM J. Appl. Math. (1967) 15:997–1007Crossref, Google Scholar
• Simmons F. W., Su F. E. Consensus-halving via theorems of Borsuk-Ulam and Tucker. Math. Soc. Sci. (2003) 45:15–25Crossref, Google Scholar
• Sperner E. Neuer Beweis für die Invarianz der Dimensionszahl und des Gebietes. Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg (1928) 6:265–272Crossref, Google Scholar
• Spielman D., Teng S.-H. Spectral partitioning works: Planar graphs and finite element meshes. Proc. 37th Annual Symp. Foundations Comput. Sci. (1996) Burlington, VT:96–105Crossref, Google Scholar
• Su F. E. Rental harmony: Sperner's lemma in fair division. Amer. Math. Monthly (1999) 106:930–942Crossref, Google Scholar
• Talman A. J. J., Yang Z. A constructive proof of Ky Fan's coincidence theorem. Math. Programming (Ser. A) (2009) 118:317–325Crossref, Google Scholar
• Todd M. J. The computation of fixed points and applications. Lecture Notes in Economics and Mathematical Systems (1976) (Springer-Verlag, New York) Google Scholar
• Todd M. J. A quadratically-convergent fixed-point algorithm for economic equilibria and linearly constrained optimization. Math. Programming (1980) 18(1):111–126Crossref, Google Scholar
• Tucker A. W. Some topological properties of disk and sphere. Proc. First Canadian Math. Congress (1945) Montréal, Canada:285–309Google Scholar
• Yamamoto Y. A new variable dimension algorithm for the fixed point problem. Math. Programming (1983) 25(3):329–342Crossref, Google Scholar
• Ye Y. A path to the Arrow-Debreu competitive market equilibrium. Math. Programming (2007) 111(1–2):315–348Crossref, Google Scholar