CAREER: Fair and Efficient Market Design at Scale

职业：公平、高效的大规模市场设计

• 批准号: 2238960
• 负责人: Christian Kroer
• 金额: $ 60万
• 依托单位: Columbia University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2023
• 资助国家: 美国
• 起止时间: 2023-07-01 至 2028-06-30
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2238960&HistoricalAwards=false
• 关键词: CAREER; Fair; Efficient; Market; Design

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.

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

项目成果

Statistical Inference and A/B Testing for First-Price Pacing Equilibria

一价节奏均衡的统计推断和 A/B 测试

• 发表时间: 2023
• 期刊: Proceedings of the 40 th International Conference on Machine Learning
• 作者: Liao, Luofeng;Kroer, Christian
• 通讯作者: Kroer, Christian

Fair Allocation Over Time, with Applications to Content Moderation

随着时间的推移公平分配，以及内容审核的应用

• DOI: 10.1145/3580305.3599340
• 发表时间: 2023
• 期刊: KDD '23: Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining
• 作者: Allouah, Amine;Kroer, Christian;Zhang, Xuan;Avadhanula, Vashist;Bohanon, Nona;Dania, Anil;Gocmen, Caner;Pupyrev, Sergey;Shah, Parikshit;Stier-Moses, Nicolas
• 通讯作者: Stier-Moses, Nicolas

Single-Leg Revenue Management with Advice

• DOI: 10.1145/3580507.3597704
• 发表时间: 2022-02
• 期刊: Proceedings of the 24th ACM Conference on Economics and Computation
• 作者: S. Balseiro;Christian Kroer;Rachitesh Kumar