6.2, Approaches To Automated Negotiation

Notes take from Argumentation-Based Negotiation (ABN) (2003), by Iyad Rahwan et al.

1, Game-theoretic Approaches to Negotiation
Game theory is a branch of economics that studies the strategic interactions between self-interested economic agents (and recently, self-interested computational agents).

In game-theoretic analysis, researchers usually attempt to determine the optimal strategy by analysing the interaction as a game between identical participants, seeking its equilibrium…

However, classical game-theoretic approaches have some significant limitations from the computational perspective. Specifically, most these approaches assume that agents have unbounded computational resources and that the space of outcomes is completely known…

2, Heuristic-based Approaches to Negotiation
To address some of the aforementioned limitations of game-theoretic approaches, a number of heuristics have emerged. Heuristics are rules of thumb that produce good enough (rather than optimal) outcomes and are often produced in contexts with more relaxed assumptions about agents’ rationality and resources…

Disadvantages: Firstly, the models often lead to outcomes that sub-optimal because they adopt an approximate notion of rationality and because they do not examine the full space of possible outcomes. And secondly, it is very difficult to predict precisely how the system and the constituent agents will behave…

3, Argumentation-based Approaches to Negotiation
Limitations of conventional negotiation approaches:
- Agents are not allowed to exchange any additional information other than what is expressed in the proposal itself. This can be problematic, for example, in situations where agents have limited information about the environment, or where their rational choices depend on those of other agents.
- Agents’ utilities or preferences are usually assumed to be completely characterised prior to the interaction. Thus an agent is assumed to have a mechanism by which it can assess and compare any two proposals. This is not always the case…
- Agents’ preference over proposals are often assumed to be proper in the sense that they reflect the true benefit the agent receives from satisfying these preferences.
- Agents’ utilities or preferences are assumed to be fixed. One agent cannot directly influence another agent’s preference model, or any of its internal mental attitudes (e.g. beliefs, desires, goals, etc.) that generate its preference model…

Argumentation-based approaches to negotiation attempt to overcome the above limitations by allowing agents to exchange additional information, or to “argue” about their beliefs and other mental attitudes during the negotiation process.

In the context of negotiation, we view an argument as a piece of information that may allow an agent to (a) justify its negotiation stance; or (b) influence another agent’s negotiation stance.

Thus, in addition to accepting or rejecting a proposal, an agent can offer a critique of it. This can help make negotiations more efficient. By understanding why its counterpart cannot accept a particular deal, an agent may be in a better position to make an alternative offer that has a higher change of being acceptable…

Another type of information that can be exchanged is a justification of a proposal, stating why an agent made such a proposal or why the counterpart should accept it. This may make it possible to change the other agent’s region of acceptability or the nature of the negotiation space itself (by introducing new attributes/dimensions to the negotiation object)…

An agent might also make a threat or promise a reward in order to exert some pressure on its counterpart to accept a proposal…

4, Summary
There is no universal approach to automated negotiation that suits every problem domain. Rather, there is a set of approaches, each based on different assumptions about the environment and the agents involved in the interaction…

ABN frameworks are gaining increasing popularity for its potential ability to overcome the limitations of more conventional approaches to automated negotiation. However, such models are typically more complex than their game-theoretic and heuristic counterparts.