Algorithmic market design

Placeholder Show Content


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.


Type of resource text
Form electronic; electronic resource; remote
Extent 1 online resource.
Publication date 2015
Issuance monographic
Language English


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-


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

© 2015 by Mohammad Akbarpour
This work is licensed under a Creative Commons Attribution Non Commercial 3.0 Unported license (CC BY-NC).

Also listed in

Loading usage metrics...