Auction algorithms for market equilibrium

ABSTRACT

In this paper we study algorithms for computing market equilibrium in markets with linear utility functions. The buyers in the market have an initial endowment given by a portfolio of items. The market equilibrium problem is to compute a price vector which ensures market clearing, i. e. the demand of a good equals its supply, and given the prices, each buyer maximizes its utility. The problem is of considerable interest in Economics. This paper presents a formulation of the market equilibrium problem as a parameterized linear program. We construct the dual of these parametrized linear programs. We show that finding the market equilibrium is the same as finding a linear-program from the family of programs where the optimal dual solution satisfies certain properties. The market clearing conditions arise naturally from complementary slackness conditions.We then define an auction mechanism which computes prices such that approximate market clearing is achieved. The algorithm we obtain outperforms previously known methods.

REFERENCES

• 1: K. Arrow and G. Debreu. Existance of an equilibrium for a competitive economy. Econometrica, 22:265--290, 1954.
• 2: Vipul Bansal , Rahul Garg, Simultaneous Independent Online Auctions with Discrete Bid Increments, Electronic Commerce Research, v.5 n.2, p.181-201, April 2005 [doi>10.1007/s10660-005-6156-1]
• 3: D. P. Bertsekas. Auction Algorithms for Network Flow Problems: A Tutorial Introduction. Computational Optimization and Applications, 1:7--66, 1992.
• 4: W. C. Brainard and H. E. Scarf. How to compute equilibrium prices in 1891. Cowles Foundation Discussion Paper (1272), 2000.
• 5: John Q. Cheng , Michael P. Wellman, The WALRAS Algorithm: A Convergent Distributed Implementation of General Equilibrium Outcomes, Computational Economics, v.12 n.1, p.1-24, August 1998 [doi>10.1023/A:1008654125853]
• 6: G. Demange, D. Gale, and M. Sotomayor. Multi-item Auctions. Journal of Political Economy, 94(4):863--872, 1986.
• 7: 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]
• 8: 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
• 9: N. R. Devanur and V. Vazirani. An improved approximation scheme for computing the arrow-debreu prices for the linear case. In Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2003), 2003.
• 10: K. Jain, M. Mahdian, and A. Saberi. Approximating market equilibrium. In Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX 2003), 2003.
• 11: H. W. Kuhn. The hungarian method for the assignment problem. Naval Research Logistics Quarterly, 2:83--97, 1955.
• 12: Christos H. Papadimitriou, On the complexity of the parity argument and other inefficient proofs of existence, Journal of Computer and System Sciences, v.48 n.3, p.498-532, June 1994 [doi>10.1016/S0022-0000(05)80063-7]
• 13: P. Samuelson. Foundations of economic analysis. Harward University Press, Cambridge, Mass., 1947.
• 14: L. Walras. Elements of pure economics, or the theory of social wealth (in French). Lausanne, Paris, 1874.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

General Terms:
Algorithms, Economics

Keywords:
approximation algorithms, auction algorithms, market equilibrium