Shortening Automated Negotiation Threads via Neural Nets

Abstract

In the artificial intelligence domain, an emerging research field that rapidly gains momentum is Automated Negotiations (Fatima, Wooldridge, & Jennings, 2007) (Buttner, 2006). In this framework, building intelligent agents (Silva, Romão, Deugo, & da Silva, 2001) adequate for participating in negotiations and acting autonomously on behalf of their owners is a very challenging research topic (Saha, 2006) (Jennings, Faratin, Lomuscio, Parsons, Sierra, & Wooldridge, 2001). In automated negotiations, three main items need to be specified (Faratin, Sierra, & Jennings, 1998) (Rosenschein, & Zlotkin, 1994): (i) the negotiation protocol & model, (ii) the negotiation issues, and (iii) the negotiation strategies that the agents will employ. According to (Walton, & Krabbe, 1995), “Negotiation is a form of interaction in which a group of agents, with conflicting interests and a desire to cooperate try to come to a mutually acceptable agreement on the division of scarce resources”. These resources do not only refer to money, but also include other parameters, over which the agents’ owners are willing to negotiate, such as product quality features, delivery conditions, guarantee, etc. (Maes, Guttman, & Moukas, 1999) (Sierra, 2004). In this framework, agents operate following predefined rules and procedures specified by the employed negotiation protocol (Rosenschein, & Zlotkin, 1994), aiming to address the requirements of their human or corporate owners as much as possible. Furthermore, the negotiating agents use a reasoning model based on which their responses to their opponent’s offers are formulated (Muller, 1996). This policy is widely known as the negotiation strategy of the agent (Li, Su, & Lam, 2006). This paper elaborates on the design of negotiation strategies for autonomous agents. The proposed strategies are applicable in cases where the agents have strict deadlines and they negotiate with a single party over the value of a single parameter (single-issue bilateral negotiations). Learning techniques based on MLP and GR Neural Networks (NNs) are employed by the client agents, in order to predict their opponents’ behaviour and achieve a timely detection of unsuccessful negotiations. The proposed NN-assisted strategies have been evaluated and turn out to be highly effective with regards to the duration reduction of the negotiation threads that cannot lead to agreements. The rest of the paper is structured as follows. In the second section, the basic principles of the designed negotiation framework are presented, while the formal problem statement is provided. The third section elaborates on the NN-assisted strategies designed and provides the configuration details of the NNs employed. The fourth section presents the experiments conducted, while the fifth section summarizes and evaluates the results of these experiments. Finally, in the last section, conclusions are drawn and future research plans are exposed.

Key Terms in this Chapter

Generalized-Regression (GR) NN: A GR NN is a special case of a RBF NN with a second linear layer and is often used for function approximation.

Radial Basis Function (RBF): Function that involves a distance criterion with respect to a centre, such as a circle, ellipse or Gaussian.

Neural Network (NN): A network modelled after the neurons in a biological nervous system with multiple synapses and layers. It is designed as an interconnected system of processing elements organized in a layered parallel architecture. These elements are called neurons and have a limited number of inputs and outputs. NNs can be trained to find nonlinear relationships in data, enabling specific input sets to lead to given target outputs.

Bilateral Negotiation: A negotiation procedure, where exactly two parties are involved, i.e. a client and a provider.

Backpropagation algorithm: A supervised learning technique used for training artificial NNs based on the minimisation of the error obtained from the comparison between the desired output and the actual one when applying specific inputs.

Automated Negotiation: It is the process by which group of actors communicate with one another aiming to reach to a mutually acceptable agreement on some matter, where at least one of the actors is an autonomous software agent.

Negotiation Protocol: The set of rules that govern the interactions between the negotiating parties.

RBF NN: It is an artificial NN, the activation functions of which are radial basis functions. It has two layers of processing, where the first maps the input onto each RBF neuron in the other (hidden) layer.

Multi-Layer Perceptron (MLP): A fully connected feedforward NN with at least one hidden layer that is trained using back-propagation algorithmic techniques.

Negotiation Strategy: The reasoning model based on which the negotiating parties formulate their response to their opponent’s offers.