Agent-based service composition through simultaneous negotiation in forward and reverse auctions

ABSTRACT

Service composition is the act of taking several component products or services, and bundling them together to meet the needs of a given customer. In the future, service composition will play an increasingly important role in e-commerce, and automation will be desirable to improve speed and efficiency of customer response. In this paper, we consider a service composition agent that both buys components and sells services through auctions. It buys component services by participating in many English auctions. It sells composite services by participating in Request-for-Quotes reverse auctions. Because it does not hold a long-term inventory of component services, it must take risks; it must make offers in reverse auctions prior to purchasing all the components needed, and must bid in English auctions prior to having a guaranteed customer for the composite good. We present algorithms that is able to manage this risk, by appropriately bidding/offering in many auctions and reverse auctions simultaneously. The algorithms will withdraw from one set of possible auctions and move to another set if this will produce a better-expected outcome, but will effectively manage the risk of accidentally winning outstanding bids/offers during the withdrawal process. We illustrate the behavior of these algorithms through a set of worked examples.

REFERENCES

• 1: P. Anthony, W. Hall, V. Dang, and N.R. Jennings. Autonomous agents for participating in multiple on-line auctions. In Proc. IJCAI Workshop on E-Business and the Intelligent Web, pages 54--64, 2001.
• 2: Andrew Byde, A Dynamic Programming Model for Algorithm Design in Simultaneous Auctions, Proceedings of the Second International Workshop on Electronic Commerce, p.152-163, November 16-17, 2001
• 3: Andrew Byde , Chris Preist , Nicholas R. Jennings, Decision procedures for multiple auctions, Proceedings of the first international joint conference on Autonomous agents and multiagent systems: part 2, July 15-19, 2002, Bologna, Italy [doi>10.1145/544862.544888]
• 4: D. Cliff and J. Bruten. Less than human: Simple adaptive trading agents for CDA markets. In Proc. of the 1998 Symposium on Computation in Economics, Finance, and Engineering: Economic Systems, 1998.
• 5: P. Faratin, C. Sierra, and N. Jennings. Negotiation decision functions for autonomous agents. Robotics and Autonomous Systems, 3-4(24):159--182, 1998.
• 6: P. Garcia, E. Giminez, L. Godo, and J. Rodriguez-Aguilar. Possibilistic-based design of bidding strategies in electronic auctions. In Proc. 13th Biennial European Conference on Artificial Intelligence, 1998.
• 7: S. Gjerstad and J. Dickhaut. Price formation in double auctions. Games and Economic Behaviour, 22(1):1--29, 1998.
• 8: M. He and N. Jennings. Southamptontac: Designing a successful trading agent. In Proc $15^th$ European Conf. on AI (ECAI-2002), pages 8--12, 2002.
• 9: M. He, H. Leung, and N. Jennings. A fuzzy logic based bidding strategy for autonomous agents in continuous double auctions. In IEEE. trans., 2002.
• 10: T. Ito, N. Fukuta, T. Shintani, and K. Sycara. BiddingBot: A multiagent support system for cooperative bidding in multiple auctions. In Proc. $4^th$ Int. Conf. on Multi-Agent Systems, pages 182--189, 2000.
• 11: N. R. Jennings, P. Faratin, M. J. Johnson, P. O. O'Brien, and M. E. Wiegand. Using intelligent agents to manage business processes. In First International Conference on the Practical Application of Intelligent Agents and Multi-Agent Technology (PAAM-96), pages 345--360, April 1996.
• 12: B. Laasri, H. Laasri, S. Lander, and V. Lesser. Generic model for intelligent negotiating agents. International Journal of Intelligent and Cooperative Information Systems, 2(1):291--317, 1992.
• 13: Elth Ogston , Stamatis Vassiliadis, A peer-to-peer agent auction, 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.544776]
• 14: S. Park , E. Durfee , W. Birmingham, Emergent Properties of a Market-based Digital Library with Strategic Agents, Proceedings of the 3rd International Conference on Multi Agent Systems, p.230, July 03-07, 1998
• 15: Sunju Park , Edmund H. Durfee , William P. Birmingham, An adaptive agent bidding strategy based on stochastic modeling, Proceedings of the third annual conference on Autonomous Agents, p.147-153, April 1999, Seattle, Washington, United States [doi>10.1145/301136.301181]
• 16: S. Parsons, C. Sierra, and N. R. Jennings. Agents that reason and negotiate by arguing. Journal of Logic and Computation, 8(3):261--292, 1998.
• 17: Chris Preist , Claudio Bartolini , Ivan Phillips, Algorithm Design for Agents which Participate in Multiple Simultaneous Auctions, Agent-Mediated Electronic Commerce III, Current Issues in Agent-Based Electronic Commerce Systems (includes revised papers from AMEC 2000 Workshop), p.139-154, January 2001
• 18: Chris Preist , Andrew Byde , Claudio Bartolini, Economic dynamics of agents in multiple auctions, Proceedings of the fifth international conference on Autonomous agents, p.545-551, May 2001, Montreal, Quebec, Canada [doi>10.1145/375735.376441]
• 19: C. Preist, A. Byde, C. Bartolini, and G. Piccinelli. Towards agent-based service composition through negotiation in multiple auctions. AISBJ, 1(1), 2001.
• 20: Chris Preist , Carlos Mérida-Campos, Automated Negotiation in Many-to-Many Markets for Imperfectly Substitutable Goods, Revised Papers from the Workshop on Agent Mediated Electronic Commerce on Agent-Mediated Electronic Commerce IV, Designing Mechanisms and Systems, p.203-218, July 16, 2002
• 21: Chris Preist , Maarten van Tol, Adaptive agents in a persistent shout double auction, Proceedings of the first international conference on Information and computation economies, p.11-18, October 25-28, 1998, Charleston, South Carolina, United States [doi>10.1145/288994.288998]
• 22: J. Rosenschein and G. Zlotkin. Rules of Encounter. MIT Press, 1994.
• 23: Tuomas Sandholm, eMediator: a next generation electronic commerce server, Proceedings of the fourth international conference on Autonomous agents, p.341-348, June 03-07, 2000, Barcelona, Spain [doi>10.1145/336595.337522]
• 24: Michael Schillo , Christian Kray , Klaus Fischer, The eager bidder problem: a fundamental problem of DAI and selected solutions, Proceedings of the first international joint conference on Autonomous agents and multiagent systems: part 2, July 15-19, 2002, Bologna, Italy [doi>10.1145/544862.544886]
• 25: R. G. Smith. The Contract Net protocol: High level communication and control in a distributed problem solver. IEEE Transactions on Computing, 29(12):1104--1113, 1980.
• 26: Peter Stone , Michael L. Littman , Satinder Singh , Michael Kearns, ATTac-2000: an adaptive autonomous bidding agent, Proceedings of the fifth international conference on Autonomous agents, p.238-245, May 2001, Montreal, Quebec, Canada [doi>10.1145/375735.376301]
• 27: Peter Stone , Robert E. Schapire , János Csirik , Michael L. Littman , David A. McAllester, ATTac-2001: A Learning, Autonomous Bidding Agent, Revised Papers from the Workshop on Agent Mediated Electronic Commerce on Agent-Mediated Electronic Commerce IV, Designing Mechanisms and Systems, p.143-160, July 16, 2002
• 28: Gerald Tesauro , Jonathan L. Bredin, Strategic sequential bidding in auctions using dynamic programming, Proceedings of the first international joint conference on Autonomous agents and multiagent systems: part 2, July 15-19, 2002, Bologna, Italy [doi>10.1145/544862.544885]
• 29: G. Tesauro and R. Das. High-performance bidding agents for the continuous double auction. In Proceedings of IJCAI workshop on Economic Agents, Models and Mechanisms, 2001.
• 30: Michael P. Wellman , Amy Greenwald , Peter Stone , Peter R. Wurman, The 2001 trading agent competition, Eighteenth national conference on Artificial intelligence, p.935-941, July 28-August 01, 2002, Edmonton, Alberta, Canada

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.1 Applications and Expert Systems

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search

General Terms:
Algorithms

Keywords:
agent, auctions, bidding, service composition