Scheduling tasks with precedence constraints to solicit desirable bid combinations

ABSTRACT

In our previous research we suggested an approach to maximizing agents preferences over schedules of multiple tasks with temporal and precedence constraints. The proposed approach is based on Expected Utility Theory. In this paper we address two mutually dependent questions: (a) what are the properties of the problem domain that can facilitate efficient maximization algorithms, and (b) what criteria determine attractiveness of one or another potential solution to the agent. We discuss different ways of exploring the problem domain. We show that naive optimization approaches often fail to find solutions for risk-averse agents and propose ways of using properties of the domain to improve upon naive approaches.

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: Alexander Babanov , John Collins , Maria Gini, Asking the right question: Risk and expectation in multiagent contracting, Artificial Intelligence for Engineering Design, Analysis and Manufacturing, v.17 n.3, p.173-186, June 2003
• 3: B. P. Gerkey and M. J. Mataric. Sold!: Auction methods for multi-robot coordination. IEEE Trans. Robotics and Automation, 18(5):758--786, October 2002.
• 4: 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]
• 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: A. Mas-Colell, M. D. Whinston, and J. R. Green. Microeconomic Theory. Oxford University Press, 1995.
• 7: R. McAfee and P. J. McMillan. Auctions and bidding. Journal of Economic Literature, 25:699--738, 1987.
• 8: 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]
• 9: 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, 1999.
• 10: 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]
• 11: 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]
• 12: Jean-Paul Watson , J. Christopher Beck , Adele E. Howe , L. Darrell Whitley, Problem difficulty for tabu search in job-shop scheduling, Artificial Intelligence, v.143 n.2, p.189-217, February 2003 [doi>10.1016/S0004-3702(02)00363-6]
• 13: 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.

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

General Terms:
Algorithms, Economics, Theory

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