Thesis Defense: The Structure of Auctions: Optimality and Efficiency

Speaker: Alan Deckelbaum , MIT

Date: Thursday, April 24, 2014

Time: 4:00 PM to 5:00 PM Note: all times are in the Eastern Time Zone

Public: Yes

Location: 8-205

Event Type:

Room Description:

Host: Costis Daskalakis

Contact: Joanne Talbot Hanley, 617-253-6054, joanne@csail.mit.edu

Relevant URL:

Speaker URL: None

Speaker Photo:
None

Reminders to:

Reminder Subject: TALK:

Abstract: The problem of constructing auctions to maximize expected revenue is central to mechanism design and to algorithmic game theory. While the special case of selling a single item has been well understood since the work of Myerson, the multi-item case has been much more challenging, and progress over the past three decades has been sporadic. In the first part of this thesis we develop a mathematical framework for finding and characterizing optimal single-bidder multi-item mechanisms by establishing that revenue maximization has a tight dual minimization problem. This approach reduces mechanism design to a measure-theoretic question involving transport maps and stochastic dominance relations. As an important application, we prove that a grand bundling mechanism is optimal if and only if two particular measure-theoretic inequalities are satisfied. We also provide several new examples of optimal mechanisms and we prove that the optimal mechanism design problem in general is computationally intractable, even in the most basic multi-item setting, unless ZPP contains P^#P.

Another key problem in mechanism design is how to efficiently allocate a collection of goods amongst multiple bidders. In the second part of the thesis, we study this problem of welfare maximization in the presence of unrestricted rational collusion. We generalize the notion of dominant-strategy mechanisms to collusive contexts, construct a highly practical such mechanism for multi-unit auctions, and prove that no such mechanism (practical or not) exists for unrestricted combinatorial auctions. Our results explore the power and limitations of enlarging strategy spaces to incentivize agents to reveal information about their collusive behavior.

Research Areas:

Impact Areas:

This event is not part of a series.

Created by Joanne Talbot Hanley at Thursday, April 24, 2014 at 10:24 AM.