Page 263 - Socially Intelligent Agents Creating Relationships with Computers and Robots

246 Socially Intelligent Agents

A) Responsive Mechanism B) Trade−Off Mechanism C) Meta Strategy
1.0 1.0 1.0
x
U(b(x))
U(b) U(b)
U(b)

y
U(b(y))
0 1.0 0 1.0 0 1.0
U(a(x)) U(a) U(a(y)) U(a) U(a)

Figure 30.1. Utility Dynamics of the Mechanisms

ilarity [14] to approximate the preference structure of the negotiation opponent.
It then uses a hill-climbing technique to explore the space of possible contract
trade-offs for a contract that is most likely to be acceptable. The complexity of
this algorithm has been shown to grow linearly with growing numbers of issues
[4].
The details of the algorithms can be found in [3] and [4]. The dynamics of
the contract utility generated by each of the above mechanisms and one possible
combination is given in figure 30.1 A, B and C respectively for the alternating
sequential protocol. The filled ovals are the utility of the offered contracts
from agent to agent from agent ’s perspective, and the unfilled ovals
representtheutilityof theofferedcontractsfrom agent toagent fromagent ’s
perspective. The patterned oval represents the joint utility of the final outcomes.
The pareto-optimal line is given by the curvilinear line connecting the two pairs
of payoffs and . Figure 30.1 A represents a possible execution trace
where both agents generate contracts with the responsive mechanism. Each
offer has lower utility for the agent who makes the offer, but relatively more
utility for the other. This process continues until one of the agents is satisfied

( ), where is the contract offered by agent to

at time . This termination criteria is referred to as the cross-over in utilities.
The responsive mechanism can select different outcomes based on the rate of
concession adopted for each issue (the angle of approach to the outcome point
in figure 30.1 A).
Figure 30.1 B represents another possible utility execution trace where both
agents now generate contracts with the trade-off mechanism. Now each offer
has the same utility for the agent who makes the offer, but relatively more
utility for the other (movement towards the pareto-optimal line). The trade-off
mechanism searches for outcomes that are of the same utility to the agent, but
which may result in a higher utility for the opponent. Once again, this is a
simplification for purposes of the exposition—an offer generated by agent