CAREER: Fair and Efficient Market Design at Scale

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

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.