Theses and Dissertations from UMD

Permanent URI for this communityhttp://hdl.handle.net/1903/2

New submissions to the thesis/dissertation collections are added automatically as they are received from the Graduate School. Currently, the Graduate School deposits all theses and dissertations from a given semester after the official graduation date. This means that there may be up to a 4 month delay in the appearance of a give thesis/dissertation in DRUM

More information is available at Theses and Dissertations at University of Maryland Libraries.

Browse

Filters

20041

Settings

Author: search.filters.author.Day, Robert Warren

Search Results

Now showing 1 - 1 of 1
  • Thumbnail Image
    Item
    EXPRESSING PREFERENCES WITH PRICE-VECTOR AGENTS IN COMBINATORIAL AUCTIONS
    (2004-08-12) Day, Robert Warren; Raghavan, Subramanian; Applied Mathematics and Scientific Computation; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)
    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.