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

Multi-Agent Contract Negotiation 245

“reachable”. Call the set of feasible outcomes , containing those agreements
that are individually rational and bounded by the pareto optimal line [13].
An agreement is individually rational if it assigns each agent a utility that is at
least as large as the agent can guarantee for itself from the conflict outcome .
Pareto optimality is informally defined as the set of outcomes that are better
for both agents [1]. It is often used as a measure of the efficiency of the social
outcome. Given the game , the protocol, or “rules of encounter” [8],
normatively specifies the process of negotiation. The protocol chosen for this
game is the alternating sequential model in which the agents take turns to make
offers and counter offers [10]. The protocol terminates when the agents come to
an agreement or time limits are reached or, alternatively, when one of the agents
withdraws from the negotiation. This distributed, iterative and finite protocol
was selected because it is un-mediated, supports belief update and places time
bounds on the computational resources that can be utilized.
However, like chess for example, agents can have different negotiation strate-
gies given the normative rules of the game. Two heuristic distributed and au-
tonomous search strategies have been developed whose design has been moti-
vated by the knowledge and computation boundedness arguments given above.
One parametric mechanism, the responsive mechanism, is a mechanism that
conditions the decisions of the agent directly to its environment such as the
concessionary behaviour of the other party, the time elapsed in negotiation, the
resources used, etc. [3]. However, the mechanism is known to have several
limitations [4]. In some cases agents fail to make agreements, even though there
are potential solutions, because they fail to explore different possible value com-
binations for the negotiation issues. For instance, a contract may exist in which
the service consumer offers to pay a higher price for a service if it is delivered
sooner. This contract may be of equal value to the consumer as one that has a
lower price and is delivered later. However from the service provider’s point
of view, the former may be acceptable and the latter may not. The responsive
mechanism does not allow the agents to explore for such possibilities because
it treats each issue independently and only allows agents to concede on issues.
A second mechanism, called the trade-off mechanism, was developed to ad-
dress the above limitations and consequently select solutions that lie closer to
the pareto-optimal line, again in the presence of limited knowledge and compu-
tational boundedness [4]. Intuitively, a trade-off is where one party lowers its
utility on some negotiation issues and simultaneously demands more on others
while maintaining a constant overall contract utility. This, in turn, should make
agreement more likely and increase the efficiency of the contracts. An algo-
rithm has been developed that enables agents to make trade-offs between both
quantitative and qualitative negotiation issues, in the presence of information
uncertainty and resource boundedness for multi-dimensional goods [4]. The
algorithm computes dimensional trade-offs using techniques from fuzzy sim-