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.