Combinatorial auctions with decreasing marginal utilities

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Combinatorial auctions with decreasing marginal utilities

Full text

Pdf (241 KB)

Source

Electronic Commerce archive
Proceedings of the 3rd ACM conference on Electronic Commerce table of contents

Tampa, Florida, USA

Pages: 18 - 28

Year of Publication: 2001

ISBN:1-58113-387-1

Authors

Benny Lehmann	Digital Fuel
Daniel Lehmann	The Hebrew University of Jerusalem, Israel
Noam Nisan	The Hebrew University of Jerusalem, Israel

Sponsor

SIGEcom: ACM Special Interest Group on Electronic Commerce

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 36, Citation Count: 24

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/501158.501161 What is a DOI?

ABSTRACT

In most of microeconomic theory, consumers are assumed to exhibit decreasing marginal utilities. This paper considers combinatorial auctions among such buyers. The valuations of such buyers are placed within a hierarchy of valuations that exhibit no complementarities, a hierarchy that includes also OR and XOR combinations of singleton valuations, and valuations satisfying the gross substitutes property. While we show that the allocation problem among valuations with decreasing marginal utilities is NP-hard, we present an efficient greedy 2-approximation algorithm for this case. No such approximation algorithm exists in a setting allowing for complementarities. Some results about strategic aspects of combinatorial auctions among players with decreasing marginal utilities are also presented.

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	Lawrence M.Ausubel.An e .cient dynamic auction for heterogeneous commodities..rst draft:5 July 2000,8 September 2000.
	2	Sven de Vries and Rakesh Vohra.Combinatorial auctions:A survey. http://www.kellogg.nwu.edu/faculty/vohra/htm/res.htm, January 2001.
	3	Michael L. Fredman , Robert Endre Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms, Journal of the ACM (JACM), v.34 n.3, p.596-615, July 1987 [doi>10.1145/28869.28874]
	4	Yuzo Fujishima , Kevin Leyton-Brown , Yoav Shoham, Taming the Computational Complexity of Combinatorial Auctions: Optimal and Approximate Approaches, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, p.548-553, July 31-August 06, 1999
	5	Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
	6	Rica Gonen , Daniel Lehmann, Optimal solutions for multi-unit combinatorial auctions: branch and bound heuristics, Proceedings of the 2nd ACM conference on Electronic commerce, p.13-20, October 17-20, 2000, Minneapolis, Minnesota, United States [doi>10.1145/352871.352873]
	7	F.Gul and E.Stacchetti.Walrasian equilibrium with gross substitutes.Journal of Economic Theory , 87:95 -124,1999.
	8	F.Gul and E.Stacchetti.The english auction with di .erentiated commodities.Journal of Economic Theory ,92:66 -95,2000.
	9	A.S.Kelso and V.P.Crawford.Job matching, coalition formation and gross substitutes. Econometrica ,50:1483 -1504,1982.
	10	Daniel Lehmann , Liaden Ita O'Callaghan , Yoav Shoham, Truth revelation in approximately efficient combinatorial auctions, Proceedings of the 1st ACM conference on Electronic commerce, p.96-102, November 03-05, 1999, Denver, Colorado, United States [doi>10.1145/336992.337016]
	11	Daniel Lehmann , Liadan I O''Callaghan , Yoav Shoham, Truth Revelation in Rapid, Approximately Efficient Combinatorial Auctions, Stanford University, Stanford, CA, 1999
	12	Je .rey K.MacKie-Mason and Hal R.Varian. Generalized Vickrey auctions.Working paper,Un.of Michigan,July 1994.
	13	H.Moulin.Axioms of Cooperative Decision Making . Cambridge Universit Press,Cambridge,U.K.,1988.
	14	H.Nara anan.Submodular Functions and Electrical Networks ,volume54of Annals of Discrete Mathematics .North-Holland,1997.
	15	Noam Nisan, Bidding and allocation in combinatorial auctions, Proceedings of the 2nd ACM conference on Electronic commerce, p.1-12, October 17-20, 2000, Minneapolis, Minnesota, United States [doi>10.1145/352871.352872]
	16	Noam Nisan.The Communication Complexit of Combinatorial Auctions.Preprint,2001.Available from http://www.cs.huji.ac.il/~noam/mkts.html.
	17	Michael H. Rothkopf , Aleksandar Pekec , Ronald M. Harstad, Computationally Manageable Combinational Auctions, Management Science, v.44 n.8, p.1131-1147, August 1998 [doi>10.1287/mnsc.44.8.1131]
	18	Yuko Sakurai , Makoto Yokoo , Shigeo Matsubara, A limitation of the generalized Vickrey auction in electronic commerce: robustness against false-name bids, Proceedings of the sixteenth national conference on Artificial intelligence and the eleventh Innovative applications of artificial intelligence conference innovative applications of artificial intelligence, p.86-92, July 18-22, 1999, Orlando, Florida, United States
	19	Tuomas Sandholm, An Algorithm for Optimal Winner Determination in Combinatorial Auctions, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, p.542-547, July 31-August 06, 1999
	20	Tuomas Sandholm, An Algorithm for Optimal Winner Determination in Combinatorial Auctions, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, p.542-547, July 31-August 06, 1999
	21	Robert Endre Tarjan, Data structures and network algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983
	22	Moshe Tennenholtz.Some tractable combinatorial auctions.Unpublished draft:January 2000.
	23	Hal R.Varian.Economic mechanism design for computerized agents.In Proceedings of the First Usenix Conference on Electronic Commerce ,New York,July 1995.
	24	William S.Vickrey.Counterspeculation,auctions and competitive sealed tenders.Journal of Finance , 16:8 -37,1961.
	25	Makoto Yokoo , Yuko Sakurai , Shigeo Matsubara, The Effect of False-name Declarations in Mechanism Design: Towards Collective Decision Making on the Internet, Proceedings of the The 20th International Conference on Distributed Computing Systems ( ICDCS 2000), p.146, April 10-13, 2000
	26	Makoto Yokoo , Yuko Sakurai , Shigeo Matsubara, Robust Combinatorial Auction Protocol against False-Name Bids, Proceedings of the Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on Innovative Applications of Artificial Intelligence, p.110-115, July 30-August 03, 2000
	27	Robust Double Auction Protocol against False-Name Bids, Proceedings of the The 21st International Conference on Distributed Computing Systems, p.137, April 16-19, 2001

CITED BY 24

	Daniel Lehmann , Liadan Ita Oćallaghan , Yoav Shoham, Truth revelation in approximately efficient combinatorial auctions, Journal of the ACM (JACM), v.49 n.5, p.577-602, September 2002
	Yair Bartal , Rica Gonen , Noam Nisan, Incentive compatible multi unit combinatorial auctions, Proceedings of the 9th conference on Theoretical aspects of rationality and knowledge, June 20-22, 2003, Univerity of Indiana, Indiana
	Meir Bing , Daniel Lehmann , Paul Milgrom, Presentation and structure of substitutes valuations, Proceedings of the 5th ACM conference on Electronic commerce, May 17-20, 2004, New York, NY, 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
	Shahar Dobzinski , Noam Nisan , Michael Schapira, Approximation algorithms for combinatorial auctions with complement-free bidders, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	Ron Lavi , Noam Nisan, Online ascending auctions for gradually expiring items, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	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
	Shahar Dobzinski , Michael Schapira, An improved approximation algorithm for combinatorial auctions with submodular bidders, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1064-1073, January 22-26, 2006, Miami, Florida
	Shahar Dobzinski , Noam Nisan , Michael Schapira, Truthful randomized mechanisms for combinatorial auctions, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
	Nir Andelman , Yishay Mansour, A sufficient condition for truthfulness with single parameter agents, Proceedings of the 7th ACM conference on Electronic commerce, p.8-17, June 11-15, 2006, Ann Arbor, Michigan, USA
	Liad Blumrosen , Shahar Dobzinski, Welfare maximization in congestion games, Proceedings of the 7th ACM conference on Electronic commerce, p.52-61, June 11-15, 2006, Ann Arbor, Michigan, USA
	Uriel Feige, On maximizing welfare when utility functions are subadditive, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
	Shahar Dobzinski , Noam Nisan, Limitations of VCG-based mechanisms, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA
	Aranyak Mehta , Amin Saberi , Umesh Vazirani , Vijay Vazirani, AdWords and generalized online matching, Journal of the ACM (JACM), v.54 n.5, p.22-es, October 2007
	Jan Vondrak, Optimal approximation for the submodular welfare problem in the value oracle model, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada
	Eugene Fink , Josh Johnson , Jenny Hu, Exchange Market for Complex Goods: Theory and Experiments, Netnomics, v.6 n.1, p.21-42, April 2004
	Vahab Mirrokni , Michael Schapira , Jan Vondrak, Tight information-theoretic lower bounds for welfare maximization in combinatorial auctions, Proceedings of the 9th ACM conference on Electronic commerce, July 08-12, 2008, Chicago, Il, USA
	Mohammad Ghodsi , Hamid Mahini , Vahab S. Mirrokni , Morteza ZadiMoghaddam, Permutation betting markets: singleton betting with extra information, Proceedings of the 9th ACM conference on Electronic commerce, July 08-12, 2008, Chicago, Il, USA
	Ureil Feige , Nicole Immorlica , Vahab Mirrokni , Hamid Nazerzadeh, A combinatorial allocation mechanism with penalties for banner advertising, Proceeding of the 17th international conference on World Wide Web, April 21-25, 2008, Beijing, China
	Benjamin Birnbaum , Claire Mathieu, On-line bipartite matching made simple, ACM SIGACT News, v.39 n.1, March 2008
	Gagan Goel , Aranyak Mehta, Online budgeted matching in random input models with applications to Adwords, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.982-991, January 20-22, 2008, San Francisco, California
	Azarakhsh Malekian , Chi-Chao Chang , Ravi Kumar , Grant Wang, Optimizing query rewrites for keyword-based advertising, Proceedings of the 9th ACM conference on Electronic commerce, July 08-12, 2008, Chicago, Il, USA
	Mokshay Madiman, Cores of cooperative games in information theory, EURASIP Journal on Wireless Communications and Networking, v.2008 n.4, p.1-12, January 2008
	Eugene Fink , Jianli Gong , Josh Johnson, Exchange market for complex commodities: search for optimal matches, Journal of Experimental & Theoretical Artificial Intelligence, v.19 n.2, p.91-117, June 2007