The structure of auctions : optimality and efficiency

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, progress on the multi-item case has been sporadic over the past three decades. 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 the 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.

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Mathematics.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2014

Author dc:creator

• Deckelbaum, Alan

Advisor dc:contributor.advisor

• Constantinos Daskalakis.

• Mathematics.

Statement dc:rights

• M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/90182

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/90182