Ein Multiagentensystem zur Verhandlungsautomatisierung in elektronischen Märkten

Abstract

Der elektronische Handel von Sachgütern über das Internet (E-Commerce) gewinnt für Unternehmen und Konsumenten immer mehr an Bedeutung. Für einen effektiven Ablauf sollten möglichst viele Phasen der Geschäftstransaktionen durch IT-Systeme unterstützt oder automatisiert werden. Heutzutage beinhalten jedoch nur wenige E-Commerce-Anwendungen die wichtige Verhandlungsphase. Es fehlt die Möglichkeit zu komplexen Verhandlungen über mehrere Vertragsattribute zwischen vielen Teilnehmern. Eine geeignete Automatisierungstechnologie sind intelligente Software-Agenten, die autonom nach den Vorgaben ihres Auftraggebers agieren. In der Arbeit wurde ein Multiagentensystem zur Automatisierung von komplexen, multilateralen Verhandlungen in offenen, elektronischen Märkten entworfen. Diese neue Komponente dient zur Verbesserung der Servicequalität von E-Commerce-Anwendungen und zur Steigerung der Transaktionszahlen. Zur Modellierung des Agentensystems wurde die agentenorientierte Software-Engineering-Methode Gaia um zusätzliche Modellen aus anderen Notationen ergänzt. Mit dieser neuen Verfahrensweise wurden Agententypen, ihre Beziehungen und Aufgaben beschrieben sowie eine Ontologie und Kommunikationsprotokolle entworfen. Die Agenten können sowohl an mehreren Auktionsarten als auch an multilateralen, integrativen Verhandlungen teilnehmen. Sie automatisieren somit die Phasen Händlerauswahl und Verhandlung. Wichtige Defizite im Bereich von automatisierten Verhandlungen wurden behoben. Die verbesserte Verhandlungsstrategie der Agenten entscheidet mit Hilfe mehrerer Taktiken, wie der Agent einem Verhandlungspartner entgegenkommt. Die Ressourcentaktiken zur Berücksichtigung der Marktsituation und die Vorgehensweise zur Entscheidung eines Agenten über das Verhandlungsende sind neu, da vor dem Abschluss eines Handels alle parallelen Verhandlungen und die Risikobereitschaft des Agenten mit einbezogen werden. Ein Zufallselement in der Strategie erschwert das Erkennen der angewandten Taktiken und das Ausnutzen durch die Verhandlungspartner. Die Verhandlungsstrategie der Agenten ist generisch und nicht auf spezielle Waren beschränkt. Außerdem kann sie das Verhandlungsergebnis durch Aufteilen des Auftrags in mehrere Teilmengen verbessern. Durch unterschiedliche Parametrisierung und Gewichtung der Taktiken ist ein weites Spektrum an Strategien möglich. Anwender können die Parameter an ihre aktuellen Bedürfnisse und die Marktlage anpassen, damit sich ihre Agenten besser gegen die Konkurrenz behaupten. Der entworfene effiziente Algorithmus dient der flexiblen Generierung von Angeboten und der Erzeugung mehrerer Angebotsalternativen. Der heuristische Algorithmus mit linearer Komplexität ermöglicht eine gute Skalierbarkeit und damit mehr Einsatzmöglichkeiten. Das System wurde mit verbreiteten, plattformunabhängigen, performanten, objektorientierten Technologien implementiert und kann mit seinen auf Standards beruhenden Schnittstellen in viele E-Commerce-Systeme integriert werden. Für spezielle Anforderungen und Strategien können auch externe Agenten mit den bereitgestellten internen Agenten verhandeln. Sicherheit in dem offenen System wird mit Verfahren wie Verschlüsselung gewährleistet. In der ersten Stufe der Evaluierung wurde eine Simulationssoftware konstruiert und zum Testen der Verhandlungsstrategien unter realistischen Bedingungen eingesetzt. In der zweiten Evaluierungsstufe wurde die praktische und breite Einsetzbarkeit des Agentensystems durch die Realisierung von unterschiedlichen Pilotanwendungen bewiesen. In vier europäischen Ländern wurden E-Commerce-Systeme im Business-to-Business und Business-to-Consumer Bereich mit agentenbasierten Auktionen und Verhandlungen erweitert.

Negotiations are an important aspect of business transactions. In many applications of electronic markets only automated negotiations can be applied in an economic way. A suitable automation technology are intelligent software agents, who can act autonomously according to the order of their contractor. So far only systems with limited negotiation possibilities and auction systems exist. In these systems, prices can be changed by only one of the two involved parties; complex negotiations involving more than two participants and several contract conditions are not supported. In this work, a multi-agent system was developed that provides automated support for complex, multilateral negotiations in electronic markets. The presented system allows for improving the quality of service of e-Commerce-applications and for increasing the number of transactions. Due to the lack of a standard and a complete method for modelling agent systems, the agent-oriented software engineering method Gaia was extended by complementing it with models from other authors. This approach allowed modelling several agent types, their relations and tasks as well as an ontology and multiple communication protocols. The agents can participate in several kinds of auctions, as well as in multilateral, integrative negotiations. This way, agents automate the merchant brokering phase and the negotiation phase. The main contribution of the presented work lies in the elimination of important deficits of existing automated multilateral negotiation mechanisms. The negotiation strategy of the proposed agents offers a repertoire of tactics for accommodating negotiation partners. Other novel elements are the resource tactics taking the market situation into account and the method for deciding when to end a negotiation. The decision mechanism considers all parallel negotiations and the agent’s degree of risk aversion. By allowing negative values for utility functions representing the value of offers, the proposed system is able to detect when a negotiation partner is trying to accommodate, even if the offer is not yet acceptable. This allows coming to an agreement, even if the negotiation partner is using imitating tactics with a flexible attribute utility distribution. To make it harder for negotiation partners to figure out the agent’s negotiation tactics and to exploit this knowledge during negotiations the proposed system introduces randomness into its strategy. The negotiation strategy of the agents is generic and not limited to specific goods. In addition, the proposed strategy allows improving the negotiation result by dividing orders into subsets. Parameterization and weighting of tactics make a wide range of strategies possible. To give their agents a competitive advantage, the presented system allows users to hand-optimize agent parameters and to adapt them to the users’ needs and the market situation at hand. As part of the work reported in this dissertation, an efficient and flexible offer generation algorithm was designed. This algorithm can generate multiple alternative offers, each of which has a similar utility for the agent’s user. In the common case where the negotiation partners have different preferences, this facilitates finding more favourable solutions for both sides. This algorithm works without making assumptions about limits or attribute weights of the negotiation partner. The algorithm also considers adequately negotiation attributes with few permitted values and thus large utility differences between these values. Unlike approaches computing optimal solutions, the proposed heuristic algorithm offers linear complexity. This allows for scalability and thus a wider range of applications. The number of simultaneously acting agents is therefore only limited by the polynomial number of parallel negotiations. Load peaks are flattened by reducing the number of offers per negotiation. The experiences gained during prototyping were used to adapt the architecture and the user interface of the multi-agent system to the requirements of client companies. The system was implemented in Java, a common, platform-independent, performant, object-oriented technology. With its open interfaces based on the HTTP and XML standards, the proposed system can be integrated into existing e-Commerce applications. If necessary, external agents using different strategies can negotiate with internal agents using the CORBA interface. Authentication and encryption ensure security thereby. The evaluation was accomplished in two stages. First, to test the negotiation strategies and algorithms under realistic conditions, a simulation program was developed. In the second evaluation stage, a series of pilot applications demonstrated the applicability of the proposed agent system. In four European countries, e-Commerce-systems for Business-to-Business and Business-to-Consumer applications were extended with agent-based auctions and negotiations.