Market-Based Allocation with Indivisible Bids - Agent-Mediated Electronic Commerce - page 58

However, realistic versions of this scenario vary from the idealization in several
ways. 1 One particularly important characteristic of this application domain is noncon-
vexity in preferences and production technology, as manifest (for example) in fixed
costs, reconfiguration switching costs, and preset order sizes. The most straightforward
multi-unit auction mechanisms assume divisibility of offers: an agent willing to buy q
units at some price would also be willing to accept q ≤ q units at that price. This as-

sumption will not generally hold given nonconvex preferences and costs, and therefore
agents with these characteristics may be hesitant to bid at all absent some condition that
its offer be accepted in whole or not at all.
We investigate the design of multi-unit auctions accommodating such indivisibility
constraints. Our focus is on how such auctions can be operated in a computationally
efficient manner, and on the auctions' price quote policies for revealing information to
agents to guide their bidding. We evaluate our designs experimentally, employing a ver-
sion of the manufacturing scenario sketched above. Our main finding is that supporting
indivisibility constraints can in fact improve the quality of global allocations achieved
through trading, but that this improvement does depend pivotally on the form of the
price quote. In the full version of this paper we also show how the computational costs
of optimizing bid matching and producing meaningful quotes can be amortized over the
auction's operation, calculated incrementally throughout the dynamic bidding process.

2 Auction Mechanisms

We consider two-sided auctions for multiple units of a single good. The auctions clear
periodically at predefined intervals, and thus implement a call market . We distinguish
two major versions of this auction, differing in their treatment of offer quantities. In
the first (called “standard” for purposes of this paper), quantities appearing in bids are
assumed divisible, and so the bidder effectively expresses a willingness to trade any
amount up to the specified quantity at the associated unit price. In the second, offers are
considered “all-or-none” (AON), and so agents explicitly specify the payment at which
they would be willing to trade any acceptable discrete quantity. We refer to this version
as the “AON” auction henceforth.
In both auctions, agents may submit bid schedules , indicating the prices offered to
trade various quantities (with negative quantities indicating amounts offered to sell).
The points on the schedule are exclusive (i.e., treated as “XOR” [4]), in that the result-
ing allocation will employ at most one of them. For divisible (standard) bids, the prices
are per unit, and consistency requires that unit prices be nonincreasing in quantity. For
indivisible (AON) bids, the prices represent total payments for the associated quantity,
and these totals (not the per-unit payments) must be nondecreasing in quantity. Assum-
ing only free disposal, with AON bids, agents can express arbitrary valuations for the
good [5,4]. Standard divisible bids can express only convex valuations.
Operation of the standard auction is relatively simple, as described, for example, by
Wurman et al. [6]. Mechanisms resembling the AON auction have been described in the

1

Our work does not address all important variations from the ideal. In particular, we maintain
the assumption of competitiveness, modeling our agents essentially as price takers.