Algorithmic market design
Abstract/Contents
- Abstract
- This thesis consists of two essays that exploit algorithmic techniques to solve two matching market design problems. The first essay introduces a simple benchmark model of dynamic matching in networked markets, where agents arrive and depart stochastically and the network of acceptable transactions among agents forms a random graph. The main insight of our analysis is that waiting to thicken the market can be substantially more important than increasing the speed of transactions. We also show that naive local algorithms that maintain market thickness by choosing the right time to match agents, but do not exploit global network structure, can perform very close to optimal algorithms. Finally, our analysis asserts that having information about agents' departure times is highly valuable. To elicit agents' departure times when it is private, we design an incentive-compatible continuous-time dynamic mechanism without transfers. The second essay extends the scope of random allocation mechanisms, in which the mechanism first identifies a feasible "expected allocation" and then implements it by randomizing over nearby feasible integer allocations. Previous literature had shown that the cases in which this is possible are sharply limited. We show that if some of the feasibility constraints can be treated as goals rather than hard constraints then, subject to weak conditions that we identify, any expected allocation that satisfies all the constraints and goals can be implemented by randomizing among nearby integer allocations that satisfy all the hard constraints exactly and the goals at least approximately. We show that by adding ex post utility goals to random serial dictatorship, we can construct a strategy-proof mechanism with the same ex ante utility that is nearly ex post fair.
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 | Akbarpour, Mohammad |
|---|---|
| Associated with | Stanford University, Department of Economics. |
| Primary advisor | Milgrom, Paul R. (Paul Robert), 1948- |
| Thesis advisor | Milgrom, Paul R. (Paul Robert), 1948- |
| Thesis advisor | Jackson, Matthew O |
| Thesis advisor | Roth, Alvin E, 1951- |
| Advisor | Jackson, Matthew O |
| Advisor | Roth, Alvin E, 1951- |
Subjects
| Genre | Theses |
|---|
Bibliographic information
| Statement of responsibility | Mohammad Akbarpour. |
|---|---|
| Note | Submitted to the Department of Economics. |
| Thesis | Thesis (Ph.D.)--Stanford University, 2015. |
| Location | electronic resource |
Access conditions
- Copyright
- © 2015 by Mohammad Akbarpour
- 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...