Information Technology Reference
In-Depth Information
overall efficiency. Therefore, since we are not addressing strategic issues in this work,
the choice is not pivotal for our experimental analysis. Nevertheless, to fully specify the
mechanism one must identify a pricing rule. Ours starts with Vickrey prices and adjusts
them proportionally to ensure budget balance.
3
The Vickrey calculation requires that
we compute the total surplus with each agent's bid excluded, for which
O
(
N
) deletion
and insertion operations need to be performed.
2.3
Quoting
After each bid, the auction issues a
price quote
, providing to the agents some informa-
tion regarding the state of the order topic, intended as a guide to future bidding. In the
standard auction, the quote comprises a
BID
-
ASK
pair, representing the prices at which
an agent could successfully trade at least one unit. The
BID
quote defines the price at
which an agent could sell one unit, and the
ASK
quote the corresponding price to buy.
For standard (divisible-bid) auctions, we can incrementally maintain the order topic so
that price quotes can be provided in constant time once the bids are inserted [6].
For the AON auction, it is not immediately apparent how the auction should define
its price quotes. We identified four candidate quoting policies, described here and com-
pared experimentally in Section 4 below.
Standard Quote.
One possibility is for the AON auction to provide a “standard” quote,
defined as the
BID
-
ASK
pair reflecting the order topic interpreted
as if the bids were di-
visible
. Constructing this interpretation requires some care, since simply treating each
bid point as a divisible offer may violate the standard auction's consistency condition
requiring that quantity be nonincreasing in unit price. To ensure this monotonicity, we
transform each bid
B
i
by first sorting the bid points (
p
ij
,
q
ij
) (not including the dummy
point with
p
ij
=
q
ij
= 0) in decreasing order of unit price. We then traverse the list,
translating each to a unit-price bid point, skipping any that would violate the mono-
tonicity condition with respect to those already seen. These translated bids can then be
handled by the order topic and quoting algorithm of the standard auction.
Marginal Unit Quote.
A second quote candidate attempts to maintain the interpreta-
tion of the standard quote as a price threshold sufficient to trade one unit, but respecting
the indivisibility constraints of AON bids. Calculating this quote requires solving the
MCKP for the bids in the order topic. Under this interpretation, the
ASK
quote is always
defined as long as there is any sell offer in the order topic. The same is not true for the
BID
quote, however, because it could be the case that no existing offer or combination of
offers can be satisfied by contributing a single additional unit. The marginal unit quote
takes the same form as the standard quote, but provides more conservative values. In-
deed, it is even possible (and consistent) that the
ASK
price quoted be lower than the
BID
price, something that cannot happen in the divisible case. It would also be possible
to define this quote with any particular quantity defined as “marginal” (e.g., ten units
3
Intuitively, this should tend toward reducing the incentive to behave strategically, though we
know this is not strictly true. Of course, no budget-balanced mechanism can achieve this ex-
actly. A serious treatment of strategic concerns in this context is a subject of future work.
