The main challenges

The main difficulty in the development of automated negotiators is that in order to negotiate proficiently with a human counterpart, they must be able to work in settings with both opponents with bounded rationality and incomplete information. The difficulty can also stem from the fact the humans are also influenced by behavioral aspects and by social preferences that hold between players (such as inequity-aver-sion2 and reciprocity4). Thus, it is difficult to predict individual choices.

Tackling the issues of bounded rationality and incomplete information is a complex task. To achieve this, an automated agent is required to have two interdependent mechanisms. The

first is a decision-making component that works via modeling human factors. This mechanism is in charge of generating offers and deciding whether to accept or reject offers made by the opponent. The challenge behind this mechanism does not lie in the computational complexity of making good decisions but rather in reasoning about the psychological and social factors that characterize human behavior. The second component is learning, which allows the agent to infer the opponent’s preferences and strategies, based on his actions.

Another inherent problem in the design of the automated agent is the ability to generalize its behavior. While humans can negotiate in different set-

figure 3. Architecture of a general agent’s design.

Domain Knowledge and specifications

Past sessions/interactions

Agent’s strategy and Tactics

Decision-making:
qualitative,
randomization

opponent Modeling

figure 4. The Diplomacy game.

tings and domains, when designing an automated agent a decision should be made whether the agent should be a general-purpose negotiator, that is, will be able to successfully negotiate in many settings and be domain-independent, 24 or the agent will only be suitable for one specific domain (for example, Ficici and Pfeffer, 8 Kraus and Lehmann22). Perhaps the advantage of the agent’s specificity is the ability to construct better strategies that could allow it to achieve better agreements, as compared to a more general-purpose negotiator. This is due to the fact that the specificity allows the designer to debug the agent’s strategy more carefully and against more test cases. By doing so, the designer can fine-tune the agent’s strategy and allow for a more proficient automated negotiator. Agents that are domain independent, on the other hand, are more difficult to test against all possible cases and states.

The issue of trust also plays an important role in negotiations, especially when the other side’s behavior is unpredictable. Successful negotiations depend on the trust established between all parties, which can depend on cheap-talk during negotiations (that is, unverifiable information with regard to the other party’s private information7) and the introduction of unenforceable agreements. Based on the actions and information each party can update its reputation (for better or for worse) with regard to the other party and thus build trust between the sides. Some of the systems we review below do allow cheap-talk and unenforceable agreements. Building trust can also depend on past and future interactions with the other party (for example, one-shot interaction or repeated interactions). Due to limited space, we do not cover the issue of trust in detail. Readers are encouraged to refer to Ross31 for a comprehensive review on this topic.

Another important issue is how automated agents can be evaluated and compared. Such an evaluation is important in order to select the most appropriate agent for the task at hand. Yet, no single criteria is defined. The answer to the questions of “what constitutes a good negotiator agent?” is multifaceted. For example, is a good agent an agent that:

Achieves a maximal payoff when ˲ matched with human negotiators? But