Self-interested automated mechanism design and implications for optimal combinatorial auctions

ABSTRACT

Often, an outcome must be chosen on the basis of the preferences reported by a group of agents. The key difficulty is that the agents may report their preferences insincerely to make the chosen outcome more favorable to themselves. Mechanism design is the art of designing the rules of the game so that the agents are motivated to report their preferences truthfully, and a desirable outcome is chosen. In a recently proposed approach---called automated mechanism design ---a mechanism is computed for the preference aggregation setting at hand. This has several advantages, but the downside is that the mechanism design optimization problem needs to be solved anew each time. Unlike the earlier work on automated mechanism design that studied a benevolent designer, in this paper we study automated mechanism design problems where the designer is self-interested. In this case, the center cares only about which outcome is chosen and what payments are made to it. The reason that the agents' preferences are relevant is that the center is constrained to making each agent at least as well off as the agent would have been had it not participated in the mechanism. In this setting, we show that designing optimal deterministic mechanisms is NP-complete in two important special cases: when the center is interested only in the payments made to it, and when payments are not possible and the center is interested only in the outcome chosen. We then show how allowing for randomization in the mechanism makes problems in this setting computationally easy. Finally, we show that the payment-maximizing AMD problem is closely related to an interesting variant of the optimal (revenue-maximizing) combinatorial auction design problem, where the bidders have "best-only" preferences. We show that here, too, designing an optimal deterministic auction is NP-complete, but designing an optimal randomized auction is easy.

REFERENCES

• 1: M. Armstrong. Optimal multi-object auctions. Review of Economic Studies, 67:455--481, 2000.
• 2: K. Arrow. The property rights doctrine and demand revelation under incomplete information. In M. Boskin, editor, Economics and human welfare. New York Academic Press, 1979.
• 3: C. Avery and T. Hendershott. Bundling and optimal auctions of multiple products. Review of Economic Studies, 67:483--497, 2000.
• 4: E. H. Clarke. Multipart pricing of public goods. Public Choice, 11:17--33, 1971.
• 5: V. Conitzer and T. Sandholm. Complexity of mechanism design. In Proceedings of the 18th Annual Conference on Uncertainty in Artificial Intelligence (UAI-02), pages 103--110, Edmonton, Canada, 2002.
• 6: Vincent Conitzer , Tuomas Sandholm, Automated mechanism design: complexity results stemming from the single-agent setting, Proceedings of the 5th international conference on Electronic commerce, p.17-24, September 30-October 03, 2003, Pittsburgh, Pennsylvania [doi>10.1145/948005.948008]
• 7: 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 [doi>10.1145/988772.988824]
• 8: C. d'Aspremont and L. A. Gérard-Varet. Incentives and incomplete information. Journal of Public Economics, 11:25--45, 1979.
• 9: Joan Feigenbaum , Christos H. Papadimitriou , Scott Shenker, Sharing the cost of multicast transmissions, Journal of Computer and System Sciences, v.63 n.1, p.21-41, August 2001 [doi>10.1006/jcss.2001.1754]
• 10: A. Gibbard. Manipulation of voting schemes. Econometrica, 41:587--602, 1973.
• 11: T. Groves. Incentives in teams. Econometrica, 41:617--631, 1973.
• 12: J. Hershberger , S. Suri, Vickrey Prices and Shortest Paths: What is an Edge Worth?, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.252, October 14-17, 2001
• 13: L. Khachiyan. A polynomial algorithm in linear programming. Soviet Math. Doklady, 20:191--194, 1979.
• 14: Rajeev Kohli , Ramesh Krishnamurti , Prakash Mirchandani, The Minimum Satisfiability Problem, SIAM Journal on Discrete Mathematics, v.7 n.2, p.275-283, May 1994 [doi>10.1137/S0895480191220836]
• 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: A. Mas-Colell, M. Whinston, and J. R. Green. Microeconomic Theory. Oxford University Press, 1995.
• 17: E. S. Maskin and J. Riley. Optimal multi-unit auctions. In F. Hahn, editor, The Economics of Missing Markets, Information, and Games, chapter~14, pages 312--335. Clarendon Press, Oxford, 1989.
• 18: R. Myerson. Optimal auction design. Mathematics of Operation Research, 6:58--73, 1981.
• 19: 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]
• 20: 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]
• 21: T. Roughgarden, Designing Networks for Selfish Users is Hard, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.472, October 14-17, 2001
• 22: T. Sandholm. Issues in computational Vickrey auctions. International Journal of Electronic Commerce, 4(3):107--129, 2000. Special Issue on Applying Intelligent Agents for Electronic Commerce. A short, early version appeared at the Second International Conference on Multi--Agent Systems (ICMAS), pages 299--306, 1996.
• 23: M. A. Satterthwaite. Strategy-proofness and Arrow's conditions: existence and correspondence theorems for voting procedures and social welfare functions. Journal of Economic Theory, 10:187--217, 1975.
• 24: W. Vickrey. Counterspeculation, auctions, and competitive sealed tenders. Journal of Finance, 16:8--37, 1961.
• 25: R. V. Vohra. Research problems in combinatorial auctions. Mimeo, version Oct. 29, 2001.

INDEX TERMS

Primary Classification:
  J. Computer Applications
  J.4 SOCIAL AND BEHAVIORAL SCIENCES
      Subjects: Economics

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

General Terms:
Algorithms, Economics, Theory

Keywords:
automated mechanism design, combinatorial auctions, revenue maximization