Skip to main content.
Advanced search >
<< Back to previous page Print

<< Monday, April 22, 2013 >>


Remind me

Tell a friend

Add to my Google calendar (bCal)

Download to my calendar

Bookmark and ShareShare


[Dissertation Talk] The Complexity of Optimal Auction Design

Seminar: Departmental | April 22 | 2-3 p.m. | 373 Soda Hall


Georgios Pierrakos, EECS

Electrical Engineering and Computer Sciences (EECS)


This dissertation provides a complexity-theoretic critique of Myerson's theorem, one of Mechanism Design's crown jewels. This theorem gives a remarkably crisp solution to the problem faced by a monopolist wishing to sell a single item to a number of interested, rational bidders, whose valuations for the item are distributed independently according to some given distributions. The monopolist's goal is to design an auction that will maximize her expected revenue, while at the same time incentivizing the bidders to bid their true value for the item. Myerson solves this through a reduction to the problem of designing the social welfare-maximizing auction (i.e. allocating the item to the bidder who values it the most). This latter problem is well understood, and it admits a very simple solution, namely the Vickrey (or second-price) auction.

In the present dissertation we explore the trade-offs between the plausibility of this result and its tractability:

First, we consider what happens as we shift away from the simple setting of Myerson to more complex settings, and, in particular, to the case of bidders with arbitrarily correlated valuations. As our main result, we show that a characterization as crisp and elegant as Myerson's is not possible for this more general setting. Then, motivated by the subtle interplay between social welfare- and revenue-maximizing auctions implied by Myerson's theorem, we study the trade-off between those two objectives for various types of auctions. We show that, as one moves from the least plausible auction format to the most plausible one, the problem of reconciling revenue and welfare becomes less and less tractable.


georgios@cs.berkeley.edu, 510-6763164