Skip navigation
Please use this identifier to cite or link to this item: http://arks.princeton.edu/ark:/88435/dsp013197xq14f
Title: A Study of Prophet and Prophet Secretary Inequalities for Combinatorial Auctions
Authors: Christensen, Jacob
Advisors: Singla, Sahil
McConnell, Mark
Department: Mathematics
Class Year: 2021
Abstract: We study the problem of combinatorial auctions with subadditive buyers in an online setting. There is a set of n agents and m unique indivisible items, and a product distribution F = F1 × · · · × Fn of valuations vi ∼ Fi which are assumed to be subadditive. In the online setting, agents arrive sequentially in some random order to receive an allocation of items which cannot be taken back. Our goal to design a mechanism which efficiently produces an allocation of items to the agents that maximizes expected social welfare. Expectation is taken over the the randomness of the mechanism, the valuation distributions, and the arrival order. We first study the most current posted price mechanisms, which set a price on each item and requires agents to pay the sum of item prices for whatever set they are allocated. We then look at the multi-unit auction setting, where there are m copies of 1 indivisible item. This setting is explored in conjunction with the secretary model, which assumes agents arrive uniform randomly. In this crossover setting, we prove that there are mechanisms using uniform dynamic prices which provide a (1−1/e)-approximation for unit-demand and XOS valuations.
URI: http://arks.princeton.edu/ark:/88435/dsp013197xq14f
Type of Material: Princeton University Senior Theses
Language: en
Appears in Collections:Mathematics, 1934-2021

Files in This Item:
File Description SizeFormat 
CHRISTENSEN-JACOB-THESIS.pdf302.73 kBAdobe PDF    Request a copy


Items in Dataspace are protected by copyright, with all rights reserved, unless otherwise indicated.