Information Technology Reference
In-Depth Information
Table 1.
Algorithm Comparison
Algorithm
Opti-
mal?
Agents
Time
Revenue
Split?
Always
Converges?
Complete
Search
Yes
Coopera-
tive
Exponential
No
Yes
Hill Climbing
No
Coopera-
tive
Linear:
O
(
|b|
)
No
Yes
Partitioning
No
Coopera-
tive
Dependent on
partition size
No
Yes
mMCP
No
Selfish
Linear:
O
(
|b|
)
Yes
Yes
Equiresis-
tance
No
Selfish
Not defined
Yes
No
any given time only one agent is performing the computation. The hill climbing
algorithm on the other hand does not guarantee an optimal solution but performs
much faster. More tests need to be done in order to determine the expected
quality of the solution found by the hill climbing algorithm.
The partitioning based approach ignores the bids outside partitions. This re-
sults in sub-optimal solution if the ignored bids are part of the optimal solution.
One of the reasons our partitioning approach performed worse than hill-climbing
(fig. 5) is that the goods were randomly partitioned. One way to improve the
quality of solution in the general case would be to partition the strongly con-
nected goods together, i.e., try to put goods that have lot of common bids in one
partition. We intend to extend our work to create dynamic distributed partition-
ing algorithms that can tailor their partitioning strategy to the characteristics
of the set of bids under consideration.
The mMCP that we proposed is again similar to a greedy approach. It can
converge to a local maximum and is always guaranteed to converge. We are
currently testing it to see if we can predict what are the characteristics of the
solution that it converges to. We are also studying modifications of the algorithm
that force convergence to optimal as well as the tradeoffs associated with using
different step sizes and other shortcuts for faster convergence.
Our study of the applicability of the NET equations is preliminary. We note
that these equations can be applied only if agents' know their neighbors'
P
con
values—an unrealistic assumption in most cases. Another problem we face is the
fact that the algorithm does not always converge. We are studying possible ways
of either forcing convergence or determining a priori if the problem is one that
will converge. Still, we are attracted to the fact that the equi-resistance equa-
tions have been shown to model the behavior of humans. We believe that the
widespread adoption of a peer-to-peer agent-based marketplace requires agents
that behave as humans. That is, if a user notices his agent either gives up negoti-
ation too soon or is too aggressive in its negotiations then the user will likely not
use that system. We see the possibility of a whole research program dedicated to
building agents that negotiate, not necessarily optimally, but as humans would.
In summary, the problem of distributed winner determination in combinatorial
auctions is an important problem whose solution will enable the construction of
