Robust market design : information and computation
Abstract/Contents
- Abstract
- A fundamental problem in economics is how to allocate precious and scarce resources, such as radio spectrum or the attention of online consumers, to the benefit of society. The vibrant research area of market design, recognized by the 2012 Nobel Prize in economics, aims to develop an engineering science of allocation mechanisms based on sound theoretical foundations. Two central assumptions are at the heart of much of the classic theory on resource allocation: the common knowledge and substitutability assumptions. Relaxing these is a prerequisite for many real-life applications, but involves significant informational and computational challenges. The starting point of this dissertation is that the computational paradigm offers an ideal toolbox for overcoming these challenges in order to achieve a robust and applicable theory of market design. We use tools and techniques from combinatorial optimization, randomized algorithms and computational complexity to make contributions on both the informational and computational fronts: (I) We design simple mechanisms for maximizing seller revenue that do not rely on common knowledge of buyers' willingness to pay. First we show that across many different markets -- including notoriously challenging ones in which the goods are heterogeneous -- the optimal revenue benchmark can be surpassed or approximated by adding buyers or limiting supplies, and then applying the standard Vickrey (second-price) mechanism. We also show how, by removing the common knowledge assumption, the classic theory of revenue maximization expands to encompass the realistic but complex case in which buyers are interdependent in their willingness to pay. (II) We prove positive and negative results for maximizing social welfare without substitutability, i.e., without the convexity property known to drive economic efficiency. On the positive side, we design natural greedy mechanisms for two-sided markets with strong incentive properties, whose welfare performance depends on the market's distance from substitutability. On the negative side, we show how computational challenges related to complementarity lead to the economic failure of competitive markets, in the sense that there do not exist simple prices that guide such a market to an efficient allocation. These results carry implications for the practice of market design, both for revenue-maximizing sellers such as Internet companies running online auctions, and for welfare-maximizing policy makers such as governments running spectrum auctions.
Description
| Type of resource | text |
|---|---|
| Form | electronic; electronic resource; remote |
| Extent | 1 online resource. |
| Publication date | 2015 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Associated with | Talgam Cohen, Inbal |
|---|---|
| Associated with | Stanford University, Department of Computer Science. |
| Primary advisor | Roughgarden, Tim |
| Thesis advisor | Roughgarden, Tim |
| Thesis advisor | Johari, Ramesh, 1976- |
| Thesis advisor | Milgrom, Paul R. (Paul Robert), 1948- |
| Advisor | Johari, Ramesh, 1976- |
| Advisor | Milgrom, Paul R. (Paul Robert), 1948- |
Subjects
| Genre | Theses |
|---|
Bibliographic information
| Statement of responsibility | Inbal Talgam Cohen. |
|---|---|
| Note | Submitted to the Department of Computer Science. |
| Thesis | Thesis (Ph.D.)--Stanford University, 2015. |
| Location | electronic resource |
Access conditions
- Copyright
- © 2015 by Inbal Talgam Cohen
- License
- This work is licensed under a Creative Commons Attribution Non Commercial 3.0 Unported license (CC BY-NC).
Also listed in
Loading usage metrics...