Circumventing Lower Bounds in Mechanism and Tournament Design

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.