On the complexity of equilibria

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On the complexity of equilibria

Full text

Pdf (153 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the thiry-fourth annual ACM symposium on Theory of computing table of contents

Montreal, Quebec, Canada

SESSION: Session 2A table of contents

Pages: 67 - 71

Year of Publication: 2002

ISBN:1-58113-495-9

Authors

Xiaotie Deng	City University of Hong Kong, Hong Kong, China
Christos Papadimitriou	University of California, Berkeley, CA
Shmuel Safra	Tel Aviv University, Israel

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 42, Citation Count: 27

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/509907.509920 What is a DOI?

ABSTRACT

We prove complexity, approximability, and inapproximability results for the problem of finding an exchange equilibrium in markets with indivisible (integer) goods, most notably a polynomial-time algorithm that approximates the market equilibrium arbitrarily closely when the number of goods is bounded and the utilities are linear. We also show a communication complexity lower bound, implying that the ideal informational economy of a market with unique individual optima is unattainable in general.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	K. Arrow, and G. Debreu, "Existence of an Equilibrium for a Competitive Economy", Econometrica, Vol. 22, pp.265--290, 1954.
	2	R. W. Cottle, G. B. Dantzig, "Complementary pivot theory of (MATH)ematical programming", Linear Algebra and Appl. 1 1968 no. 1, 103--125.
	3	J. Jordan, "The Competitive Mechanism is Dimensionally Efficient Uniquely," Journal of Economic Theory, 1982.
	4	D. Gale, "Equilibrium in a discrete exchange economy with money," Internat. J. Game Theory} 13 (1984, no. 1, 61--64.
	5	L. Hurwicz, "On Information Decentralization and Efficiency in Resourse Allocation Mechanism", Studies in (MATH)ematical Economics (S. Reiter, ed.), pp. 238--350, 1986.
	6	D. Kozen, C. Yap, "Algebraic Cell Decomposition in NC (Preliminary Version," Proc.~FOCS 1985, pp. 515--521.
	7	H. W. Lenstra, Jr. "Integer programming with a fixed number of variables," (MATH). Oper. Res.} 8 (1983), no. 4, 538--548.
	8	A. K. Lenstra; H. W. Lenstra, Jr.; L. Lovasz "Factoring polynomials with rational coefficients", (MATH). Ann. 261 (1982), no. 4, 515--534.
	9	N. Nisan, "Communication Complexity of Combinatorial Auctions," manuscript, 2001. "Communication Complexity of Approximate Set Packing and Covering."
	10	N. Nisan and I. Segal, "The Communication Complexity of Efficient Allocation Problems" presented in DIMACS workshop on Computational Issues in Game Theory and Mechanism Design, November 2001.
	11	Christos Papadimitriou, Algorithms, games, and the internet, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.749-753, July 2001, Hersonissos, Greece [doi>10.1145/380752.380883]
	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	C. H. Papadimitriou , M. Yannakakis, On the approximability of trade-offs and optimal access of Web sources, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.86, November 12-14, 2000
	14	H. Scarf, The Computation of Economic Equilibria (with collaboration of T. Hansen, Cowles Foundation Monograph No. 24. New Haven: Yale University Press, 1973.

CITED BY 27

	Georg Gottlob , Gianluigi Greco , Francesco Scarcello, Pure Nash equilibria: hard and easy games, Proceedings of the 9th conference on Theoretical aspects of rationality and knowledge, June 20-22, 2003, Univerity of Indiana, Indiana
	Sándor P. Fekete , Martin Skutella , Gerhard J. Woeginger, The complexity of economic equilibria for house allocation markets, Information Processing Letters, v.88 n.5, p.219-223, 16 December 2003
	Nikhil R. Devanur , Vijay V. Vazirani, Extensions of the spending constraint model: existence and uniqueness of equilibria [Extended Abstract], Proceedings of the 4th ACM conference on Electronic commerce, June 09-12, 2003, San Diego, CA, USA
	Rene Beier , Artur Czumaj , Piotr Krysta , Berthold Vöcking, Computing equilibria for congestion games with (im)perfect information, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
	Rahul Garg , Sanjiv Kapoor, Auction algorithms for market equilibrium, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
	R. J. Lipton , E. Markakis , E. Mossel , A. Saberi, On approximately fair allocations of indivisible goods, Proceedings of the 5th ACM conference on Electronic commerce, May 17-20, 2004, New York, NY, USA
	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
	Ning Chen , Xiaotie Deng , Xiaoming Sun, On complexity of single-minded auction, Journal of Computer and System Sciences, v.69 n.4, p.675-687, December 2004
	Bruno Codenotti , Sriram Pemmaraju , Kasturi Varadarajan, The computation of market equilibria, ACM SIGACT News, v.35 n.4, December 2004
	Éva Tardos, Network games, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, p.341-342, June 13-16, 2004, Chicago, IL, USA
	Christos H. Papadimitriou , Tim Roughgarden, Computing equilibria in multi-player games, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	Xi Chen , Xiaotie Deng, On algorithms for discrete and approximate brouwer fixed points, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	Erik D. Demaine , Mohammad Taghi Hajiaghayi , Uriel Feige , Mohammad R. Salavatipour, Combination can be hard: approximability of the unique coverage problem, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.162-171, January 22-26, 2006, Miami, Florida
	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
	Venkatesan Guruswami , Jason D. Hartline , Anna R. Karlin , David Kempe , Claire Kenyon , Frank McSherry, On profit-maximizing envy-free pricing, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	Bruno Codenotti , Amin Saberi , Kasturi Varadarajan , Yinyu Ye, Leontief economies encode nonzero sum two-player games, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.659-667, January 22-26, 2006, Miami, Florida
	Ning Chen , Xiaotie Deng , Hong Zhu, Combinatorial auction across independent markets [Extended Abstract], Proceedings of the 4th ACM conference on Electronic commerce, June 09-12, 2003, San Diego, CA, USA
	Xi Chen , Xiaotie Deng, Matching algorithmic bounds for finding a Brouwer fixed point, Journal of the ACM (JACM), v.55 n.3, p.1-26, July 2008
	Sanjiv Kapoor , Aranyak Mehta , Vijay Vazirani, An auction-based market equilibrium algorithm for a production model, Theoretical Computer Science, v.378 n.2, p.153-164, June, 2007
	Rahul Garg , Sanjiv Kapoor, Auction Algorithms for Market Equilibrium, Mathematics of Operations Research, v.31 n.4, p.714-729, November 2006
	Fang Wu , Li Zhang, Proportional response dynamics leads to market equilibrium, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA
	Dinesh Garg , Kamal Jain , Kunal Talwar , Vijay V. Vazirani, A primal-dual algorithm for computing Fisher equilibrium in the absence of gross substitutability property, Theoretical Computer Science, v.378 n.2, p.143-152, June, 2007
	Nikhil R. Devanur , Christos H. Papadimitriou , Amin Saberi , Vijay V. Vazirani, Market equilibrium via a primal--dual algorithm for a convex program, Journal of the ACM (JACM), v.55 n.5, p.1-18, October 2008
	Bruno Codenotti , Benton Mccune , Sriram Pemmaraju , Rajiv Raman , Kasturi Varadarajan, An experimental study of different approaches to solve the market equilibrium problem, Journal of Experimental Algorithmics (JEA), 12, June 2008
	Xiaotie Deng , Ye Du, The computation of approximate competitive equilibrium is PPAD-hard, Information Processing Letters, v.108 n.6, p.369-373, November, 2008
	Zhenjie Zhang , Laks V. S. Lakshmanan , Anthony K. H. Tung, On domination game analysis for microeconomic data mining, ACM Transactions on Knowledge Discovery from Data (TKDD), v.2 n.4, p.1-27, January 2009
	Georg Gottlob , Gianluigi Greco , Francesco Scarcello, Pure Nash equilibria: hard and easy games, Journal of Artificial Intelligence Research, v.24 n.1, p.357-406, July 2005