UC Irvine

For several decades now, matching mechanisms have been deployed, sometimes implicitly, to solve economic and social problems with unprecedented efficiency. Most notably, the kidney transplant matching algorithm has been key in saving many lives, 39,000 donation in 2019 alone. Likewise, the National Residency Matching Program successfully employed in the United States today uses a matching mechanism that places medical students into hospital residencies. A similar mechanism is used in college and public school admissions around the United States, most famously, in the Boston and New York City. This dissertation will continue this long history of applying matching mechanisms towards efficiently solving social problems.

We begin with a summary of relevant definitions and other terminology in chapter1, all of which will be applied in the chapters that follow. Chapter 2 will examine two concurrent social problems, over-production of resources that contributes to global waste, and lack of access to wasted resources by people living on the economic margin. We will contrast two possible solutions to both problems, that is, a decentralized vs a centralized matching solution. The feasibility of both solutions will be tested through theoretical investigation and two qualitative case studies in food surplus redistribution in the United Kingdom and allocation of housing to unhoused household in Los Angeles County during the pandemic.

Chapter 3 will give a more detail examination of allocation of housing to the unhoused by examining the efficiency and robustness to manipulation of the algorithm that was employed by LA county vs a centralized matching mechanism. Whereas Chapter 4 will explore an online matching mechanism solution to the problem of traffic congestion pricing. The proposed solution combines a matching algorithm, which assigns drivers to routes at the time of travel, with an anticipatory pricing mechanism that determines how much each traveling driver pays if they choose to use a congested route.

The conclusion will present open problems implied in the preceding three chapters.