Towards a combinatorial auction protocol among experts and amateurs: the case of single-skilled experts

ABSTRACT

Auctions have recently commanded a great deal of attention in the field of multi-agent systems. Correctly judging the quality of auctioned goods is often difficult for amateurs, in particular, on the Internet auctions. We have formalized such a situation so that Nature selects the quality of the auctioned good. Experts can observe Nature's selection (i.e., the quality of the good) correctly, while amateurs, including the auctioneer, cannot. In other words, the information on Nature's selection is asymmetric between experts and amateurs. In this situation, it is difficult to attain an efficient allocation, since experts have a clear advantage over amateurs, and they would not reveal their valuable information without some reward. Thus, we have succeeded in developing a single unit auction protocol in which truth telling is a dominant strategy for each expert. In this paper, we focus on a combinatorial auction protocol under asymmetric information on Nature's selection. Experts may have an interest in, and expert knowledge on, Nature's selection for several goods, i.e., experts are versatile. However, the case of versatile experts is very complicated. Thus, as a first step, we assume experts to have an interest in, and expert knowledge on, a single good. That is, experts are single-skilled. Under these assumptions, we develop an auction protocol in which the dominant strategy for experts is truth telling. Also, for amateurs, truth-telling is the best response when experts tell the truth. By making experts to elicit their information on the quality of the goods, the protocol can achieve a Pareto efficient allocation, if certain assumptions are satisfied.

REFERENCES

• 1: Craig Boutilier , Moisés Goldszmidt , Bikash Sabata, Sequential Auctions for the Allocation of Resources with Complementarities, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, p.527-523, July 31-August 06, 1999
• 2: Yuzo Fujishima , Kevin Leyton-Brown , Yoav Shoham, Taming the Computational Complexity of Combinatorial Auctions: Optimal and Approximate Approaches, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, p.548-553, July 31-August 06, 1999
• 3: Robert H. Guttman , Alexandros G. Moukas , Pattie Maes, Agent-mediated electronic commerce: a survey, The Knowledge Engineering Review, v.13 n.2, p.147-159, July 1998 [doi>10.1017/S0269888998002082]
• 4: Benoît Hudson , Tuomas Sandholm, Effectiveness of Preference Elicitation in Combinatorial Auctions, Revised Papers from the Workshop on Agent Mediated Electronic Commerce on Agent-Mediated Electronic Commerce IV, Designing Mechanisms and Systems, p.69-86, July 16, 2002
• 5: A Combinatorial Auction for Collaborative Planning, Proceedings of the Fourth International Conference on MultiAgent Systems (ICMAS-2000), p.151, July 10-12, 2000
• 6: Takayuki Ito , Makoto Yokoo , Shigeo Matsubara, Designing an auction protocol under asymmetric information on nature's selection, Proceedings of the first international joint conference on Autonomous agents and multiagent systems: part 1, July 15-19, 2002, Bologna, Italy [doi>10.1145/544741.544759]
• 7: Cuihong Li , Katia Sycara, Algorithm for combinatorial coalition formation and payoff division in an electronic marketplace, Proceedings of the first international joint conference on Autonomous agents and multiagent systems: part 1, July 15-19, 2002, Bologna, Italy [doi>10.1145/544741.544771]
• 8: A. Mas-Colell, M. D. Whinston, and J. R. Green. Microeconomic Theory. Oxford University Press, 2nd edition, 1995.
• 9: E. Rasmusen. Games and Information. Blackwell Publishers Ltd, 2nd edition, 1994.
• 10: Tuomas Sandholm, An Algorithm for Optimal Winner Determination in Combinatorial Auctions, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, p.542-547, July 31-August 06, 1999
• 11: Tuomas Sandholm, eMediator: a next generation electronic commerce server, Proceedings of the fourth international conference on Autonomous agents, p.341-348, June 03-07, 2000, Barcelona, Spain [doi>10.1145/336595.337522]
• 12: Tuomas Sandholm , Subhash Suri, Improved Algorithms for Optimal Winner Determination in Combinatorial Auctions and Generalizations, Proceedings of the Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on Innovative Applications of Artificial Intelligence, p.90-97, July 30-August 03, 2000
• 13: Tuomas Sandholm , Subhash Suri , Andrew Gilpin , David Levine, Winner determination in combinatorial auction generalizations, Proceedings of the first international joint conference on Autonomous agents and multiagent systems: part 1, July 15-19, 2002, Bologna, Italy [doi>10.1145/544741.544760]
• 14: H. R. Varian. Economic mechanism design for computerized agents. In Proc. of the First Usenix Workshop on Electronic Commerce, 1995.
• 15: Peter R. Wurman , Michael P. Wellman , William E. Walsh, The Michigan Internet AuctionBot: a configurable auction server for human and software agents, Proceedings of the second international conference on Autonomous agents, p.301-308, May 10-13, 1998, Minneapolis, Minnesota, United States [doi>10.1145/280765.280847]

INDEX TERMS

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

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

General Terms:
Algorithms, Design, Economics, Theory

Keywords:
auctions, mechanism design, multiagent systems