Information Technology Reference
In-Depth Information
Market-Based Allocation with Indivisible Bids
L. Julian Schvartzman and Michael P. Wellman
University of Michigan
Computer Science & Engineering
Ann Arbor, MI 48109-2121 USA
{ lschvart, wellman } @umich.edu
Abstract. We study multi-unit double auctions accepting bids with indivisibility
constraints. We propose different price-quote policies and study their influence on
the efficiency of market-based allocation. Using a reconfigurable manufacturing
scenario where agents trade large quantities of multiple goods, we demonstrate
potential benefits of supporting indivisibility constraints in bidding. These bene-
fits are highly sensitive to the form of price quote provided, indicating interesting
tradeoffs in communication and allocation efficiency.
1
Introduction
Consider a scenario with N manufacturing facilities with capabilities to produce vari-
ous industrial parts. The facilities are controlled by different agents (e.g, firms, or profit-
center divisions within the same large firm), and may vary in capacity, fixed and variable
costs for producing the different part types, time for reconfiguring to switch between
parts, transportation costs, and perhaps other factors. Each facility also has a set of cus-
tomer orders, each representing a promise to pay a fixed amount contingent on delivery
of a specified quantity of a particular type of part in the current period.
Since the facilities face heterogeneous cost structures, they stand to achieve signifi-
cant gains in efficiency by exchanging orders among themselves. We can formulate the
order allocation problem as a global optimization, but of course the agents may not have
the appropriate incentives to reveal their private information about costs and orders, or
comply with the resulting order exchanges. Economic mechanisms such as combina-
torial auctions [1] can address these incentives problems, and provide an elegant solu-
tion when in fact they can be instituted. However, there are several organizational and
computational impediments to holding large-scale (measured in numbers of goods and
agents, and units per good) two-sided combinatorial auctions, and these are as yet un-
common in practice. It is substantially simpler to deploy individual two-sided multi-unit
auctions for each of several goods, and these more ad hoc markets can address the allo-
cation problem to a useful degree. For example, idealized models of such configurations
as general-equilibrium systems demonstrate the potential of computational markets to
achieve efficient allocations in convex, competitive environments [2,3].
This work was supported by the NSF Engineering Research Center for Reconfigurable Manu-
facturing under Award EEC-9529125 of the National Science Foundation. An extended report
is available from the authors.
Search WWH ::




Custom Search