Skip navigation
Please use this identifier to cite or link to this item: http://arks.princeton.edu/ark:/88435/dsp015d86p356k
Title: Approximation Schemes for Revenue Maximization with Multiple Subadditive Buyers
Authors: Chakarov, Dimitar
Advisors: Weinberg, Matt
Department: Mathematics
Class Year: 2024
Abstract: We consider the problem of revenue maximization for a single monopolistic seller with $n$ independent items facing $m$ independent buyers. Our main technical result reduces finding a $(1 - O(\varepsilon))$-approximation to revenue maximization for a distribution over unbounded subadditive valuations to finding a $(1 - \varepsilon)$-approximation when the values are (almost) bounded and still subadditive. We use this reduction to show a quasi-polynomial time approximation scheme for multiple $k$-demand buyers who have constant support per item. Along the way, we introduce several theoretical notions---modified revenue maximization, leftovers of an interim menu, making buyers exclusive above a threshold, and extending an interim menu with exclusive options---that might be of independent interest to mechanism designers.
URI: http://arks.princeton.edu/ark:/88435/dsp015d86p356k
Type of Material: Princeton University Senior Theses
Language: en
Appears in Collections:Mathematics, 1934-2024

Files in This Item:
File Description SizeFormat 
CHAKAROV-DIMITAR-THESIS.pdf868.46 kBAdobe PDF    Request a copy


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