CAREER: Fair and Efficient Market Design at Scale

市场是一种古老的制度，它使社会能够通过匹配供求来有效地配置资源。大多数人认为市场与金钱有关，例如股票市场。然而，即使在没有资金的问题中，市场设计原则在形成有效结果方面也发挥着关键作用。示例问题包括医疗住院医师匹配、学生与学校匹配、捐赠者与肾脏匹配、公平的课程座位分配、住房分配以及共享计算资源。市场均衡是经济理论中的一个关键概念，它规定了商品（如课程座位或计算资源）如何通过找到出清市场的价格在个人之间有效分配。这甚至适用于没有货币的环境，通过给每个人一个假货币的预算来诱导市场。然而，为了使这些想法具有实际应用，我们需要计算市场均衡的方法，可能是大规模的。该项目将开发一种人工智能和优化驱动的大规模市场均衡计算方法。这将导致新的更公平的算法来解决诸如匹配献血者和献血地点、课程座位分配、公共住房分配和公平推荐系统等问题。该项目还包括大量的教育内容，包括撰写一本关于现代人工智能和基于优化的博弈论和市场设计方法的书。该项目开发了一种通用的人工智能驱动方法，用于实现大规模市场均衡。这需要开发新的在线学习方法，以考虑现实世界的结构和基于机器学习的预测。具体而言，该项目在以下四个技术挑战方面做出了贡献：1)在线公平分配和动态市场：该项目提出了基于在线学习和一阶方法的在线公平分配新算法，重点关注对许多类型的输入模型具有鲁棒性的算法，并将乐观和预测在线学习的最新进展扩展到公平分配设置。2)双边偏好：基于市场均衡的公平分配没有捕捉到的现实世界中常见的复杂情况是，市场的双方都对应于我们希望公平对待的代理人。该项目开发了一类新的双边费雪市场模型和算法。3)组合偏好：组合偏好在实践中大量存在，但这些并没有被标准模型捕获。该项目开发了新的实用程序类和相关的优化模型和算法，用于处理各种组合实用程序结构。4)费雪市场的统计推断：该项目将启动费雪市场的统计推断研究，包括从底层模型中抽样的费雪市场的正态性等问题，以及市场反事实推断的新理论。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Markets are an ancient institution that enables society to efficiently allocate resources by matching supply to demand. Most people think of markets as involving money, for example the stock market. Yet even in problems without money, market design principles play a key role in shaping efficient outcomes. Example problems include medical residency matching, matching students to schools, matching donors to kidneys, fair course seat assignment, housing allocation, and sharing compute resources. Market equilibrium is a key concept in economic theory, specifying how goods, such as course seats or compute resources, can efficiently be distributed among individuals, by finding prices that clear the market. This applies even in settings without money, by giving each individual a budget of faux currency in order to induce a market. Yet, for these ideas to have practical applications, we need methods for computing market equilibria, potentially at large scales. This project will develop an AI and optimization-driven approach to large-scale market equilibrium computation. This will lead to new and fairer algorithms for problems such as matching blood donors to donation sites, course seat allocation, public housing allocation, and fair recommender systems. This project also includes a substantial educational component, including writing a book on modern AI and optimization-based methods for game theory and market design. The project develops a general AI-driven approach towards operationalizing large-scale market equilibria. This requires the development of new online learning methods that account for real-world structure and machine-learning-based predictions. Concretely, the project makes contributions along the following four technical challenges: 1) Online fair allocation and dynamic markets: The project proposes new algorithms for online fair allocation, based on online learning and first-order methods, with a focus on algorithms that are robust to many types of input models, and the extension of recent advances in optimistic and predictive online learning to the fair allocation setting. 2) Two-sided preferences: A frequent real-world complication not captured by market-equilibrium-based fair allocation is that both sides of the market correspond to agents that we wish to treat fairly. The project develops a new class of two-sided Fisher market models and algorithms. 3) Combinatorial preferences: Combinatorial preferences abound in practice, yet these are not captured by standard models. The project develops new utility classes and associated optimization models and algorithms for handling a wide array of combinatorial utility structures. 4) Statistical inference in Fisher markets: The project will initiate the study of statistical inference in Fisher markets, including questions such as the normality of Fisher markets sampled from an underlying model, as well as a new theory of counterfactual inference in markets.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.