STRATUM: A METHODOLOGY FOR DESIGNING HEURISTIC AGENT NEGOTIATION STRATEGIES

Abstract

Automated negotiation is a powerful (and sometimes essential) means for allocating resources among self-interested autonomous software agents. A key problem in building negotiating agents is the design of the negotiation strategy, which is used by an agent to decide its negotiation behavior. In complex domains, there is no single, obvious optimal strategy. This has led to much work on designing heuristic strategies, where agent designers usually rely on intuition and experience. In this article, we introduce STRATUM, a methodology for designing strategies for negotiating agents. The methodology provides a disciplined approach to analyzing the negotiation environment and designing strategies in light of agent capabilities and acts as a bridge between theoretical studies of automated negotiation and the software engineering of negotiation applications. We illustrate the application of the methodology by characterizing some strategies for the Trading Agent Competition and for argumentation-based negotiation.

We are grateful to Minghua He for providing us with details on the SouthamptonTAC-02 strategy. During this work, Iyad Rahwan was partially supported by a Melbourne Research Scholarship (MRS) from the University of Melbourne. The general structure of the methodology and the characterization of negotiation capabilities arose from discussions between Peter McBurney and Iyad Rahwan while the latter was a visitor at the Department of Computer Science, the University of Liverpool, UK, funded by a Melbourne University PORES award. Peter McBurney acknowledges partial financial support from the European Commission under Project ASPIC (IST-FP6-002307).

Notes

Rational in the sense that they try to maximize their expected utilities, that their preferences satisfy certain axiomatic conditions, and that their decisions assume that other agents are also rational.

Some work has been done on calculating equilibrium strategies while taking into account the cost of computation (Larson and Sandholm, 2001). However, this approach has been applied to a particular, relatively simple bilateral bargaining setting, and it is not clear yet how this approach generalizes to more complex negotiations (e.g., involving multiple concurrent negotiations).

The name illustrates that this methodology does not follow the traditional game-theoretic approach. The word stratum is the singular of strata (a set of layers) and refers to the compositional construction of strategies from simple tactics and capabilities.

This hierarchical objectives structure has a structural similarity to the landmarks theory of conversation protocols of Kumar et al. (2002). However, our approach concerns only the objectives of an individual agent and not the joint goals of all participants to an interaction.

When describing the negotiation objectives and strategies, we use the terms “objective” and “subobjective” deliberately in order to distinguish them from the agent's own internal “goals” and “sub-goals.”

In the latter case, the template above would be referred to as a strategy template.

For the interested reader, Greenwald (2003) provides a comprehensive description.

Based on personal communication with the designers of Southampton TAC-02 (He, 2004).

That is, a risk-averse behavior.

In this tactic, the agent buys most of the flights earlier and will only change travel plans if a significant improvement can be obtained.

For brevity, we do not present the full specification of the argumentation system used. The interested reader may refer to Rahwan (2004).

Note that this uses a different, and simpler, formula to the one used in TAC.

Of course, this dialogue assumes that A ₁ prefers to sell a ticket for $250 than hire out a car for $400.