EXPRESSING PREFERENCES WITH PRICE-VECTOR AGENTS IN COMBINATORIAL AUCTIONS
EXPRESSING PREFERENCES WITH PRICE-VECTOR AGENTS IN COMBINATORIAL AUCTIONS
Files
Publication or External Link
Date
2004-08-12
Authors
Day, Robert Warren
Advisor
Raghavan, Subramanian
Citation
DRUM DOI
Abstract
In this work, we investigate two combinatorial auction formats in which
each bidding bidder may be represented by a collection of unit-demand or
price-vector agents. In the first model, bidder preferences are aggregated in
a Bid Table, through which a bidder in a combinatorial auction may
express several forms of subadditive preferences. We show that the gross
substitutes property holds for this model, and design a large-scale
combinatorial auction using bid tables as a demand revelation stage,
determining linear price signals for later stages. The constraints of this
model coincide naturally with the restrictions of recently proposed FAA
landing-slot auctions, and we provide a slot auction design based on this model.
In a second model, we explore the more complex behavior possible when
each bidder's collection of price-vector agents coordinate based on a
bidder-specified ordering of the auction items. With this coordination each
bidder is able to convey a rich set of preferences, including the ability to
express both superadditive and subadditive bundle synergies (i.e., substitutes
and complements). The instructions for this collection of agents are tabulated
in a lower-triangular Matrix Bid, and we compare the use of matrix
bids to other compact techniques for writing down a wide variety of bidding
information. We show that the winner determination problem for this Matrix Bid
Auction is NP-hard, provide results from a series of computational
experiments, and develop IP techniques for improving run time.
In addition to the results on price-vector agents, bid tables, and
matrix bidding, we present a new technique for achieving bidder-Pareto-optimal
core outcomes in a sealed-bid combinatorial auction. The key idea of this
iterative procedure is the formulation of the separation problem for core
constraints at an arbitrary point in winner payment space.