Matching algorithmic bounds for finding a Brouwer fixed point

ABSTRACT

We prove a new discrete fixed point theorem for direction-preserving functions defined on integer points, based on a novel characterization of boundary conditions for the existence of fixed points. The theorem allows us to derive an improved algorithm for finding such a fixed point. We also develop a new lower bound proof technique. Together, they allow us to derive an asymptotic matching bound for the problem of finding a fixed point in a hypercube of any constantly bounded finite dimension.

Exploring a linkage with the approximation version of the continuous fixed point problem, we obtain asymptotic matching bounds for the complexity of the approximate Brouwer fixed point problem in the continuous case for Lipschitz functions. It settles a fifteen-years-old open problem of Hirsch, Papadimitriou, and Vavasis by improving both the upper and lower bounds.

Our characterization for the existence of a fixed point is also applicable to functions defined on nonconvex domains, which makes it a potentially useful tool for the design and analysis of algorithms for fixed points in general domains.

REFERENCES

• 1: Altman, E., Avrachenkov, K., and Barakat, C. 2002. Tcp network calculus: The case of large delay-bandwidth product. In Proceedings of the 21st Annual Joint Conference of the IEEE Computer and Communications Societies. IEEE, Computer Society Press, Los Alamitos, CA, 417--426.
• 2: Arrow, K., and Debreu, G. 1954. Existence of an equilibrium for a competitive economy. Econometrica 22, 265--290.
• 3: Banach, S. 1922. Sur les opérations dans les ensembles abstraits et leur application aux Équations intégrales. Fund. Math. 3, 133--181.
• 4: Brouwer, L. 1910. Über abbildung von mannigfaltigkeiten. Math. Ann. 71, 97--115.
• 5: Chen, N., Deng, X., Sun, X., and Yao, A. C.-C. 2004. Fisher equilibrium price with a class of concave utility functions. In Proceedings of the 12th Annual European Symposium on Algorithms. Springer-Verlag, New York, 169--179.
• 6: Chen, X., Sun, X., and Teng, S.-H. 2008. Quantum separation of local search and fixed point computation. In Proceedings of the 14th Annual International Computing and Combinatorics Conference. Springer-Verlag, New York, 169--178.
• 7: Xi Chen , Shang-Hua Teng, Paths Beyond Local Search: A Tight Bound for Randomized Fixed-Point Computation, Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, p.124-134, October 21-23, 2007 [doi>10.1109/FOCS.2007.53]
• 8: Codenotti, B., and Varadarajan, K. 2004. Efficient computation of equilibrium prices for markets with Leontief utilities. In Proceedings of the 31st International Colloquium on Automata, Languages and Programming. Springer-Verlag, New York, 371--382.
• 9: 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]
• 10: 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]
• 11: 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]
• 12: 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]
• 13: 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
• 14: Eaves, B. 1972. Homotopies for computation of fixed points. Math. Prog. 3, 1--22.
• 15: 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]
• 16: 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]
• 17: Iimura, T. 2003. A discrete fixed point theorem and its applications. J. Math. Econ. 39, 7, 725--742.
• 18: Iimura, T., Murota, K., and Tamura, A. 2005. Discrete fixed point theorem reconsidered. J. Math. Econ. 41, 8, 1030--1036.
• 19: 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, p.286-294, October 17-19, 2004 [doi>10.1109/FOCS.2004.6]
• 20: Jain, K., Mahdian, M., and Saberi, A. 2003. Approximating market equilibria. In Proceedings of the 6th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems and the 7th International Workshop on Randomization and Approximation Techniques in Computer Science. Springer-Verlag, New York, 861--869.
• 21: 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
• 22: Kellogg, R., Li, T., and Yorke, J. 1976. Constructive proof of the Brouwer fixed point theorem and computational results. SIAM J. Numer. Anal. 13, 473--483.
• 23: 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]
• 24: Kronecker, L. 1869. Über systeme von funktionen mehrerer variabeln. Monatsber. Berlin Akad., 159--193 and 688--698.
• 25: Kuhn, H. 1968. Simplicial approximation of fixed points. Proc. Nat. Acad. Sci. 61, 1238--1242.
• 26: 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]
• 27: 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]
• 28: Meinardus, G. 1963. Invarianz bei linearen approximationen. Arch. Rational. Mech. Anal. 14, 1, 301--303.
• 29: Merrill, O. 1972. Applications and Extensions of an Algorithm that Computes Fixed Points of Certain Upper Semi-Continuous Point-to-Set Mappings. Ph.d. dissertation, University of Michigan, Ann Arbor, MI.
• 30: Nash, J. F. 1950. Equilibrium points in n-person games. Proc. Nat. Acad. Sci. USA 36, 48--49.
• 31: James M. Ortega , Werner C. Rheinboldt, Iterative solution of nonlinear equations in several variables, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2000
• 32: C. H. Papadimitriou, On graph-theoretic lemmata and complexity classes, Proceedings of the Proceedings [1990] 31st Annual Symposium on Foundations of Computer Science, p.794-801 vol.2, October 22-24, 1990 [doi>10.1109/FSCS.1990.89602]
• 33: Robinson, C. 1999. Dynamical Systems, Stability, Symbolic Dynamics, and Chaos. CRC Press.
• 34: Scarf, H. 1967. The approximation of fixed points of a continuous mapping. SIAM J. Applied Mathematics 15, 997--1007.
• 35: 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]
• 36: 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]
• 37: 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]
• 38: Sikorski, K. 1989. Fast algorithms for the computation of fixed points. In Robustness in Identification and Control, R. Milanese and A. Vicino, Eds. Plenum Press, New York, 49--59.
• 39: 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]
• 40: 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]
• 41: Smale, S. 1976. A convergent process of price adjustment and global newton methods. J. Math. Econ. 3, 2, 107--120.
• 42: Sperner, E. 1928. Neuer beweis fur die invarianz der dimensionszahl und des gebietes. Abhandlungen aus dem Mathematischen Seminar Universitat Hamburg 6, 265--272.
• 43: 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
• 44: Yang, Z. 1999. Computing equilibria and fixed points: The solution of nonlinear inequalities. Kluwer Academic Publishers, Dordrecht.

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: Geometrical problems and computations; Sorting and searching

General Terms:
Algorithms, Economics, Theory

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