Skip navigation
Please use this identifier to cite or link to this item: http://arks.princeton.edu/ark:/88435/dsp019880vt91m
 Title: Circumventing Lower Bounds in Mechanism and Tournament Design Authors: Schvartzman Cohenca, Ariel Advisors: Weinberg, S. Matthew Contributors: Computer Science Department Keywords: approximately optimal auctionscorrelated auctionsmechanism designmulti item auctionstournament 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. URI: http://arks.princeton.edu/ark:/88435/dsp019880vt91m Alternate format: The Mudd Manuscript Library retains one bound copy of each dissertation. Search for these copies in the library's main catalog: catalog.princeton.edu 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 PDF

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