Information Technology Reference
In-Depth Information
set of goods for bid b i , b i to refer to the price of bid b i and g i torefertothelist
of bids in which good g i is present.
Each consumer can place any number of bids 1 . The bid can be for either a
single good or a combination of goods. For example, consumer c i can place a bid
b k on the bundle
{
g 1 ,g 4 ,g 7 }
for a value of v 1 and another bid b j on bundle
{
g 2
}
for value v 2 .
Definition 1 (Feasible Allocation). An allocation A ofgoodsisafeasible
allocation if and only if no two bids in the allocation share a good.
The set of all feasible allocations, given B ,isgivenby F which is
|∀ b i ,b k ∈A,i = k b i
b k =
F
≡{
b
B
∅}
.
(1)
The value of an allocation A is given by
V ( A )=
b∈A
b p .
(2)
The revenue maximizing solution A is the feasible allocation that maximizes
the total price paid for all the goods, that is A =argmax A⊆F V ( A ).
In distributed combinatorial auctions there is no centralized auctioneer who
collects all the bids. Instead, we assume that each good for sale is represented
by an agent. When a consumer places a bid b i , the bid is passed on to b i which
are the agents representing the goods present in the bids 2 . Any agent g i can
communicate with any other agent. Thus each agent has the list of bids in which
it is present.
We further assume that a bid can be cleared if and only if all the agents in
the bid agree to clear it. The final agreement reached by the agents is final and
binding. We also assume that the agents don't have a reservation price for their
goods and that goods can be sold only once. Finally, some of the algorithms we
will introduce make use of w ( b ) which is the average price per good for bid b .
That is, w ( b )= b p
|b g
.
The question we try to answer is: How can the agents determine the set of
winning bids in the absence of the centralized controller?
|
4
Complete Search Algorithm
In a complete search the agents search over the space of all the possible alloca-
tions to determine the optimal allocation. Since there is no centralized auctioneer
that has global information, the agents must pass messages to each other and
perform the search in a distributed manner.
In this algorithm we assume that the agents possess a linear ordering such
that every agent has a child variable which points to its child, except for the
leaf node who sets this variable to
. Each agent also maintains the following
variables:
1 In our paper, we assume that each consumer places a single bid.
2 We use the terms “agent” and “good” interchangeably.
Search WWH ::




Custom Search