Communications - January 2010

In order for the Colored-Trails Agent to model the opponent, prior knowledge regarding the behavior of humans is needed. The learning mechanism requires sufficient human data for training and is currently limited to one domain only.

Gal10 also examines automated agent design in the domain of the Colored Trails. They present a machine-learning approach for modeling human behavior in a two-player negotiation, where one player proposes a trade to the other, who can accept or reject it. Their model tries to predict the reaction of the opponent to the different offers, and using this prediction it determines the best strategy for the agent. The domain on which Gal et al. tested their agent can also be viewed as a Cliff-Edge environment, more complex than the Ultimatum Game, upon which Katz and Kraus evaluated their agent. 16

Gal et al. show that the proposed model successfully learns the social preferences of the opponent and achieves better results than the Nash equilibrium, Nash bargaining computer agents, and human players.

We now continue with agents that are domain-independent, and we propose an agent that has greater generality than the aforementioned agents.

The Guessing Heuristic Agent Jonker et al. 15 deal with bilateral multi-issue and multi-attribute negotiations that involve incomplete information. The negotiation follows the alternating offer protocol and is conducted once with each opponent. Jonker designed a generic agent that uses a “guessing heuristic” in the buyer-seller domain.a This heuristic tries to predict the opponent’s preferences based on its offers’ history. This is under the assumption the opponent’s utility has a linear function structure. Jonker et al. assert that this heuristic allows their agent to improve the outcome of the negotiations. Regarding the offer generation mechanism, they use a concession mechanism to obtain the next offer. In their experiments, the automated agent

a Although Jonker et al. discuss and present results on one domain only, they state their model is generic and has also been applied in other domains.

if we look into
the design elements
of all the agents
mentioned in
this article, we
cannot find one
specific feature
that connects them
or can account
for their good
negotiation skills.

acts as a proxy for the human user. The user is involved only in the beginning when he inputs the preference parameters. Then the agent generates the offers and the counteroffers. When comparing negotiations involving only automated agents with negotiations involving only humans, the agents usually outperformed the humans (in the buyer’s role). Yet, in an additional experiment they matched humans versus agent negotiators. In this experiment, humans only played the role of the buyer. When comparing the human vs. agent negotiations to that of only automated agents, the humans attained somewhat better results than the agents (in the buyer’s role), based on the average utilities. The authors believe this should be accounted to the fact that humans forced the automated negotiators to make more concessions then they themselves did.

The next agent also deals with bilateral multi-issue negotiations that involve incomplete information. Nonetheless the negotiation protocol is richer than that of the Guessing Heuristic agent.

The QOAgent

The QOAgent24 is a domain-independent agent that can negotiate with people in environments of finite horizon bilateral negotiations with incomplete information. The negotiations consider a finite set of multi-attribute issues and time constraints. Costs are assigned to each negotiator, such that during the negotiation process, the negotiator might gain or lose utility over time. If no agreement is reached by a given deadline a status quo outcome is enforced. A negotiator can also opt-out of the negotiation if it decides that the negotiation is not proceeding in a favorable manner. Similar to the negotiation protocol in the Diplomat agent’s domain, the negotiation protocol in the QOAgent’s domain extends the model of alternating offers such that each agent can perform up to M > 0 interactions with the opponent agent during each time period. In addition, queries and promises are allowed that add unenforceable agreements to the environment.