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

Multi-Agent Contract Negotiation 247

may indeed have decreasing utility to agent (arrow moving away from the
pareto-optimal line) if the similarity function being used does not correctly
induce the preferences of the other agent.
Finally, agents can combine the two mechanisms through a meta-strategy
(figure 30.1 C). One rationale for the use of a meta-strategy is reasoning about
the costs and benefits of different search mechanisms. Another rationale, ob-
servable from the example shown in figure 30.1 B, is that because the local
utility information is private agents can not make an interpersonal comparison
of individual utilities in order to compute whether a pareto optimal solution
has indeed been reached. In the absence of a mediator the lack of such global
information means negotiation will fail to find a joint solution that is acceptable
to both parties. In fact agents enter a loop of exchanging the same contract
with one another. Figure 30.1 C shows a solution where both agents imple-
ment a responsive mechanism and concede utility. This concession may, as
shown in figure 30.1 C, indeed satisfy the termination conditions of the trade-
off mechanism where offers cross-over in utilities. Alternatively, agents may
resume implementing a trade-off algorithm until such a cross-over is eventually
reached or time limits are reached. In general, the evaluation of which search
should be implemented is delegated to a meta-level reasoner whose decisions
can be based on bounding factors such as the opponent’s perceived strategy,
the on-line cost of communication, the off-line cost of the search algorithm,
the structure of the problem or the optimality of the search mechanism in terms
of completeness (finding an agreement when one exists), the time and space
complexity of the search mechanism, and the expected solution optimality of
the mechanism when more than one agreement is feasible.

3. A Mediated Game

In the above model the issues being negotiated over are assumed to be inde-
pendent, where the utility to an agent of a given issue choice is independent of
what selections are made for other issues. The utility function that aggregates
the individual utilities under this assumption is then taken to be linear. This
assumption significantly simplifies the agents’ local decision problem of what
issue values to propose in order to optimize their local utility. Optimization of
such a linear function is achieved by hillclimbing the utility gradient. However,
real world contracts, are highly inter-dependent. When issue interdependencies
exist, the utility function for the agents exhibits multiple local optima. Multi-
optimality results in firstly a more extensive bounded rationality problem since
not only is computation limited but now also both local and global knowledge
are limited. Local knowledge is limited because the agent now has to know and
optimize a much more complicated utility function. Secondly, a methodolog-
ical change from deductive models to simulation studies is needed due to the