Risk and expectations in a-priori time allocation in multi-agent contracting

ABSTRACT

In related research we have proposed a market architecture for multi-agent contracting and we have implemented prototypes of both the market architecture and the agents in a system called MAGNET. A customer agent in MAGNET solicits bids for the execution of multi-step plans, in which tasks have precedence and time constraints, by posting a Request for Quotes to the market. The Request for Quotes needs to include for each task its precedence constraints and a time window. In this paper, we study the problem of optimizing the time windows in the Requests for Quotes. Our approach is to use the Expected Utility Theory to reduce the likelihood of receiving unattractive bids, while maximizing the number of bids that are likely to be included in the winning bundle. We describe the model, illustrate its operation and properties, and discuss what assumptions are required for its successful integration into MAGNET or other multi-agent contracting systems.

REFERENCES

• 1: John Collins , Corey Bilot , Maria Gini , Bamshad Mobasher, Decision Processes in Agent-Based Automated Contracting, IEEE Internet Computing, v.5 n.2, p.61-72, March 2001 [doi>10.1109/4236.914649]
• 2: J. Collins, M. Gini, and B. Mobasher. Multi-agent negotiation using combinatorial auctions with precedence constraints. Technical Report 02-009, University of Minnesota, Department of Computer Science and Engineering, Minneapolis, Minnesota, February 2002.
• 3: John Collins , Maksim Tsvetovat , Rashmi Sundareswara , Joshua van Tonder , Maria Gini , Bamshad Mobasher, Evaluating risk: flexibility and feasibility in multi-agent contracting, Proceedings of the third annual conference on Autonomous Agents, p.350-351, April 1999, Seattle, Washington, United States [doi>10.1145/301136.301229]
• 4: John Collins , Ben Youngdahl , Scott Jamison , Bamshad Mobasher , Maria Gini, A market architecture for multi-agent contracting, Proceedings of the second international conference on Autonomous agents, p.285-292, May 10-13, 1998, Minneapolis, Minnesota, United States [doi>10.1145/280765.280845]
• 5: M. B. Dias and A. Stentz. A free market architecture for distributed control of a multirobot system. In Sixth Int'l Conf. on Intelligent Autonomous Systems, pages 115--122, Venice, Italy, July 2000.
• 6: Alyssa Glass , Barbara Grosz, Socially conscious decision-making, Proceedings of the fourth international conference on Autonomous agents, p.217-224, June 03-07, 2000, Barcelona, Spain [doi>10.1145/336595.337385]
• 7: B. J. Grosz, L. Hunsberger, and S. Kraus. Planning and acting together. AI Magazine, 20(4):23--34, 1999.
• 8: 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]
• 9: A Combinatorial Auction for Collaborative Planning, Proceedings of the Fourth International Conference on MultiAgent Systems (ICMAS-2000), p.151, July 10-12, 2000
• 10: B. Jullien and B. Salanie. Estimating preferences under risk: The case of racetrack bettors. The Journal of Political Economy, 108(3):503--530, June 2000.
• 11: D. Kjenstad. Coordinated Supply Chain Scheduling. PhD thesis, Dept of Production and Quality Engineering, Norvegian University of Science and Technology, Trondheim, Norway, 1998.
• 12: J. Machina. Choice under uncertainty: Problems solved and unsolved. The Journal of Economic Perspectives, 1(1):121--154, 1987.
• 13: M. J. Machina. Dynamic consistency and non-expected utility models of choice und er uncertainty. The Journal of Economic Literature, 27(4):1622--1668, December 1989.
• 14: A. Mas-Colell, M. D. Whinston, and J. R. Green. Microeconomic Theory. Oxford University Press, January 1995.
• 15: R. McAfee and P. J. McMillan. Auctions and bidding. Journal of Economic Literature, 25:699--738, 1987.
• 16: 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]
• 17: David C. Parkes , Lyle H. Ungar, An auction-based method for decentralized train scheduling, Proceedings of the fifth international conference on Autonomous agents, p.43-50, May 2001, Montreal, Quebec, Canada [doi>10.1145/375735.375866]
• 18: M. E. Pollack. Planning in dynamic environments: The DIPART system. In A. Tate, editor, Advanced Planning Technology. AAAI Press, 1996.
• 19: J. W. Pratt. Risk aversion in the small and in the large. Econometrica, 32:122--136, 1964.
• 20: Colin R. Reeves, Modern heuristic techniques for combinatorial problems, John Wiley & Sons, Inc., New York, NY, 1993
• 21: N. M. Sadeh, D. W. Hildum, D. Kjenstad, and A. Tseng. MASCOT: an agent-based architecture for coordinated mixed-initiative supply chain planning and scheduling. In Workshop on Agent-Based Decision Support in Managing the Internet-Enabled Supply Chain, at Agents '99, pages 133--138, May 1999.
• 22: 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
• 23: V. K. Smith and W. H. Desvousges. An empirical analysis of the economic value of risk changes. The Journal of Political Economy, 95(1):89--114, February 1987.
• 24: William E. Walsh , Michael P. Wellman , Fredrik Ygge, Combinatorial auctions for supply chain formation, Proceedings of the 2nd ACM conference on Electronic commerce, p.260-269, October 17-20, 2000, Minneapolis, Minnesota, United States [doi>10.1145/352871.352900]
• 25: M. P. Wellman, W. E. Walsh, P. R. Wurman, and J. K. MacKie-Mason. Auction protocols for decentralized scheduling. Games and Economic Behavior, 35:271--303, 2001.
• 26: 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:
  K. Computing Milieux
  K.4 COMPUTERS AND SOCIETY
      K.4.4 Electronic Commerce

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

General Terms:
Algorithms, Economics, Theory

Keywords:
automated auctions, expected utility, multi-agent contracting, risk estimation