This thesis consists of three self-contained essays that investigate the algebraic structure of matching markets and the stabilization dynamics in decentralized markets. Chapter 2 is based on Wu and Roth (2018). It studies envy-free matchings that naturally arise from workers retiring or companies expanding. We show that the set of envy-free matchings forms a lattice that has a Conway-like join, but not a Conway-like meet. Furthermore, a job hopping process in which companies make offers to their favorite blocking workers, and workers accept their favorite offers, producing a sequence of vacancy chains, is a Tarski operator on this lattice. The fixed points of this Tarski operator correspond to the set of stable matchings; and the steady state matching starting from any given initial state is derived analytically. Chapter 3 is based on Wu (2020). The goal of this chapter, is to provide a systematic approach for analyzing entering classes in the college admissions model. When dealing with a many-to-one matching model, we often convert it into a one-to-one matching problem by assigning each seat of a college to a single student, instead of matching each college to multiple students. The preferences in this new model are significantly correlated and severely restrict the possible changes to entering classes. Through the so-called "rotations" that correspond to the join-irreducible elements in the lattice of stable matchings, we present a unified treatment for several results on entering classes, including the famous "Rural Hospital Theorem". We also show that, the least preferred student in an entering class appears to play a very interesting role. For example, each entering class can be completely characterized by its worst student. Chapter 4 is based on Gu, Roth, and Wu (2020). The motivating question is that, how come some black markets, such as the market for hitmen are well-regulated, but many others like the market for drugs are far from being under our control, even though we try very hard to eliminate them. To understand this, we build a three-dimensional discrete time Markov chain to study how black markets evolve over time, focusing on social repugnance and search frictions. We borrow tools from Markov jump processes, random walks, exponential martingales and optional sampling theory to analyze both the steady state limit and the realizations along the way. In the first part of the chapter, we identify conditions that lead to market survival or extinction. And the second part studies speed of convergence. We show that if a market is going to die eventually, then it dies exponentially fast. This further implies if a market has survived for a long time, then it is likely to survive forever.

This paper empirically studies a decentralized dynamic peer-to-peer matching market. We use data from a leading ride-sharing platform in China to estimate a continuous-time dynamic model of search and match between drivers and passengers. We assess the efficiency of the decentralized market by how much centralized algorithms may improve welfare. We find that a centralized algorithm can increase the number of matches by making matches less frequently and matching agents more assortatively.

We consider decentralized matching with frictions in a two-sided market. By frictions, we mean natural refinements that make it hard or even impossible to use the canonical notion of stability. Instead of that, we use non-cooperative game theory tools: a matching process is described as a game where all agents have their own strategies. It allows us to use Nash equilibrium to distinguish "good" and "bad" matchings. Although this approach significantly complicates the model, market frictions (incomplete information, dynamics, and application costs) allow us to get more nuanced results and better understanding of the matching process itself. In Chapter 2, we consider multi-period decentralized matching in a market of universities and students. Because of dynamics, asymmetry, and private information, we always observe delays and coordination failures with nonzero probability. We show that problems of miscoordination and delay may be solved by signaling or by incentivizing immediate response turning a dynamic problem into a static one and make the matching stable. Although implementing signaling or immediate response is always socially beneficial, it is not necessarily beneficial for the best university. We also obtain sufficient conditions for assortative matching to be and not to be in equilibrium. In Chapter 3, we consider decentralized matching in a market of firms and workers with application costs and limited budgets. Workers choose whether they should take the risk of applying to a higher-ranked firm (with some probability of rejection) or make a safe choice. We show that application costs set by firms with uncertain capacity may be treated as a screening instrument in order to attract only strong applicants or avoid the competition. Surprisingly, competition may lead to increasing costs: low-ranked firms may even prefer implementing highest possible costs in equilibrium. We provide economic intuition behind this paradox and find necessary and sufficient conditions that lead to this result. Finally, Chapter 4 is devoted to the difference in results for firms with limited and unlimited capacity. The main insight here is that in order to avoid competition with high-type employees, low-type employees may send applications to higher-ranked firms. This happens when the entire pool of employees is weak enough.

We experimentally study decentralized one-to-one matching markets with transfers. We vary the information available to participants, complete or incomplete, and the surplus structure, supermodular or submodular. Several insights emerge. First, while markets often culminate in efficient matchings, stability is more elusive, reflecting the difficulty of arranging attendant transfers. Second, incomplete information and submodularity present hurdles to efficiency and especially stability; their combination drastically diminishes stability's likelihood. Third, matchings form "from the top down" in complete-information supermodular markets, but exhibit many more and less-obviously ordered offers otherwise. Last, participants' market positions matter far more than their dynamic bargaining styles for outcomes.