Information Technology Reference
In-Depth Information
algorithm is not guaranteed to converge to the global optimal allocation as it
can get stuck at a local maxima by clearing a bid that has high
w
(
b
) but is not
to be found in the optimal allocation.
6
Partitioning Based Search
The greedy algorithm produces a non-optimal solution in polynomial time and
the complete search provides the optimal solution in exponential time. Although
the complete algorithm determines the optimal winner in a distributed manner,
there is no parallelism as only one agent is active at any instant. The agents in
the hill-climbing algorithm execute in parallel but they can get stuck at local
maxima. Hence we now present a partitioning based approach. Our main moti-
vation for proposing this approach is to obtain solutions whose quality is better
than solutions produced by greedy approach but where the execution is compa-
rable to the time taken by the greedy algorithm. In this approach, we partition
the goods and the agents perform a complete search within the group (while
ignoring the bids outside the partition). The algorithm proceeds as follows:
1. The controller partitions the agents into different groups. The controller also
selects the
headAgent
of every group.
2. Each agent is provided with its partition information (the linear ordering in
its partition).
3. Each agent deletes the bids that contain any good not present in its partition.
4. The controller initiates the Complete-Search algorithm in every partition.
In order to explain how the controller partitions the agents, we first define
the following:
Definition 2 (Graphical representation of Combinatorial Auction).
A
combinatorial auction can be represented as a graph G
=(
N, E
)
,whereN is the
set of nodes and E is the set of edges. Each node corresponds to a good on sale.
An edge exists between any two nodes if they are present in the same bid.
It is not always possible to divide the goods into disjoint partitions (where there is
no edge between partitions). There could be bids on goods in different partitions.
Currently, we use a greedy approach to address this issue. The agents do not
consider the bids that have a good that is not present in its partition. This
approach will result in an optimal solution only if the ignored bids are not part
of the optimal allocation.
7
Negotiation Based Approaches
The search-based approaches provided in the earlier sections ignored the issue of
splitting revenue among multiple sellers. That is unrealistic in cases where, for
example, one agent has a good that is in much more demand than all the other
goods in the combinatorial bids that it is in. This problem has been identified
