An approximate truthful mechanism for combinatorial auctions with single parameter agents

ABSTRACT

Mechanism design seeks algorithms whose inputs are provided by selfish agents who would lie if advantageous. Incentive compatible mechanisms compel the agents to tell the truth by making it in their self-interest to do so. Often, as in combinatorial auctions, such mechanisms involve the solution of NP-hard problems. Unfortunately, approximation algorithms typically destroy incentive compatibility. Randomized rounding is a commonly used technique for designing approximation algorithms. We devise a version of randomized rounding that is incentive compatible, giving a truthful mechanism for combinatorial auctions with single parameter agents (e.g., "single minded bidders") that approximately maximizes the social value of the auction. We discuss two orthogonal notions of truthfulness for a randomized mechanism, truthfulness with high probability and in expectation, and give a mechanism that achieves both simultaneously.We consider combinatorial auctions where multiple copies of many different items are on sale, and each bidder i desires a subset Si. Given a set of bids, the problem of finding the allocation of items that maximizes total valuation is the well-known SETPACKING problem. This problem is NP-hard, but for the case of items with many identical copies the optimum can be approximated very well. To turn this approximation algorithm into a truthful auction mechanism we overcome two problems: we show how to make the allocation algorithm monotone, and give a method to compute the appropriate payments efficiently.

REFERENCES

• 1: 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
• 2: Aaron Archer , Éva Tardos, Frugal path mechanisms, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.991-999, January 06-08, 2002, San Francisco, California
• 3: Ziv Bar-Yossef , Kirsten Hildrum , Felix Wu, Incentive-compatible online auctions for digital goods, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.964-970, January 06-08, 2002, San Francisco, California
• 4: E. H. Clarke. Multipart pricing of public goods. Public Choice, 8:17--33, 1971.
• 5: P. Cramton. Spectrum auctions. In M. Cave, S. Majumdar, and I. Vogelsang, editors, Handbook of Telecommunications Economics. Elsevier, Amsterdam, 2002.
• 6: Amos Fiat , Andrew V. Goldberg , Jason D. Hartline , Anna R. Karlin, Competitive generalized auctions, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509921]
• 7: Andrew V. Goldberg , Jason D. Hartline , Andrew Wright, Competitive auctions and digital goods, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.735-744, January 07-09, 2001, Washington, D.C., United States
• 8: A. V. Goldberg and J. D. Hartline. Competitive auctions for multicast content. Unpublished manuscript, 2000.
• 9: T. Groves. Incentives in teams. Econometrica, 41(4):617--631, Jul 1973.
• 10: Ron Lavi , Noam Nisan, Competitive analysis of incentive compatible on-line auctions, Proceedings of the 2nd ACM conference on Electronic commerce, p.233-241, October 17-20, 2000, Minneapolis, Minnesota, United States [doi>10.1145/352871.352897]
• 11: 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]
• 12: 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
• 13: Noam Nisan , Amir Ronen, Algorithmic mechanism design (extended abstract), Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.129-140, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301287]
• 14: 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]
• 15: Prabhakar Raghavan, Probabilistic construction of deterministic algorithms: approximating packing integer programs, Journal of Computer and System Sciences, v.37 n.2, p.130-143, October 1988 [doi>10.1016/0022-0000(88)90003-7]
• 16: Amir Ronen, Algorithms for Rational Agents, Proceedings of the 27th Conference on Current Trends in Theory and Practice of Informatics, p.56-70, November 25-December 02, 2000
• 17: J. Schummer. Almost-dominant strategy implementation. Unpublished manuscript, 2001.
• 18: W. Vickrey. Counterspeculation, auctions and competitive sealed tenders. J. Finance, 16:8--37, 1961.

INDEX TERMS

Primary Classification:
  K. Computing Milieux
  K.4 COMPUTERS AND SOCIETY
      K.4.4 Electronic Commerce

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms

General Terms:
Algorithms, Theory