Approximately-strategyproof and tractable multi-unit auctions

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Approximately-strategyproof and tractable multi-unit auctions

Full text

Pdf (303 KB)

Source

Electronic Commerce archive
Proceedings of the 4th ACM conference on Electronic commerce table of contents

San Diego, CA, USA

Pages: 166 - 175

Year of Publication: 2003

ISBN:1-58113-679-X

Authors

Anshul Kothar	University of California at Santa Barbara, CA
David C. Parke	Harvard University, Cambridge, MA
Subhash Sur	University of California at Santa Barbara, CA

Sponsors

ACM: Association for Computing Machinery
SIGEcom: ACM Special Interest Group on Electronic Commerce

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 18, Citation Count: 11

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

ABSTRACT

We present an approximately-efficient and approximately-strategyproof auction mechanism for a single-good multi-unit allocation problem. The bidding language in our auctions allows marginal-decreasing piecewise constant curves. First, we develop a fully polynomial-time approximation scheme for the multi-unit allocation problem, which computes a (1+ε)≈ in worst-case time T = O(n³/ε), given n bids each with a constant number of pieces. Second, we embed this approximation scheme within a Vickrey-Clarke-Groves (VCG) mechanism and compute payments to n agents for an asymptotic cost of O(T log n). The maximal possible gain from manipulation to a bidder in the combined scheme is bounded by ε/(1+ε) V, where V is the total surplus in the efficient outcome.

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	L. M. Ausubel and P. R. Milgrom. Ascending auctions with package bidding. Frontiers of Theoretical Economics, 1:1--42, 2002.
	2	S. Bikchandani, S. de Vries, J. Schummer, and R. V. Vohra. Linear programming and Vickrey auctions. Technical report, Anderson Graduate School of Management, U.C.L.A., 2001.
	3	S. Bikchandani and J. M. Ostroy. The package assignment model. Journal of Economic Theory, 2002. Forthcoming.
	4	K. Chatterjee and W Samuelson. Bargaining under incomplete information. Operations Research, 31:835--851, 1983.
	5	E. H. Clarke. Multipart pricing of public goods. Public Choice, 11:17--33, 1971.
	6	Sven de Vries , Rakesh V. Vohra, Combinatorial Auctions: A Survey, INFORMS Journal on Computing, v.15 n.3, p.284-309, July 2003 [doi>10.1287/ijoc.15.3.284.16077]
	7	M. Eso, S. Ghosh, J. R. Kalagnanam, and L. Ladanyi. Bid evaluation in procurement auctions with piece-wise linear supply curves. Technical report, IBM TJ Watson Research Center, 2001. in preparation.
	8	Joan Feigenbaum , Scott Shenker, Distributed algorithmic mechanism design: recent results and future directions, Proceedings of the 6th international workshop on Discrete algorithms and methods for mobile computing and communications, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570810.570812]
	9	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
	10	G. V. Gens and E. V. Levner. Computational complexity of approximation algorithms for combinatorial problems. In Mathematical Foundation of Computer Science, 292--300, 1979.
	11	T. Groves. Incentives in teams. Econometrica, 41:617--631, 1973.
	12	Jayant R. Kalagnanam , Andrew J. Davenport , Ho S. Lee, Computational Aspects of Clearing Continuous Call Double Auctions with Assignment Constraints and Indivisible Demand, Electronic Commerce Research, v.1 n.3, p.221-238, July 2001 [doi>10.1023/A:1011589804040]
	13	V. Krishna. Auction Theory. Academic Press, 2002.
	14	V. Krishna and M. Perry. Efficient mechanism design. Technical report, Pennsylvania State University, 1998. Available at: http://econ.la.psu.edu/ vkrishna/vcg18.ps.
	15	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]
	16	R. B. Myerson. Optimal auction design. Mathematics of Operation Research, 6:58--73, 1981.
	17	R. B. Myerson and M. A. Satterthwaite. Efficient mechanisms for bilateral trading. Journal of Economic Theory, 28:265--281, 1983.
	18	Noam Nisan , Amir Ronen, Computationally feasible VCG mechanisms, Proceedings of the 2nd ACM conference on Electronic commerce, p.242-252, October 17-20, 2000, Minneapolis, Minnesota, United States [doi>10.1145/352871.352898]
	19	D. C. Parkes, J. R. Kalagnanam, and M. Eso. Achieving budget-balance with Vickrey-based payment schemes in exchanges. In IJCAI, 2001.
	20	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]
	21	J. Schummer. Almost dominant strategy implementation. Technical report, MEDS Department, Kellogg Graduate School of Management, 2001.
	22	W. Vickrey. Counterspeculation, auctions, and competitive sealed tenders. Journal of Finance, 16:8--37, 1961.

CITED BY 11

	Vincent Conitzer , Tuomas Sandholm, Computational criticisms of the revelation principle, Proceedings of the 5th ACM conference on Electronic commerce, May 17-20, 2004, New York, NY, USA
	Peter Haddawy , Namthip Rujikeadkumjorn , Khaimook Dhananaiyapergse , Christine Cheng, Balanced matching of buyers and sellers in e-marketplaces: the barter trade exchange model, Proceedings of the 6th international conference on Electronic commerce, October 25-27, 2004, Delft, The Netherlands
	Ahuva Mu'alem, On decentralized incentive compatible mechanisms, Proceedings of the 6th ACM conference on Electronic commerce, p.240-248, June 05-08, 2005, Vancouver, BC, Canada
	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
	Terence Kelly, Combinatorial Auctions and Knapsack Problems, Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, p.1280-1281, July 19-23, 2004, New York, New York
	Rajdeep K. Dash , Nicholas R. Jennings , David C. Parkes, Computational-Mechanism Design: A Call to Arms, IEEE Intelligent Systems, v.18 n.6, p.40-47, November 2003
	Xia Zhou , Sorabh Gandhi , Subhash Suri , Haitao Zheng, eBay in the Sky: strategy-proof wireless spectrum auctions, Proceedings of the 14th ACM international conference on Mobile computing and networking, September 14-19, 2008, San Francisco, California, USA
	Takayuki Ito , Makoto Yokoo , Atsushi Iwasaki , Shigeo Matsubara, A new strategy-proof greedy-allocation combinatorial auction protocol and its extension to open ascending auction protocol, Proceedings of the 20th national conference on Artificial intelligence, p.261-266, July 09-13, 2005, Pittsburgh, Pennsylvania
	Tuomas Sandholm, Expressive commerce and its application to sourcing, Proceedings of the 18th conference on Innovative applications of artificial intelligence, p.1736-1743, July 16-20, 2006, Boston, Massachusetts
	R. Mohammad Ebrahim , J. Razmi , H. Haleh, Scatter search algorithm for supplier selection and order lot sizing under multiple price discount environment, Advances in Engineering Software, v.40 n.9, p.766-776, September, 2009
	Vincent Conitzer , Tuomas Sandholm, Incremental mechanism design, Proceedings of the 20th international joint conference on Artifical intelligence, p.1251-1256, January 06-12, 2007, Hyderabad, India