Information Technology Reference
In-Depth Information
the computational task of winner determination. But, since the agents perform-
ing the computation have an interest in the outcome of the computation and
might try to manipulate it, we need protocols that provide the correct incentives
to agents and prevent them from manipulating the outcome. As such, our prob-
lem is an instance of a distributed algorithmic mechanism design problem [6,7].
Hence it is also essential that we address the issue of revenue distribution among
the sellers in each winning combinatorial bid, an issue that has not been ad-
dressed by any of the centralized winner determination algorithms we have found.
Specifically, we assume that each agent has a good for sale and receives com-
binatorial bids from prospective buyers. The agents must then implement some
protocol which will lead to the distributed calculation of the set of winning bids.
We consider both the case where the agents are cooperative and when they
are selfish. A system with cooperative agents could arise if all the agents are
owned by the same entity or if the participants have previously arrived at an
off-line agreement. Selfish agents more closely simulate the selfish interests of
their human counterparts who want to maximize their profit.
We start by covering some of the past work on combinatorial auctions in sec-
tion 2. Section 3 formally defines the distributed combinatorial auctions problem.
Sections 4, 5 and 6 give a complete algorithm, a simple hill-climbing algorithm
and a partitioning-based algorithm, respectively. Section 7 provides a negotiation
based approach. Finally, section 8 shows our test results and section 9 discusses
the future work.
2
Related Work
Sandholm [2] has given an algorithm for calculating the optimal set of bids in a
combinatorial auction using an implementation of
A
∗
. Hoos and Boutilier have
provided a solution using stochastic local search [8]. Rothkopf et al. provides a
solution using dynamic programming [1]. Fujishima et al. proposes one method
to speed up the search by structuring the search space and a heuristic method
that lacks optimality guarantees but performs well on average [9]. All these
algorithms are centralized.
In the area of multiple agents operating simultaneously in a market setting,
Preist provides an algorithm for agents that participate in multiple English auc-
tions [10,11]. Wellman
et. al.
[12] use a market mechanism to solve a decentralized
scheduling problem. Both solve different problems from ours. The reader new to
combinatorial auctions can read the survey provided by [13].
3
Problem Description
A distributed combinatorial auction is defined as a set goods
G
where
g
i
∈
G
and
|
G
|
=
n
, a set of consumers
C
where
c
i
∈
C
and
|
C
|
=
k
, and a set of bids
B
where
b
i
∈
B
.Eachbid
b
i
is a tuple
{
c, g, p
}
where
c
is the consumer who placed
the bid,
g
G
is the set of goods being bid on, and
p
is the bid price. There is
no centralized auctioneer who collects these bids. We will use
b
i
to refer to the
⊆
