EXPRESSING PREFERENCES WITH PRICE-VECTOR AGENTS IN COMBINATORIAL AUCTIONS
Files
Publication or External Link
Date
Authors
Advisor
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.