Single-value combinatorial auctions and implementation in undominated strategies

ABSTRACT

In this paper we are interested in general techniques for designing mechanisms that approximately maximize the social welfare in the presence of selfish rational behavior. We demonstrate our results in the setting of Combinatorial Auctions (CA). Our first main 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 main 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 ZPP=NP). This mechanism is an implementation in undominated strategies, as well as an algorithmic implementation, notions that we justify and are of independent interest.

REFERENCES

• 1: K. Akcoglu, J. Aspens, B. DasGupta, and M. Kao. An opportunity-cost algorithm for combinatorial auctions. In E. J. Kontoghiorghes, B. Rustem, and S. Siokos, editors, Applied Optimization: Computational Methods in Decision-Making, Economics, and Finance. Kluwer Academic, 2002.
• 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: M. Babaioff, R. Lavi, and E. Pavlov. Impersonation-based mechanisms, 2005. Working paper.
• 5: M. Babaioff, R. Lavi, and E. Pavlov. Mechanism design for single-value domains. In AAAI, 2005.
• 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: 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]
• 9: E. H. Clarke. Multipart pricing of public goods. Public Choice, pages 17--33, 1971.
• 10: T. Groves. Incentives in teams. Econometrica, 1973.
• 11: Venkatesan Guruswami , Sanjeev Khanna , Rajmohan Rajaraman , Bruce Shepherd , Mihalis Yannakakis, Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems, Journal of Computer and System Sciences, v.67 n.3, p.473-496, November 2003 [doi>10.1016/S0022-0000(03)00066-7]
• 12: M. O. Jackson. Implementation in undominated strategies: A look at bounded mechanisms. Review of Economic Studies, 1992.
• 13: 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
• 14: 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]
• 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: 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
• 17: Noam Nisan, The Communication Complexity of Approximate Set Packing and Covering, Proceedings of the 29th International Colloquium on Automata, Languages and Programming, p.868-875, July 08-13, 2002
• 18: N. Nisan and A. Ronen. Algorithmic mechanism design. Games and Economic Behavior, 2001.
• 19: Peter Cramton , Yoav Shoham , Richard Steinberg, Combinatorial Auctions, The MIT Press, 2006
• 20: D. Parkes. Iterative combinatorial auctions. In P. Cramton, Y. Shoham, and R. Steinberg, editors, Combinatorial Auctions. The MIT press, 2005.
• 21: W. Vickrey. Counterspeculation, auctions and competitive sealed tenders. Journal of Finance, 1961.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation
          Subjects: Rational approximation

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

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

General Terms:
Algorithms, Theory