Mechanism design and deliberative agents

ABSTRACT

The central mechanism design problem is to develop incentives for agents to truthfully reveal their preferences over different outcomes, so that the system-wide outcome chosen by the mechanism appropriately reflects these preferences. However, in many settings, agents' do not know their actual preferences a priori. Instead, an agent may need to compute or gather information to determine whether they prefer one possible outcome over another. Due to time constraints or the cost of acquiring information, agents must be deliberative in that they need to carefully decide how to allocate their computational or information gathering resources when determining their preferences. In this paper we study the problem of designing mechanisms explicitly for deliberative agents. We propose a set of intuitive properties which we argue are desirable in deliberative-agent settings. We show that these properties are mutually incompatible, and that many approaches to mechanism design are not robust against undesirable behavior from deliberative agents.

REFERENCES

• 1: Dirk Bergemann and Juuso Välimäki. Information acquisition and efficient mechanism design. Econometrica, 70:1007--1034, 2002.
• 2: Olivier Compte and Philippe Jehiel. Auctions and information acquisition: Sealed-bid or dynamic formats? 2001. Working Paper.
• 3: 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]
• 4: Jacques Cremer, Yossi Spiegel, and Charles Zheng. Optimal selling mechanisms with costly information acquisition. Working paper, August 2003.
• 5: Takayuki Ito , Makoto Yokoo , Shigeo Matsubara, Towards a combinatorial auction protocol among experts and amateurs: the case of single-skilled experts, Proceedings of the second international joint conference on Autonomous agents and multiagent systems, July 14-18, 2003, Melbourne, Australia [doi>10.1145/860575.860652]
• 6: Mechanism Design for Resource Bounded Agents, Proceedings of the Fourth International Conference on MultiAgent Systems (ICMAS-2000), p.309, July 10-12, 2000
• 7: Kate Larson , Tuomas Sandholm, Bargaining with limited computation: deliberation equilibrium, Artificial Intelligence, v.132 n.2, p.183-217, November 2001 [doi>10.1016/S0004-3702(01)00132-1]
• 8: Kate Larson , Tuomas Sandholm, Costly valuation computation in auctions, Proceedings of the 8th conference on Theoretical aspects of rationality and knowledge, July 08-10, 2001, Siena, Italy
• 9: Kate Larson , Tuomas Sandholm, Experiments on Deliberation Equilibria in Auctions, Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, p.394-401, July 19-23, 2004, New York, New York [doi>10.1109/AAMAS.2004.120]
• 10: 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]
• 11: Andreu Mas-Colell, Michael Whinston, and Jerry R. Green. Microeconomic Theory. Oxford University Press, 1995.
• 12: 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]
• 13: David C. Parkes. Optimal auction design for agents with hard valuation problems. In Agent-Mediated Electronic Commerce Workshop at the International Joint Conference on Artificial Intelligence, Stockholm, Sweden, 1999.
• 14: Nicola Perisco. Information acquisition in auctions. Econometrica, 68(1):135--148, January 2000.
• 15: Tuomas 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.
• 16: Martin Weitzman. Optimal search for the best alternative. Econometrica, 47(3):641--654, 1979.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Multiagent systems

General Terms:
Design, Theory

Keywords:
game Theory, mechanism design, resource-bounded agents