Information Technology Reference
In-Depth Information
complete
greedy
part. 4
part. 8
part. 16
part. 32
part. 64
1e+06
3e+04
1e+03
3e+01
10
15
20
25
30
35
40
45
50
55
60
Number of Goods
Fig. 7.
Total time spent by algorithm
140
optimal
Iterated-Resistance
Modified MCP
120
100
80
60
40
20
0
1
2
3
4
5
6
7
8
9
10
Run #
Fig. 8.
Value of the solution found by mMCP, iterated-resistance equations, and the
global optimum
high-valued allocations (even though suboptimal) for many cases and always in
a short period of time.
9
Discussion and Future Work
We have presented the new problem of distributed winner determination in com-
binatorial auctions which is an instance of a distributed search problem and,
when selfish agents are assumed, is an instance of a distributed algorithmic
mechanism design problem. We presented and compared several algorithms for
solving the problem under various circumstances. Our results are summarized
in Table 1.
The complete algorithm performs a linear search to determine the optimal
winner. This algorithm works in the absence of a centralized auctioneer. However,
the running time will be of the order of total number of feasible allocations. This
is because, even though it is distributed, the agents do not execute in parallel. At
