Protocols and strategies for automated multi-attribute auctions

ABSTRACT

In this paper, we consider a model of a procurement multi-attribute auction in which the sales item is defined by several attributes, the buyer is the auctioneer, and the sellers are the bidders. Such domains include auctions on task allocation, services, or compound items. The buyer announces a scoring rule, according to its preferences, before the auction starts, and each seller places a bid, which describes the attributes of the item it offers for sale.First, we consider a variation of the first-price sealed-bid protocol, and we provide optimal and stable strategies for the buyer agent and for the seller agents participating in the multi-attribute auction. In addition, we analyze the buyer's expected revenue and suggest an optimal scoring rule that can be announced. Second, we consider four variations of the English auction for the case of a multi-attribute item, and we prove that, given some assumptions, they all converge to the same result. We also discuss which variation is preferred for different types of environments. Moreover, we show under which conditions, announcing the truth about buyer preferences is the optimal strategy for the buyer.

REFERENCES

• 1: Integer Programming for Combinatorial Auction Winner Determination, Proceedings of the Fourth International Conference on MultiAgent Systems (ICMAS-2000), p.39, July 10-12, 2000
• 2: Martin Bichler, An experimental analysis of multi-attribute auctions, Decision Support Systems, v.29 n.3, p.249-268, Oct. 2000 [doi>10.1016/S0167-9236(00)00075-0]
• 3: Che, Y. K. Design competition through multidimensional auctions, RAND Journal of Economics, Vol. 24, 1993, 668--680.
• 4: E. Giménez-Funes , L. Godo , J. Rodríguez-Aguilar , P. Garcia-Calvés, Designing Bidding Strategies for Trading Agents in Electronic Auctions, Proceedings of the 3rd International Conference on Multi Agent Systems, p.136, July 03-07, 1998
• 5: Flavio, M. and Monteiro, P. Auctions with endogenous participation, Rev. of Economic Design 5, 2000, 71--89.
• 6: Noam Nisan, Bidding and allocation in combinatorial auctions, Proceedings of the 2nd ACM conference on Electronic commerce, p.1-12, October 17-20, 2000, Minneapolis, Minnesota, United States [doi>10.1145/352871.352872]
• 7: David C. Parkes , Lyle H. Ungar , Dean P. Foster, Accounting for Cognitive Costs in On-Line Auction Design, Selected Papers from the First International Workshop on Agent Mediated Electronic Trading on Agent Mediated Electronic Commerce, p.25-40, May 10, 1998
• 8: David C. Parkes , Lyle H. Ungar, Iterative Combinatorial Auctions: Theory and Practice, Proceedings of the Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on Innovative Applications of Artificial Intelligence, p.74-81, July 30-August 03, 2000
• 9: Jeffrey S. Rosenschein , Gilad Zlotkin, Rules of encounter: designing conventions for automated negotiation among computers, MIT Press, Cambridge, MA, 1994
• 10: Sandholm, T.W. Limitations of the Vickrey Auction in Computational Multiagent Systems. In proc. of ICMAS-96 1996, 299--306.
• 11: 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
• 12: Walsh, W.E., Wellman, M. P., Wurman, P.R. and MacKie-Mason, J. K. Auction protocols for decentralized scheduling. In Proc. 18th International Conference on Distributed Computing Systems, 1998.
• 13: Yoon, K. and Hwang, C. Multiple attribute decision making: an introduction. Thousand Oaks: Sage. 1995.
• 14: A long version of the paper exists at: http://www.cs.biu.ac.il/schwart/papers/Auction-full-paper.doc

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Intelligent agents

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

General Terms:
Economics

Keywords:
bidding and bargaining agents, electronic commerce market