skip to main content
10.1145/779928.779936acmconferencesArticle/Chapter ViewAbstractPublication PagesecConference Proceedingsconference-collections
Article

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

Published:09 June 2003Publication History

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.]]Google ScholarGoogle Scholar
  2. A. Byde. A dynamic programming model for algorithm design in simultaneous auctions. In Proc. $2^nd$ Int. Workshop on Electronic Commerce (WELCOM-01), LNCS. Springer Verlag, 2001.]] Google ScholarGoogle ScholarDigital LibraryDigital Library
  3. A. Byde, C. Preist, and N. Jennings. Decision procedures for multiple simultaneous auctions. In Proc. $1^st$ Int. Conf. Autonomous Agents and Multi-Agent Systems, pages 613--620, 2002.]] Google ScholarGoogle ScholarDigital LibraryDigital Library
  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.]]Google ScholarGoogle ScholarCross RefCross Ref
  5. P. Faratin, C. Sierra, and N. Jennings. Negotiation decision functions for autonomous agents. Robotics and Autonomous Systems, 3-4(24):159--182, 1998.]]Google ScholarGoogle ScholarCross RefCross Ref
  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.]]Google ScholarGoogle Scholar
  7. S. Gjerstad and J. Dickhaut. Price formation in double auctions. Games and Economic Behaviour, 22(1):1--29, 1998.]]Google ScholarGoogle ScholarCross RefCross Ref
  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.]]Google ScholarGoogle Scholar
  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.]]Google ScholarGoogle Scholar
  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.]]Google ScholarGoogle ScholarCross RefCross Ref
  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.]]Google ScholarGoogle ScholarCross RefCross Ref
  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.]]Google ScholarGoogle ScholarCross RefCross Ref
  13. E. Ogsten and S. Vassiliadis. A peer-to-peer agent auction. In Proc. $1^st$ Int. Conf. Autonomous Agents and Multi-Agent Systems, pages 151--159, 2002.]] Google ScholarGoogle ScholarDigital LibraryDigital Library
  14. S. Park, E. Durfee, and W. Birmingham. Emergent properties of a market-based digital library with strategic agents. In Proc. $2^nd$ Int. Conf. on Multi-Agent Systems, 1998.]] Google ScholarGoogle ScholarDigital LibraryDigital Library
  15. S. Park, E. Durfee, and W. Birmingham. An adaptive agent bidding strategy based on stochastic modelling. In Proc. $3^rd$ Int. Conf. on Autonomous Agents, 1999.]] Google ScholarGoogle ScholarDigital LibraryDigital Library
  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.]]Google ScholarGoogle ScholarCross RefCross Ref
  17. C. Preist, C. Bartolini, and I. Philips. Algorithm design for agents which participate in multiple simultaneous auctions. In F. Dignum and U. Cortes, editors, Agent Mediated Electronic Commerce III, Lecture Notes in AI. Springer Verlag, September 2001.]] Google ScholarGoogle ScholarDigital LibraryDigital Library
  18. C. Preist, A. Byde, and C. Bartolini. Economic dynamics of agents in multiple auctions. In Proc. $5^th$ Int. Conf. on Autonomous Agents, 2001.]] Google ScholarGoogle ScholarDigital LibraryDigital Library
  19. C. Preist, A. Byde, C. Bartolini, and G. Piccinelli. Towards agent-based service composition through negotiation in multiple auctions. AISBJ, 1(1), 2001.]]Google ScholarGoogle Scholar
  20. C. Preist and C. Merida-Campos. Automated negotiation in many-to-many markets for imperfectly substitutable goods. In Julian Padget, David Parkes, Norman Sadeh, Onn Shehory, and William Walsh, editors, Agent-Mediated Electronic Commerce IV, volume 2531 of Lecture Notes in Artificial Intelligence. Springer Verlag, 2002. to appear.]] Google ScholarGoogle ScholarDigital LibraryDigital Library
  21. C. Preist and M. van Tol. Adaptive agents in a persistent shout double auction. In Proc. $1^st$ Int. Conf. on the Internet, Computing and Economics. ACM Press, 1998.]] Google ScholarGoogle ScholarDigital LibraryDigital Library
  22. J. Rosenschein and G. Zlotkin. Rules of Encounter. MIT Press, 1994.]]Google ScholarGoogle ScholarDigital LibraryDigital Library
  23. T. Sandholm. eMediator: A next generation electronic commerce server. In Proc. $4^th$ Int. Conf. on Autonomous Agents, 2000.]] Google ScholarGoogle ScholarDigital LibraryDigital Library
  24. M. Schillo, C. Kray, and K. Fischer. The eager bidder problem: A fundamental problem of dai and selected solutions. In Proc. $1^st$ Int. Conf. Autonomous Agents and Multi-Agent Systems, pages 599--606, 2002.]] Google ScholarGoogle ScholarDigital LibraryDigital Library
  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.]]Google ScholarGoogle ScholarDigital LibraryDigital Library
  26. P. Stone, M. Littman, S. Singh, and M. Kearns. ATTac-2000: An adaptive autonomous bidding agent. In Jörg P. Müller, Elisabeth Andre, Sandip Sen, and Claude Frasson, editors, Proceedings of the Fifth International Conference on Autonomous Agents, pages 238--245, Montreal, Canada, 2001. ACM Press.]] Google ScholarGoogle ScholarDigital LibraryDigital Library
  27. P. Stone, R. E. Schapire, and J. A. Csirik. ATTac-2001: A learning, autonomous bidding agent. In Julian Padget, David Parkes, Norman Sadeh, Onn Shehory, and William Walsh, editors, Agent-Mediated Electronic Commerce IV, volume 2531 of Lecture Notes in Artificial Intelligence. Springer Verlag, 2002. to appear.]] Google ScholarGoogle ScholarDigital LibraryDigital Library
  28. G. Tesauro and J. L. Bredin. Strategic sequential bidding in auctions using dynamic programming. In Proc. AAMAS02, pages 591--598, 2002.]] Google ScholarGoogle ScholarDigital LibraryDigital Library
  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.]]Google ScholarGoogle ScholarDigital LibraryDigital Library
  30. M. P. Wellman, A. Greenwald, P. Stone, and Peter R. Wurman. The 2002 trading agent competition. In Proceedings of the $14^th$ Innovative Applications of Artificial Intelligence Conference, 2002.]] Google ScholarGoogle ScholarDigital LibraryDigital Library

Index Terms

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

          Recommendations

          Reviews

          Maria L. Gini

          Presented in this paper are algorithms for software agents who buy components and sell services through auctions. The problem is important when an agent has to make decisions about what to buy at what price, prior to knowing if what was bought can be combined with other components to be resold for a profit. The paper presents two algorithms-one more exact and the other more efficient-based on computing the expected utility from the auctions. The use of the algorithms by an imaginary transport company is described. The paper is clearly written, and provides sufficient details about the algorithms that would enable others to implement them. The assumptions made in the study are also clearly stated. It would have been nice to have more experimental results, as well as results on real data, to be able to assess how well the agent using the algorithms performs, but it is hard to expect more from a conference paper. Online Computing Reviews Service

          Access critical reviews of Computing literature here

          Become a reviewer for Computing Reviews.

          Comments

          Login options

          Check if you have access through your login credentials or your institution to get full access on this article.

          Sign in
          • Published in

            cover image ACM Conferences
            EC '03: Proceedings of the 4th ACM conference on Electronic commerce
            June 2003
            292 pages
            ISBN:158113679X
            DOI:10.1145/779928

            Copyright © 2003 ACM

            Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

            Publisher

            Association for Computing Machinery

            New York, NY, United States

            Publication History

            • Published: 9 June 2003

            Permissions

            Request permissions about this article.

            Request Permissions

            Check for updates

            Qualifiers

            • Article

            Upcoming Conference

            EC '24
            The 25th ACM Conference on Economics and Computation
            July 8 - 11, 2024
            New Haven , CT , USA

          PDF Format

          View or Download as a PDF file.

          PDF

          eReader

          View online with eReader.

          eReader