CAREER: An Algorithmic Theory of Matching Markets

In a matching market, agents cannot buy a product just by paying its price. Instead, the product they will receive is a function of both their preferences and the preferences of the other agents, including those of the sellers. Consider for instance the problem of assigning students to public high schools. As in the USA every child is entitled to free education, decisions on how eighth-graders are assigned to public high schools must be made based on their grades, features, and wishes, rather than resorting to prices. Since their introduction by Gale and Shapley in 1962, matching markets have been a fundamental research topic in computer science, economics, and operations research. Today, they arise in contexts ranging from enhancing diversity in school cohorts, to house allocation, to the assignment of users to servers and of refugees to their new homes. Typically, the large size of those markets implies that, even when good assignments exist, one may not be able to find them. The goal of this award is to propose fast algorithms to obtain fair allocations of goods in various matching markets, as well as proposing new, impactful matching markets that model complex scenarios. These algorithms will allow finding provably good solutions to all the matching markets mentioned above, and more. The educational and outreach initiatives of this project will instruct middle school students from underrepresented minorities on the features of the current mechanisms guiding the admission to public high schools, as to enhance their opportunities of obtaining a good placement.

In more detail, this project will undertake a systematic study of matching markets from an algorithmic perspective, with the goal of understanding the computational limits of the present theory, and of devising alternative models and solutions for markets that currently elude computational tractability. This award will investigate provably fast algorithms to find matchings that satisfy or approximate important properties and/or that maximize certain objective functions modelling fairness or profit. For many of those problems, no algorithm is currently known. More generally, this project aims at a systematic algorithmization of certain existence results in the area, as well as the development of new, insightful, and impactful models. The three research thrusts of this award will focus on models with choice functions, algorithms for dominating points in polytopes (à la Scarf), and von Neumann-Morgenstern stability, respectively. By investigating the mathematical structures underlying matching markets, the research carried out in this project also aims at deducing principles and algorithms whose interest go beyond matching markets, and have impact on the investigation of mathematical objects such as lattices, posets, and polytopes.

This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.