Information Technology Reference
In-Depth Information
complete
greedy
part. 4
part. 8
part. 16
part. 32
part. 64
4e+06
1e+06
3e+05
7e+04
2e+04
4e+03
1e+03
3e+02
6e+01
10
20
30
40
50
60
Number of Goods
Fig. 6.
Total number of messages sent
that they have entered a cycle. This type of implementation is the one we have
used for the test results in section 8.
We do not yet have a distributed algorithm that can implement this method.
One problem is the fact that the calculation of an agent's payments requires
knowledge of the
P
con
values for all the agent's neighbors. It is unclear to us
how an agent might come to acquire this knowledge if we assume that all agents
are selfish. Still, since this method is predicts the behavior of humans, who do
not know their opponents'
P
con
values, we are confident that we will come up
with an appropriate distributed algorithm in the near future.
8
Preliminary Results
The input data for our algorithms was generated using CATS [18] using random
distribution. Figure 5, compares the value of allocation for the three search
algorithms. The first point on x-axis consists of 10 goods and 50 bids (thereafter
the goods and bids increment by 5 and 50 respectively). The values shown in the
figure are the average of 25 runs. As expected, the complete algorithm computes
the solution with best revenue. Similarly, figures 6 and 7 compare the messages
passed and the execution time (in clock ticks
6
) respectively for the three search
algorithms. The complete search algorithm takes exponential time
O
(
n
|b|
)to
provide the optimal allocation. The greedy algorithm takes linear time
O
(
|
b
|
),
where
n
is the number of goods and
is the number of bids.
Figure 8 shows the value of the allocations produced by mMCP and iterated-
resistance equations. The simulations were run on randomly generated data on
NetLogo [19]. In each run, the protocol and the iterations were run for 10 cy-
cles. Even though our solution using resistance equations is not guaranteed to
converge, the results are very promising because the algorithm seems to produce
|
b
|
6
The clock tick was chosen to be long enough for the agents to process and execute
a single iteration of the search algorithm.
