EXPRESSING PREFERENCES WITH PRICE-VECTOR AGENTS IN COMBINATORIAL AUCTIONS

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.