Mechanisms for multi-unit auctions

ABSTRACT

We present an incentive-compatible polynomial-time approximation scheme for multi-unit auctions with general k-minded playervaluations. The mechanism fully optimizes over an appropriately chosen sub-range of possible allocations and then uses VCG payments over this sub-range. We show that obtaining a fully polynomial-time incentive-compatible approximation scheme, at least using VCG payments, is NP-hard. For the case of valuations given by black boxes, we give a polynomial-time incentive-compatible 2-approximation mechanism and show that no better is possible, at least using VCG payments.

REFERENCES

• 1: 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]
• 2: 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]
• 3: Anshul Kothari , David C. Parkes , Subhash Suri, Approximately-strategyproof and tractable multiunit auctions, Decision Support Systems, v.39 n.1, p.105-121, March 2005 [doi>10.1016/j.dss.2004.08.009]
• 4: 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
• 5: 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]
• 6: 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]
• 7: 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
• 8: Noam Nisan. Bidding languages. In P. Cramton, Y. Shoham, and R. Steinberg, editors, Combinatorial Auctions. MIT Press, 2006.
• 9: 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]
• 10: Noam Nisan and Ilya Segal. The communication requirements of efficient allocations and supporting prices, 2006. In the Journal of Economic Theory.
• 11: W. Vickrey. Counterspeculation, auctions and competitive sealed tenders. Journal of Finance, pages 8--37, 1961.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.m Miscellaneous

General Terms:
Theory

Keywords:
combinatorial auctions, incentive compatibility