Essays on Stability and Robustness in Market Design

Abstract

This dissertation investigates outcomes of matching-based markets through the lens of stability and robustness. In the first two chapters, we examine how decentralized interactions affect market outcomes. Chapter 1 shows the fragility of stable matchings in a decentralized one-to-one matching setting. The classical work of Roth and Vande Vate (1990) suggests simple decentralized dynamics in which randomly-chosen blocking pairs match successively. Such decentralized interactions guarantee convergence to a stable matching. Our first theorem shows that, under mild conditions, any unstable matching—including a small perturbation of a stable matching—can culminate in any stable matching through these dynamics. Our second theorem highlights another aspect of fragility: stabilization may take a long time. Even in markets with a unique stable matching, where the dynamics always converge to the same matching, decentralized interactions can require an exponentially long duration to converge. A small perturbation of a stable matching may lead the market away from stability and involve a sizable proportion of mismatched participants for extended periods. Chapter 2 studies the formation of stable supply chain networks, generalizing the theory of Roth and Vande Vate (1990) developed for two-sided matching markets. We prove that for any unstable network, there exists a finite sequence of successive myopic blocking chains leading to a stable network. Our proof suggests an algorithm for finding a stable network that extends the classical Gale and Shapley (1962)’s Deferred Acceptance algorithm. In the last chapter, we turn to markets in which outcomes are generated through centralized clearinghouses. Chapter 3, joint with Marcelo Ariel Fernandez and Leeat Yariv, studies the impacts of incomplete information on centralized one-to-one matching markets. We focus on the commonly used Deferred Acceptancemechanism (Gale and Shapley, 1962). We show that many complete-information results are fragile to a small infusion of uncertainty about others' preferences.