Risk and user preferences in winner determination

ABSTRACT

We discuss a solution to the winner determination problem which takes into account not only costs but also risk aversion of the agent that accepts the bids and works for tasks that have time and precedence constraints. We develop an equivalent unit approach to the group of tasks to analyze the system and use Expected Utility Theory as the basic mechanism for decision-making. Our theoretical and experimental analysis shows that Expected Utility is especially useful for choosing between cheap-but-risky and costly-but-safe bids. Moreover, we show how bids with similar costs and similar probabilities of being successfully completed but different time windows can be efficiently selected or rejected.

REFERENCES

• 1: Alexander Babanov , John Collins , Maria Gini, Risk and expectations in a-priori time allocation in multi-agent contracting, 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.544758]
• 2: Martin Bichler, The Future of Emarkets: Multi-Dimensional Market Mechanisms, Cambridge University Press, New York, NY, 2001
• 3: Tapan Biswas. Decision-Making Under Uncertainty. St. Martin's Press, Inc., 1997.
• 4: John Edgar Collins , Maria L. Gini, Solving combinatorial auctions with temporal constraints in economic agents, 2002
• 5: 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 ]
• 6: John Collins , Güleser Demir , Maria Gini, Bidtree Ordering in IDA* Combinatorial Auction Winner-Determination with Side Constraints, Revised Papers from the Workshop on Agent Mediated Electronic Commerce on Agent-Mediated Electronic Commerce IV, Designing Mechanisms and Systems, p.17-33, July 16, 2002
• 7: John Collins and Maria Gini. An integer programming formulation of the bid evaluation problem for coordinated tasks. In Brenda Dietrich and Rakesh V. Vohra, editors, Mathematics of the Internet: E-Auction and Markets, volume 127 of IMA Volumes in Mathematics and its Applications, pages 59--74. Springer-Verlag, New York, 2001.
• 8: John Collins, Wolfgang Ketter, and Maria Gini. A multi-agent negotiation testbed for contracting tasks with temporal and precedence constraints. Int'l Journal of Electronic Commerce, 7(1):35--57, 2002.
• 9: A. Goicoechea, D. R. Hansen, and L. Duckstein. Multiobjective Decision Analysis with Engineering and Business Applications. John Wiley & Sons, New York, 1982.
• 10: Paul Milgrom. Auction and bidding: a primer. Journal of Economic Perspectives, 3(3):3--22, 1989.
• 11: 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]
• 12: Ryan Porter, Amir Ronen, Yoav Shoham, and Moshe Tennenholtz. Mechanism design with execution uncertainty. In UAI-02, 2002.
• 13: Norman M. Sadeh, David W. Hildum, Dag Kjenstad, and Allen 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, 1999.
• 14: 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 ]
• 15: J. von Neumann and O. Morgenstern. Theory of Games and Economic Behavor. Princeton Univ. Press, Princeton, 1947.
• 16: 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]
• 17: Jean Paul Watson, J. Christopher Beck, Adele Howe, and L. Darrell Whitley. Problem difficulty for tabu search in job-shop scheduling. Artificial Intelligence, 2002.
• 18: Michael P. Wellman, William E. Walsh, Peter R. Wurman, and Jeffrey K. MacKie-Mason. Auction protocols for decentralized scheduling. Games and Economic Behavior, 35:271--303, 2001.

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence

  J. Computer Applications
  J.4 SOCIAL AND BEHAVIORAL SCIENCES

General Terms:
Algorithms, Economics, Theory

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