Predicting Agents Tactics in Automated Negotiation Chongming Hou Knowledge Media Institute The Open University Milton Keynes, MK7 6AA c.m.hou@open.ac.uk Abstract This paper presents a learning mechanism that applies nonlinear regression analysis to predict a negotiation agent’s behaviour based only the opponent's previous offers. The behaviour of negotiation agents in this study is determined by their tactics in the form of decision functions. Heuristics based on estimates of an agent’s tactics are drawn from a series of experiments. The findings of this empirical study show that this approach can be used to obtain better deals than existing decision function tactics. The learning mechanism can be used online, without any prior knowledge about the other agents and is therefore, very useful in open systems where agents have little or no information about each other. 1. Introduction Negotiation is a process of joint decision making between two or more parties in an effort to resolve their conflicting demands. Negotiation has been treated formally by researchers in economics and game theory, and informally (i.e. based on observations) by researchers in industrial relations, international relations and counselling. This paper focuses on the study of two-party negotiation, which is the subject of a great deal more empirical research than the multiparty case [6]. Moreover, multiparty negotiation can be described as multiple, mutually influencing, two-party negotiations over multiple issues [3]. In two-party negotiation, the two agents play opposing roles, such as buyer and seller. Our research on negotiation lies between the fully co-operative and fully competitive negotiations. In electronic commerce, the task of negotiation can be delegated to a software agent in order to save human users time on activities which are either routine or demanding. To get better individual or social outcomes, the software agents require appropriate tactics. A tactic is the decision policy for choosing actions in different situations. Because negotiation is an interactive process, the outcome is not only determined by an agent’s own tactic but it is also influenced by the other agent’s choices. This characteristic makes it difficult to find an optimal tactic. The research presented here focuses on the online prediction of the other agent’s tactic in order to reach better deals in negotiation. The following section reviews some of the related research on negotiation tactics. Section 3 explains the motivation for predicting an opponent’s negotiation tactic. The use of nonlinear regression for estimating the family, form and parameters of an opponent’s tactic is introduced in Section 4. Section 5 presents a set of heuristics for identifying an opponent’s negotiation deadline and reservation value using the results of the nonlinear regression analysis. To test the performance of the prediction mechanism against other prevailing tactics, a set of two-party negotiations were carried out and the results are described in Section 6. Section 7 discusses the use of the proposed prediction mechanism. Section 8 highlights the main conclusions to be drawn from this work and Section 9 discusses some potential areas for future research. 2. Related work The related work carried out in game theory is presented in the following subsection. This work typically assumes that each agent has complete knowledge of the other agent’s actions and that each agent has unbounded computational power to explore the space of acceptable deals. However, these theoretical assumptions are not necessarily true in practice. Due to the failing assumptions, decision functions were proposed that would enable an agent to generate offers according to the time remaining, the resources available, or, the behaviour of an opponent. The three families of decision functions and their common forms are described. The section concludes with an overview of some related work on exploring optimal strategies and effective tactics. 1
