On algorithms for discrete and approximate brouwer fixed points

ABSTRACT

We study the algorithmic complexity of the discrete fixed point problem and develop an asymptotic matching bound for a cube in any constantly bounded finite dimension. To obtain our upper bound, we derive a new fixed point theorem, based on a novel characterization of boundary conditions for the existence of fixed points.In addition, exploring a linkage with the approximation problem of the continuous fixed point problem, we obtain asymptotic matching bounds for complexity of the approximate Brouwer fixed point problem in the continuous case for Lipschitz functions that close a previous exponential gap. It settles a fifteen years old open problem of Hirsch, Papadimitriou and Vavasis by improving both the upper and lower bounds.Our new characterization for existence of a fixed point is also applicable to functions defined on non-convex domain and makes it a potentially useful tool for design and analysis of algorithms for fixed points in general domain.

REFERENCES

• 1: E. Altman, K. Avrachenkov, and C. Barakat. Tcp network calculus: The case of large delay-bandwidth product. In Proceedings of INFOCOM 2002.
• 2: K. Arrow and G. Debreu. Existence of an equilibrium for a competitive economy. Econometrica, 22:265--290, 1954.
• 3: S. Banach. Sur les opérations dans les ensembles abstraits et leur application aux Équations intégrales. Fundamenta Mathematicae, 3:133--181, 1922.
• 4: L. Brouwer. Über abbildung von mannigfaltigkeiten. Mathematische Annalen, 71:97--115, 1910.
• 5: N. Chen, X. Deng, X. Sun, and A. C.-C. Yao. Fisher equilibrium price with a class of concave utility functions. In ESA 2004, pages 169--179.
• 6: B. Codenotti and K. Varadarajan. Efficient computation of equilibrium prices for market with leontief utilities. In To appear in ICALP 2004.
• 7: Richard Cole , Yevgeniy Dodis , Tim Roughgarden, Pricing network edges for heterogeneous selfish users, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780618]
• 8: Xiaotie Deng , Christos Papadimitriou , Shmuel Safra, On the complexity of equilibria, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509920]
• 9: Xiaotie Deng , Christos Papadimitriou , Shmuel Safra, On the complexity of price equilibria, Journal of Computer and System Sciences, v.67 n.2, p.311-324, September 2003 [doi>10.1016/S0022-0000(03)00011-4]
• 10: Nikhil R. Devanur, The spending constraint model for market equilibrium: algorithmic, existence and uniqueness results, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007431]
• 11: Nikhil R. Devanur , Christos H. Papadimitriou , Amin Saberi , Vijay V. Vazirani, Market Equilibrium via a Primal-Dual-Type Algorithm, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.389-395, November 16-19, 2002
• 12: B. Eaves. Homotopies for computation of fixed points. Mathematical Programming, 3:1--22, 1972.
• 13: M. D. Hirsch , C. H. Papadimitriou, Exponential lower bounds for finding Brouwer fixed points, Journal of Complexity, v.5 n.4, p.379-416, Dec. 1989 [doi>10.1016/0885-064X(89)90017-4]
• 14: Z. Huang , L. Khachiyan , K. Sikorski, Approximating fixed points of weakly contracting mappings, Journal of Complexity, v.15 n.2, p.200-213, June 1999 [doi>10.1006/jcom.1999.0504]
• 15: T. Iimura. A discrete fixed point theorem and its applications. Journal of Mathematical Economics, 39:725--742, 2003.
• 16: T. Iimura, K. Murota, and A. Tamura. Discrete fixed point theorem reconsidered. METR, 9 2004.
• 17: Kamal Jain, A Polynomial Time Algorithm for Computing the Arrow-Debreu Market Equilibrium for Linear Utilities, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.286-294, October 17-19, 2004 [doi>10.1109/FOCS.2004.6]
• 18: K. Jain, M. Mahdian, and A. Saberi. Approximating market equilibria. In RANDOM-APPROX 2003, pages 98--108.
• 19: Kamal Jain , Vijay V. Vazirani , Yinyu Ye, Market equilibria for homothetic, quasi-concave utilities and economies of scale in production, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 20: R. Kellogg, T. Li, and J. Yorke. Constructive proof of the brouwer fixed point theorem and computational results. SIAM J. Numer. Anal., 13:473--483, 1976.
• 21: Ker-I Ko, Computational complexity of fixed points and intersection points, Journal of Complexity, v.11 n.2, p.265-292, June 1995 [doi>10.1006/jcom.1995.1011]
• 22: L. Kronecker. Über systeme von funktionen mehrerer variabeln. Montsh. Berl. Akad. Wiss., pages 159--163, 688--698, 1869.
• 23: H. Kuhn. Simplicial approximation of fixed points. Proceedings of National Academy of Science, USA, 61:1238--1242, 1968.
• 24: Steven H. Low, A duality model of TCP and queue management algorithms, IEEE/ACM Transactions on Networking (TON), v.11 n.4, p.525-536, August 2003 [doi>10.1109/TNET.2003.815297]
• 25: Aranyak Mehta , Scott Shenker , Vijay V. Vazirani, Profit-maximizing multicast pricing by approximating fixed points [Extended Abstract], Proceedings of the 4th ACM conference on Electronic commerce, June 09-12, 2003, San Diego, CA, USA [doi>10.1145/779928.779967]
• 26: G. Meinardus. Invarianz bei linearen approximationen. Arch. Rational. Mech. Anal., 14:301--303, 1963.
• 27: O. Merrill. Applications and Extensions of an Algorithm that Computes Fixed Points of Certain Upper Semi-Continuous Point-to-Set Mappings. Phd thesis, University of Michigan, Annarbor, 1972.
• 28: J. F. Nash. Equilibrium points in n-person games. In Proceedings of NAS, 1950.
• 29: C. Papadimitriou. On graph-theoretic lemmata and complexity classes. In STOC 1990, pages 794--801.
• 30: James M. Ortega , Werner C. Rheinboldt, Iterative solution of nonlinear equations in several variables, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2000
• 31: C. Robinson. Dynamical Systems, Stability, Symbolic Dynamics, and Chaos. CRC Press, 1999.
• 32: H. Scarf. The approximation of fixed points of a continuous mapping. SIAM Journal on Applied Mathematics, 15:997--1007, 1967.
• 33: Spencer Shellman , K. Sikorski, A two-dimensional bisection envelope algorithm for fixed points, Journal of Complexity, v.18 n.2, p.641-659, June 2002 [doi>10.1006/jcom.2001.0606]
• 34: Spencer Shellman , K. Sikorski, Algorithm 825: A deep-cut bisection envelope algorithm for fixed points, ACM Transactions on Mathematical Software (TOMS), v.29 n.3, p.309-325, September 2003 [doi>10.1145/838250.838255]
• 35: Spencer Shellman , K. Sikorski, A recursive algorithm for the infinity-norm fixed point problem, Journal of Complexity, v.19 n.6, p.799-834, December 2003 [doi>10.1016/j.jco.2003.06.001]
• 36: K. Sikorski. Fast algorithms for the computation of fixed points. In R. Milanese and A.Vicino, editors, In Robustness in Identification and Control, pages 49--59. Plenum Press, New York, 1989.
• 37: K. Sikorski , C. W. Tsay , H. Woźniakowski, An ellipsoid algorithm for the computation of fixed points, Journal of Complexity, v.9 n.1, p.181-200, March 1993 [doi>10.1006/jcom.1993.1013]
• 38: K. Sikorski , H. Woźniakowski, Complexity of fixed points, I, Journal of Complexity, v.3 n.4, p.388-405, December 1, 1987 [doi>10.1016/0885-064X(87)90008-2]
• 39: S. Smale. A convergent process of price adjustment process and global newton methods. Journal on Mathematical Economics, 3:107--120, 1976.
• 40: E. Sperner. Neuer beweis fur die invarianz der dimensionszahl und des gebietes. Abhandlungen aus dem Mathematischen Seminar Universitat Hamburg, 6:265--272, 1928.
• 41: D. A. Spielmat, Spectral partitioning works: planar graphs and finite element meshes, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.96, October 14-16, 1996
• 42: Z. Yang. Computing equilibria and fixed points: The solution of nonlinear inequalities. Kluwer Academic Publishers, Dordrecht, 1999.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching; Geometrical problems and computations

General Terms:
Algorithms, Economics, Theory

Keywords:
Lipschitz function, Sperner's lemma, approximate fixed point, fixed point theorem