Single-value combinatorial auctions and algorithmic implementation in undominated strategies

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Single-value combinatorial auctions and algorithmic implementation in undominated strategies

Full text

Pdf (326 KB)

Source

Journal of the ACM (JACM) archive
Volume 56 , Issue 1 (January 2009) table of contents

Article No. 4

Year of Publication: 2009

ISSN:0004-5411

Authors

Moshe Babaioff	Microsoft Research -- Silicon Valley, Mountain View, California
Ron Lavi	The Technion -- Israel Institute of Technology, Haifa, Israel
Elan Pavlov	Massachusetts Institute of Technology, Cambridge, Massachusetts

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 26, Downloads (12 Months): 296, Citation Count: 0

Additional Information:

abstract references 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/1462153.1462157 What is a DOI?

ABSTRACT

In this article, we are interested in general techniques for designing mechanisms that approximate the social welfare in the presence of selfish rational behavior. We demonstrate our results in the setting of Combinatorial Auctions (CA). Our first result is a general deterministic technique to decouple the algorithmic allocation problem from the strategic aspects, by a procedure that converts any algorithm to a dominant-strategy ascending mechanism. This technique works for any single value domain, in which each agent has the same value for each desired outcome, and this value is the only private information. In particular, for “single-value CAs”, where each player desires any one of several different bundles but has the same value for each of them, our technique converts any approximation algorithm to a dominant strategy mechanism that almost preserves the original approximation ratio. Our second result provides the first computationally efficient deterministic mechanism for the case of single-value multi-minded bidders (with private value and private desired bundles). The mechanism achieves an approximation to the social welfare which is close to the best possible in polynomial time (unless P=NP). This mechanism is an algorithmic implementation in undominated strategies, a notion that we define and justify, and is of independent interest.

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	Akcoglu, K., Aspens, J., DasGupta, B., and Kao, M. 2002. An opportunity-cost algorithm for combinatorial auctions. In Applied Optimization: Computational Methods in Decision-Making, Economics, and Finance, E. J. Kontoghiorghes, B. Rustem, and S. Siokos, Eds. Kluwer Academic.
	2	A. Archer , É. Tardos, Truthful Mechanisms for One-Parameter Agents, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.482, October 14-17, 2001
	3	Baruch Awerbuch , Yossi Azar , Adam Meyerson, Reducing truth-telling online mechanisms to online optimization, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780616]
	4	Babaioff, M., Lavi, R., and Pavlov, E. 2005. Mechanism design for single-value domains. In Proceedings of the National Conference on Artificial Intelligence (AAAI), 241--247.
	5	Babaioff, M., Lavi, R., and Pavlov, E. 2006. Impersonation-based mechanisms. In Proceedings of the National Conference on Artificial Intelligence (AAAI).
	6	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 [doi>10.1145/846241.846250]
	7	Liad Blumrosen , Noam Nisan, On the computational power of iterative auctions, Proceedings of the 6th ACM conference on Electronic commerce, p.29-43, June 05-08, 2005, Vancouver, BC, Canada [doi>10.1145/1064009.1064013]
	8	Blumrosen, L., and Nisan, N. 2007. Combinatorial auctions. In Algorithmic Game Theory, N. Nisan, T. Roughgarden, E. Tardos, and V. Vazirani, Eds. Cambridge University press, Cambridge, UK.
	9	Patrick Briest , Piotr Krysta , Berthold Vöcking, Approximation techniques for utilitarian mechanism design, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060597]
	10	Clarke, E. H. 1971. Multipart pricing of public goods. Public Choice, 17--33.
	11	Peter Cramton , Yoav Shoham , Richard Steinberg, Combinatorial Auctions, The MIT Press, 2006
	12	Shahar Dobzinski, Two Randomized Mechanisms for Combinatorial Auctions, Proceedings of the 10th International Workshop on Approximation and the 11th International Workshop on Randomization, and Combinatorial Optimization. Algorithms and Techniques, August 20-22, 2007, Princeton, NJ, USA [doi>10.1007/978-3-540-74208-1_7]
	13	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 [doi>10.1145/1250790.1250842]
	14	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 [doi>10.1145/1060590.1060681]
	15	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 [doi>10.1145/1132516.1132607]
	16	Shahar Dobzinski , Mukund Sundararajan, On characterizations of truthful mechanisms for combinatorial auctions and scheduling, Proceedings of the 9th ACM conference on Electronic commerce, July 08-12, 2008, Chicago, Il, USA [doi>10.1145/1386790.1386798]
	17	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
	18	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]
	19	Groves, T. 1973. Incentives in teams. Econometrica, 617--631.
	20	Holzman, R., Kfir-Dahav, N., Monderer, D., and Tennenholtz, M. 2004. Bundling equilibrium in combinatorial auctions. Games Econ. Beh. 47, 104--123.
	21	Jackson, M. O. 1992. Implementation in undominated strategies: A look at bounded mechanisms. Rev. Econ. Stud.
	22	Ron Lavi , Ahuva Mu'alem , Noam Nisan, Towards a Characterization of Truthful Combinatorial Auctions, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.574, October 11-14, 2003
	23	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
	24	Ron Lavi , Chaitanya Swamy, Truthful and Near-Optimal Mechanism Design via Linear Programming, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.595-604, October 23-25, 2005 [doi>10.1109/SFCS.2005.76]
	25	Ron Lavi , Chaitanya Swamy, Truthful mechanism design for multi-dimensional scheduling via cycle monotonicity, Proceedings of the 8th ACM conference on Electronic commerce, June 11-15, 2007, San Diego, California, USA [doi>10.1145/1250910.1250947]
	26	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 [doi>10.1145/585265.585266]
	27	Ahuva Mu'alem , Noam Nisan, Truthful approximation mechanisms for restricted combinatorial auctions: extended abstract, Eighteenth national conference on Artificial intelligence, p.379-384, July 28-August 01, 2002, Edmonton, Alberta, Canada
	28	Nisan, N., and Ronen, A. 2001. Algorithmic mechanism design. Games Econom. Behav. 35, 166--196.
	29	Nisan, N., and Segal, I. 2006. The communication requirements of efficient allocations and supporting prices. J. Econ. Theory.
	30	Edo Zurel , Noam Nisan, An efficient approximate allocation algorithm for combinatorial auctions, Proceedings of the 3rd ACM conference on Electronic Commerce, p.125-136, October 14-17, 2001, Tampa, Florida, USA [doi>10.1145/501158.501172]
	31	Parkes, D. 2005. Iterative combinatorial auctions. In Combinatorial Auctions, P. Cramton, Y. Shoham, and R. Steinberg, Eds. MIT press, Cambridge, MA.
	32	Sandholm, T., Suri, S., Gilpin, A., and Levine, D. 2005. Cabob: A fast optimal algorithm for winner determination in combinatorial auctions. Manage. Sci. 51, 3, 374--390.
	33	Vickrey, W. 1961. Counterspeculation, auctions and competitive sealed tenders. J. Finance 16, 1, 8--37.
	34	David Zuckerman, Linear degree extractors and the inapproximability of max clique and chromatic number, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132612]