Information Technology Reference
In-Depth Information
Algorithms for Distributed Winner
Determination in Combinatorial Auctions
Muralidhar V. Narumanchi and Jos´eM.Vidal
Computer Science and Engineering
University of South Carolina
Columbia, SC. 29208
narumanc@cse.sc.edu
,
vidal@sc.edu
Abstract.
The problem of optimal winner determination in combinato-
rial auctions consists of finding the set of bids that maximize the revenue
for the sellers. Various solutions exist for solving this problem but they
are all centralized. That is, they assume that all bids are sent to a cen-
tralized auctioneer who then determines the winning set of bids. In this
paper we introduce the problem of distributed winner determination in
combinatorial auctions which eliminates the centralized auctioneer. We
present a set of distributed search-based algorithms for solving this prob-
lem and study their relative tradeoffs.
1
Introduction
In a combinatorial auction the buyers bid on bundles of items. After clearing,
each buyer receives either the entire bundle he bid on or nothing. Combinato-
rial auctions are often preferred over sequential auctions because bidders can
express complementarity and substitutability of their choices within the bids.
The optimal winner determination problem in a combinatorial auction involves
finding the set of bids that maximizes the revenue generated. This problem
is known to be an
NP
-Hard problem [1]. Various centralized approaches us-
ing
A
∗
[2], dynamic programming [1], integer programming [3], linear program-
ming [4], and approximation techniques [5] have been proposed for determining
the optimal and approximately-optimal solution. All these algorithms assume the
existence of a centralized auctioneer who collects all the bids and computes the
set of winning bids. All these algorithms also fail to address the question of
revenue division amongst the winning goods. In this paper we investigate the
problem of distributed winner determination, that is, the determination of the
set of winning bids in the absence of a centralized auctioneer. We provide some
distributed search-based solutions as well as a negotiation-based approach which
also performs revenue division.
Our research is motivated by a vision of a future Internet-based distributed
electronic marketplace. The system would be a peer-to-peer system, without the
need for a centralized auctioneer, and would have to provide the proper incentives
for selfish agents to participate and perform their duties as required. For such a
system to exist we will need, among other technologies, protocols that distribute
