5, Automated Negotiation

Notes taken from ‘Automated Negotiation: Prospects, Methods and Challenges’ (2001), by N. R. Jennings et al.

“… This paper is not meant as a survey of the field of automated negotiation. Rather, the descriptions and assessments of the various approaches are generally undertaken with particular reference to work in which the authors have been involved…”

The major contribution of this paper has been to:
- Examine the space of negotiation opportunities for autonomous agents;
- Identify and evaluate some of the key techniques;
- Highlight some of the major challenges for future automated negotiation research.
- Lay the foundations for building flexible (persuasive) negotiators.
- Argue that automated negotiation is a central concern for multi-agent systems research.
- Develop a generic framework for classifying and viewing automated negotiations, and then using it to discuss and analyse the three main methods of approach that have been adopted to automated negotiation.

1, Introduction
Agent interactions can vary from simple information interchanges, to requests for particular actions to be performed and on to cooperation and coordination. However, perhaps the most fundamental and powerful mechanism for managing inter-agent dependencies at run-time is negotiation – the process by which a group of agents come to a mutually acceptable agreement on some matter…

Automated negotiation research can be considered to deal with three broad topics:
- Negotiation Protocols: the set of rules that govern the interaction…
- Negotiation Objects: the range of issues over which agreement must be reached…
- Agents’ Decision Making Models: the decision making apparatus the participants employ to act in line with the negotiation protocol in order to achieve their objectives…

2, A generic framework for automated negotiation
Negotiation can be viewed as a distributed search through a space of potential agreements… For a given negotiation, the participants are the active components that determine the direction of the search…

… The minimum requirement of a negotiating agent is the ability to make and respond to proposals… However, this can be very time-consuming and inefficient since the proposer has no means of ascertaining why the proposal is unacceptable, nor whether the agents are close to an agreement, nor in which dimension/direction of the agreement space it should move next…

… The recipient needs to be able to provide more useful feedback on the proposals it receives, in the form of a critique (comments on which parts of the proposal the agent likes or dislikes) or a counter-proposal (an alternative proposal generated in response to a proposal)…

On their own, proposals, critiques and counter-proposals mean that agents, for example, cannot justify their negotiation stance or persuade one another to change theirs. On the other hand, in argumentation-based negotiation, the negotiator is seeking to make the proposal more attractive (acceptable) by providing additional meta-level information in the form of arguments for its position.

Arguments have the potential to increase the likelihood (by persuading agents to accept deals that may previously have rejected) and/or the speed (by convincing agents to accept their opponent’s position on a given issue) of arguments being reached. Common categories of arguments include:
- Threats (failure to accept this proposal means something negative will happen to you);
- Rewards (acceptance of this proposal means something positive will happen to you);
- Appeals (you should prefer this option over that alternative for some reason).

3, Game theoretic models
Game-theory is a branch of economics that studies (analyses and formalises) interactions between self-interested agents… In order for an agent to make the choice that optimises its outcome, it must reason strategically (i.e. take into account the decisions that other agents may make, and must assume that they will act so as to optimise their own outcome).

… It turns out that the search space of strategies and interactions that needs to be considered has exponential growth, which means that the problem of finding an optimal strategy is in general computationally intractable…

Game theoretic techniques can be applied to two key problems:
1. The design of an appropriate protocol that will govern the interactions between the negotiation participants. [1]
2. The design of a particular (individual-welfare maximising) strategy (the agents’ decision making models) that individual agents can use while negotiating.

Despite the advantages, there are a number of problems associated with the use of game theory when applied to automated negotiation:
- Game theory assumes that it is possible to characterise an agent’s preferences with respect to possible outcomes… With more complex (multi-issue) preferences, it can be hard to use game theoretic techniques.
- The theory has failed to generate a general model governing rational choice in interdependent situations…
- Game theory models often assume perfect computational rationality meaning that no computation is required to find mutually acceptable solutions within a feasible range of outcomes. Furthermore, this space of possible deals (which includes the opponents’ information spaces) is often assumed to be fully known by the agents, as is the potential outcomes values… Even if the joint space is known, knowing that a solution exists is entirely different to knowing what the solution actually is.

3, Heuristic approaches
This is the major means of overcoming the aforementioned limitations of game theoretic models. Such methods acknowledge that there is a cost associated with computation and decision making and so seek to search the negotiation space in a non-exhaustive fashion. Thus aiming to produce good, rather than optimal solutions. The key advantages can be stated as follows:
- the models are based on realistic assumptions; hence they provide a more suitable basis for automation and they can, therefore, be used in a wider variety of application domains;
- the designers of agents, who are not wedded to game theory, can use alternative, and less constrained, models of rationality to develop different agent architectures.
The comparative disadvantages are:
- the models often select outcomes (deals) that are sub-optimal; this is because they adopt an approximate notion of rationality and because they do not examine the full space of possible outcomes;
- the models need extensive evaluation, typically through simulations and empirical analysis, since it is usually impossible to predict precisely how the system and the constituent agents will behave in a wide variety of circumstances.

4, Argumentation-based approaches
The basic idea is to allow additional information to be exchanged, over and above proposals. This information can be of a number of different forms, all of which are arguments which explain explicitly the opinion of the agent making the argument.

In addition to rejecting a proposal, an agent can:
- Offer a critique of the proposal, explaining why it is unacceptable (thus identifying an entire area of the negotiation space as being not worth exploring by the other agent);
- Accompany a proposal with an argument which says why the other agent should accept it (thus changing the other agent’s region of acceptability).

… Agents may not be truthful in the arguments that they generate. Thus, when evaluating an argument, the recipient needs to assess the argument on its own merits and then modify this by its own perception of the argument’s degree of credibility in order to work out how to respond.

…Using argumentation in real agents means handling the complexities of the agents’ mental attitudes, communication between agents, and the integration of the argumentation mechanisms into a complex agent architecture [3].

For the future, two main areas of work remain:
1. The definition of suitable argumentation protocols, that is, sets of rules that specify how agents generate and respond to arguments based upon what they know. [6, 7]
2. The transition between the underlying negotiation protocol and the argumentation protocol. When is the right time to make this transition, when is it right to start an argument?

… the problem with such methods is that they add considerable overheads to the negotiation process, not least in the construction and evaluation of arguments…

5, Conclusions
Much research still needs to be performed in the area of automated negotiation, including:
- Extending and developing the specific approaches that have been discussed herein and even developing new methods…
- Development of a best practice repository for negotiation techniques. That is, a coherent resource that describes which negotiation techniques are best suited to a given type of problem or domain (much like the way that design patterns function in object-oriented analysis and design)…
- Advancing work on knowledge elicitation and acquisition for negotiation behaviour. At present, there is virtually no work on how a user can instruct an agent to negotiate on their behalf…
- Developing work on producing predictable negotiation behaviour…