Information Technology Reference
In-Depth Information
5000
complete
greedy
part. 4
part. 8
part. 16
part. 32
part. 64
4500
4000
3500
3000
2500
2000
1500
1000
500
0
10
20
30
40
50
60
Number of Goods
Fig. 5.
Value of the winning set of bids
example, if nodes
A
and
B
want to divide some resource between them then the
amounts that
A
and
B
will agree on (
P
A
and
P
B
respectively) can be obtained
by solving equations (3) and (4) for
P
A
and
P
B
. In these equations,
P
co
A
is the
amount that
A
makes if it has a confrontation with
B
(i.e., it doesn't exchange
with
B
)and
P
max
A
is the maximum that
A
can make from exchange with
B
.
P
max
A
P
max
B
−
P
A
−
P
B
=
(3)
P
con
A
P
con
B
P
A
−
P
B
−
P
A
+
P
B
=
TotalRevenue
(4)
Equation (3) tells us that the resistance of
A
must be equal to the resistance of
B
. Equation (4) tells us that the sum of the payments must be equal to the total
revenue. We can easily generalize these equations to
n
agents by simply adding
another resistance equation for each agent and insisting that all resistances must
be the same
5
. In all cases we end up with
n
+1 equations of
n
variables, so we
can solve for the payments.
The iterated equi-resistance method [15] tells us to start out with initial pay-
ments for the agents equal to an even distribution of the total revenue and then
iteratively solve the resistance equations for each agent in order to find its pay-
ment given those of the other agents. We are to continue doing this for several
rounds or until the system stabilizes. At some point, the agents decide to take
the deal (bid) for which they are to receive the highest payment.
This method is easy to implement in a simulator. All we need to do is at each
time step calculate the agents' payments by solving the equi-resistance equations.
We can then continue to do this until either the payments stabilize or we detect
5
However, we must stress that studies with human subjects only consider binary
negotiations. As such, there is no empirical evidence to suggest that human behavior
can be predicted using the equi-resistance equation for negotiations among three or
more agents.
