Simulation of time-independent strategies for automated negotiation

Abstract

The active research area of automated negotiation is gaining steadily in importance. Not only because automated negotiation is used as a coordination mechanism between autonomous computer agents in numerous scenarios, but also because it is generally accepted that automated computers are superior to their human counterparts in negotiations, research is being conducted on various aspects of automated negotiation. However, current research approaches in automated negotiation merely transfer human negotiation strategies to automated computer agents, neglecting the essential difference between humans and computers: Computing power. Machines can calculate much faster, and therefore time can be disregarded in automated negotiations. Consequently, the goal of this thesis is to investigate time-independent automated negotiation strategies with special emphasis on bilateral negotiations with multiple negotiation items. For this purpose, a software solution was designed and implemented to test these strategies against each other in a tournament for different negotiation problems. This will be achieved by simulation, with a special focus on three areas: proposal generation, reaction to unfair counter-offers and the negotiation problem. It could be shown in this thesis that the implemented time-independent strategies are superior to their time-dependent relatives. The next step was to identify the best time-independent strategies. To determine a definition for the best strategies, four evaluation criteria were derived. It can be said, however, that there is not one best strategy because the answer depends strongly on the criteria. The results obtained must be limited because the negotiation objectives were not weighted differently, which turned out to be a strong limitation of reality. Furthermore, the modelling of the opponents was not considered in this work. Taking this into account, the work can offer important approaches for a more in-depth analysis of the presented offer strategies, rejection strategies and negotiation problems.

Das aktive Forschungsgebiet der automatisierten Verhandlung gewinnt stetig an Bedeutung. Nicht nur weil automatisierte Verhandlungen als Koordinationsmechanismus zwischen autonomen Computeragenten in zahlreichen Szenarien eingesetzt werden, sondern auch weil es als allgemein akzeptiert gilt, dass bei Verhandlungen automatisierte Computer ihren menschlichen Konkurrenten gegenüber überlegen sind, wird zu unterschiedlichsten Aspekten der automatisierten Verhandlung geforscht. Die derzeitigen Forschungsansätze in der automatisierten Verhandlung übertragen jedoch lediglich menschliche Verhandlungsstrategien auf die automatisierten Computer-Agenten, wobei der wesentliche Unterschied zwischen Menschen und Computer vernachlässigt wird: Die Rechenleistung. Maschinen können viel schneller rechnen, und daher kann die Zeit bei automatisierten Verhandlungen außer Acht gelassen werden. Folglich ist das Ziel dieser Arbeit die Erforschung von zeitunabhängigen automatisierten Verhandlungsstrategien mit besonderem Schwerpunkt auf bilateralen Verhandlungen mit mehreren Verhandlungsgegenständen. Zu diesem Zweck wurde eine Softwarelösung konzipiert und implementiert, mit der diese Strategien in einem Turnier für verschiedene Verhandlungsprobleme gegeneinander getestet werden können. Dies wird durch eine Simulation erreicht, wobei sich die Arbeit besonders auf drei die Bereiche Angebotserstellung, Reaktion auf unfaire Gegenangebote und das Verhandlungsproblem konzentriert. Es konnte in dieser Arbeit gezeigt werden, dass die implementierten zeitunabhängigen Strategien ihren zeitabhängigen Verwandten überlegen sind. Der nächste Schritt bestand darin, die besten zeitunabhängigen Strategien zu identifizieren. Um eine Definition für die besten Strategien zu bestimmen, wurden vier Bewertungskriterien abgeleitet. Man kann jedoch sagen, dass es nicht eine beste Strategie gibt, da die Antwort stark von den Kriterien abhängt. Die erzielten Ergebnisse müssen eingeschränkt werden, da die Verhandlungsziele nicht unterschiedlich gewichtet wurden, was sich als starke Einschränkung der Realität herausstellte. Weiters wurde die Modellierung der Gegner in dieser Arbeit nicht berücksichtigt. Dies berücksichtigend kann die Arbeit wichtige Ansätze für eine vertiefte Analyse der vorgestellten Angebotsstrategien, Ablehnungsstrategien und Verhandlungsprobleme bieten