Skip navigation
Please use this identifier to cite or link to this item:
Title: Circumventing Lower Bounds in Mechanism and Tournament Design
Authors: Schvartzman Cohenca, Ariel
Advisors: Weinberg, S. Matthew
Contributors: Computer Science Department
Keywords: approximately optimal auctions
correlated auctions
mechanism design
multi item auctions
tournament design
Subjects: Computer science
Issue Date: 2020
Publisher: Princeton, NJ : Princeton University
Abstract: How should a seller price multiple items in order to maximize their revenue from a single buyer? This question has been key in connecting research done by computer scientists and economists to applications such as online ad auctions and spectrum auctions. It was shown almost 40 years ago that if the buyer only cares for one item it is optimal for the seller to offer the buyer the item at a take-it-or-leave-it price. This elegant solution, however, may be far from optimal even for the case with a single buyer interested in just two items. Optimal auction design for two or more items is intricate for a number of reasons: the auctions may be bizarre, computationally hard to find or simply too complex to present to a bidder. Numerous results suggest that (under reasonable complexity assumptions) efficiently finding optimal auctions, even in some simple settings, is impossible. In this thesis, I will present numerous ways in which we try to circumvent these impossibility results in order to recover positive results. These include the study of different multi-item models and beyond-worst case analysis for mechanism design. I will also discuss recent advances in tournament design, a field at the intersection of mechanism design and social choice theory. For problems in this field we get around known impossibility results via approximations in order to find approximately strategy-proof tournament rules.
Alternate format: The Mudd Manuscript Library retains one bound copy of each dissertation. Search for these copies in the library's main catalog:
Type of Material: Academic dissertations (Ph.D.)
Language: en
Appears in Collections:Computer Science

Files in This Item:
File Description SizeFormat 
SchvartzmanCohenca_princeton_0181D_13316.pdf1.27 MBAdobe PDFView/Download

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