Information Technology Reference
In-Depth Information
literature, and employed in practice.
2
For example, van Hoesel and M uller [7] consider
the special case of combinatorial auctions where all goods are the same, and point out
that optimal allocations can be found by dynamic programming. This corresponds to a
one-sided, one-shot version of the AON auction. Kothari et al. [8] present a one-sided,
one-shot auction that supports AON bidding in the form of a minimum trade quantity,
but then assumes divisibility for quantities beyond this minimum. Several other authors
have considered indivisibility constraints in multi-unit auctions [9,10,5], and have also
identified the connection to knapsack methods for matching bids. We describe details of
the allocation algorithm, as well as other AON auction policies, in the sections below.
2.1
Bids Matching Algorithm
As pointed out most explicitly by Kelly [5], optimal winner determination for single-
good, two-sided, multi-unit auctions with indivisible XOR bids (i.e., our AON auctions)
reduces to the
Multiple Choice Knapsack Problem
(MCKP) [10]. Here we present a
formulation of MCKP specialized (slightly) to the auction setting.
Consider a set of
N
agents, with agent
i
submitting bid
B
i
. Each
B
i
is comprised of
m
i
bid points
, (
p
ij
,
q
ij
), specifying a payment
p
ij
offered to exchange quantity
q
ij
. Each
bid includes a dummy point (0
,
0). Offers to buy are expressed as positive payment-
quantity pairs, and offers to sell as negative payment-quantity pairs. Because the stan-
dard MCKP requires positive coefficients, we define transformed bid points (
p
ij
,
q
ij
)=
(
p
ij
+
p
i
,
q
ij
+
q
i
),where
p
i
≡−
min
j
∈
B
i
q
ij
. (Note that this
transformation affects only bids with sell points; for buy-only bids,
q
i
=
p
i
= 0.) We
then define the knapsack
capacity c
min
j
∈
B
i
p
ij
,and
q
i
≡−
≡
∑
i
q
i
. Conceptually, the capacity
c
is equivalent
to the total number of units that are offered for sale. We denote by
C
the maximum
number of units that could be traded. In order to ensure that
C
is bounded, we assume
agents have a limited ability to take short positions in the goods traded. The MCKP is
formulated as:
N
i
=1
m
i
j
=1
p
ij
x
ij
maximize:
m
i
j
=1
q
ij
x
ij
≤
c
,
N
i
=1
subject to:
m
i
j
=1
x
ij
= 1
,
i
∈
A
,
x
ij
∈{
0
,
1
}.
We assume free disposal of units, reflected in allowing the auction to match bids
with more sales than purchases. Excess units are allocated arbitrarily among sellers.
Note that formulating and implementing the same problem without the assumption of
free disposal is straightforward.
2
Our understanding is that practical trading mechanisms admitting AON bids typically handle
them in an ad hoc manner. For example, such bids might be matched in a greedy manner, as in
common electronic stock trading systems, which just pass over AON bids if the entire quantity
cannot be fulfilled.
