Auction in dynamic environments: incorporating the cost caused by re-allocation

ABSTRACT

This paper proposes an auction protocol for solving a resource allocation problem in dynamic environments. In such environments, the valuation of resources has uncertainty for each bidder, i.e., this valuation depends on the situation not only at the point when the auction is held but also at the point when the allocated resources are actually used. For example a bidder's valuation in fine weather may be different from that in rainy weather. A solution for dealing with this problem is to execute auctions whenever an event occurs and then to re-allocate resources. Re-allocating resources, however, may cause disutility. Moreover, it does not always provide an equilibrium strategy because it can be viewed as a sequential auction, which means that we cannot accurately predict what outcome will be obtained. To solve this problem, we propose an auction protocol that allows bidders to declare the cost due to re-allocation and then decides an allocation based on this cost of re-allocation as well as the surplus obtained from the allocated resources themselves in the realized situation. We prove that a bidder's truth telling is in equilibrium and that a socially efficient allocation is obtained in the proposed protocol.

REFERENCES

• 1: R. K. Dash, N. R. Jennings, and D. C. Parkes. Computational-mechanism design: a call to arms. IEEE Intelligent Systems, 18(6):40--47, 2003.
• 2: Yuzo Fujishima , David McAdams , Yoav Shoham, Speeding Up Ascending-Bid Auctions, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, p.554-563, July 31-August 06, 1999
• 3: P. A. Haile. Auctions with private uncertainty and resale opportunities. Journal of Economic Theory, 108(1):72--110, 2003.
• 4: Takayuki Ito , Makoto Yokoo , Shigeo Matsubara, A Combinatorial Auction Protocol among Versatile Experts and Amateurs, Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, p.378-385, July 19-23, 2004, New York, New York [doi>10.1109/AAMAS.2004.6]
• 5: D. N. Kinny and M. P. Georgeff. Commitment and effectiveness of situated agents. In Proceedings of the Twelfth International Conference on Artificial Intelligence (IJCAI-91), pages 82--88, 1991.
• 6: 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
• 7: A. Mas-Colell, M. D. Whinston, and J. R. Green. Microeconomic Theory. Oxford University Press, 1995.
• 8: P. Milgrom. Putting Auction Theorey to Work. Cambridge University Press, 2004.
• 9: R. Porter, A. Ronen, Y. Shoham, and M. Tennenholtz. Mechanism design with execution uncertainty. In Proceedings of the Eighteenth Conference on Uncertainty in Artificial Intelligence (UAI-02), 2002.
• 10: E. Rasmusen. Games and Information: an introduction to game theory. Blackwell Publishers, 3rd edition, 2001.
• 11: Stuart J. Russell , Peter Norvig, Artificial intelligence: a modern approach, Prentice-Hall, Inc., Upper Saddle River, NJ, 1995
• 12: Tuomas Sandholm, Algorithm for optimal winner determination in combinatorial auctions, Artificial Intelligence, v.135 n.1-2, p.1-54, 02/01/2002 [doi>10.1016/S0004-3702(01)00159-X]
• 13: T. W. Sandholm and V. R. Lesser. Advantages of a leveled commitment contracting protocol. In Proceedings of the Thirteenth National Conference on Artificial Intelligence (AAAI-96), pages 126--133, 1996.
• 14: M. Yokoo, Y. Sakurai, and S. Matsubara. The effect of false-name bids in combinatorial auctions: New fraud in internet auctions. Games and Economic Behavior, 46(1):174--188, 2004.

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:
Design, Economics

Keywords:
mechanism design