CAREER: An Algorithmic Theory of Matching Markets

在匹配市场中，代理商不能仅仅通过支付价格来购买产品。相反，他们将得到的产品是他们的偏好和其他代理人（包括卖方）的偏好的函数。例如，考虑分配学生到公立高中的问题。就像在美国，每个孩子都有权享受免费教育一样，八年级学生如何分配到公立高中必须根据他们的成绩、特征和愿望来决定，而不是诉诸于价格。自1962年Gale和Shapley提出匹配市场以来，匹配市场一直是计算机科学、经济学和运筹学的基础研究课题。今天，它们出现在各种背景中，从加强学校群体的多样性，到住房分配，到将用户分配给服务器，以及将难民分配给他们的新家。通常，这些市场的庞大规模意味着，即使存在好的投资任务，人们也可能找不到它们。该奖项的目标是提出快速算法，以在各种匹配市场中获得公平的商品分配，以及提出新的、有影响力的匹配市场，以模拟复杂的场景。这些算法将允许为上述所有匹配市场找到可证明的良好解决方案，以及更多。这项计划的教育和外展措施，将会指导少数族裔中学生了解目前公立高中录取机制的特点，以增加他们获得良好安置的机会。更详细地说，该项目将从算法的角度对匹配市场进行系统研究，目的是了解当前理论的计算极限，并为目前无法计算可追溯性的市场设计替代模型和解决方案。该奖项将研究可证明的快速算法，以找到满足或近似重要属性的匹配和/或最大化建模公平或利润的某些目标函数。对于其中的许多问题，目前还没有已知的算法。更一般地说，该项目旨在对该领域某些存在的结果进行系统的算法化，以及开发新的、有洞察力的和有影响力的模型。该奖项的三个研究重点将分别集中在具有选择函数的模型、多面体中支配点的算法（例如Scarf）和von Neumann-Morgenstern稳定性。通过研究匹配市场背后的数学结构，本项目开展的研究还旨在推导出超越匹配市场的原理和算法，并对格、偏序集和多面体等数学对象的研究产生影响。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.