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

248 Socially Intelligent Agents

complex non-linearities involved in the system. The solution to these problems
are briefly outlined below in a model of negotiation that departs from the more
deductive model outlined above [5].
In this model a contract is an dimensional boolean vector where
, represents the presence or absence of a “contract clause” . The con-
tract search policy is encoded in the negotiation protocol. Because generating
contract proposals locally is both knowledge and computationally expensive
we adopt an indirect single text protocol between two agents by delegating the
contract generation process to a centralized mediator [9]. A mediator proposes

a contract at time . Each agent then votes to accept or reject . If both vote

to accept, the mediator iteratively mutates the contract and generates .
If one or both agents vote to reject, a mutation of the most recent mutually
acceptable contract is proposed instead. The process is continued until the util-
ity values for both agents become stable (i.e. until none of the newly contract
proposals offer any improvement in utility values for either agent). Note that
this approach can straightforwardly be extended to party (i.e. multi-lateral)
negotiation. The utility of the contract to an agent is defined as the linear
combination of all the pairwise influences between issues.
Two computationally inexpensive decision algorithms were evaluated in this
protocol: a hillclimber and a simulated annealer . A hillclimber only accepts a
contract if and only if the utility of the contract increases monotonically when
an issue is changed. However, this steepest ascend algorithm is known to be
incapable of escaping local maxima of the utility function. The other decision
algorithm is based on the knowledge that search success can be improved by
adding thermal noise to this decision rule [6]. The policy of decreasing
with time is called simulated annealing [6]. Simulated annealing rule is known
to reach utility equilibrium states when each issue is changed with a finite
probability and time delays are negligible.
To evaluate these algorithms simulations were run again with two agents
and . The contract length was set to (corresponding to a space of ,
or roughly possible contracts) where each bit was initialized to a value
randomly with a uniform distribution. The initial temperature was
set to and decreased in steps of to . Final average utilities were collected
for runs for each temperature decrement.
The left figure in figure 30.2 shows the observed individual payoffs for tests
examining the relationship of C-Q with local utility metric of Q. One observa-
tion is that if the other agent is a local hill-climber, an agent is then individually
better off being a local hill-climber, but fares very badly as local annealer. If
the other agent is an annealer, the agent fares well as an annealer but does even
better as a hillclimber. The highest social welfare, however, is achieved when
both agents are annealers. This pattern can be readily understood as follows. At
high virtual temperature an annealer accepts almost all proposed contracts in-