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): 0, Downloads (12 Months): 14, Citation Count: 6

Additional Information:

abstract references cited by index terms collaborative colleagues peer to peer

Tools and Actions:	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
	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 6

	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
	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
	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
	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