CAREER: Scalable and Robust Dynamic Matching Market Design

市场是授权利益相关方（人类、公司、政府或自主代理人）交换商品、服务和信息的系统。 由于后勤或社会的限制，许多市场，例如择校、拼车、住院医师、广告、尸体器官分配、在线劳动力、公共住房、难民安置，以及肾脏交换等易货市场，不能仅仅依靠价格来匹配供需。 该项目将建立人工智能（AI）与匹配市场理论和实践之间的联系。具体来说，它将创建实用的方法来设计和分析在各种形式的不确定性、复杂目标以及以原则性方式考虑利益相关者价值判断的目标下运行的动态匹配市场。 这项研究将改进现有系统并开拓新市场。 它将直接解决现实世界匹配系统（例如肾脏交换）中的问题，并将改善现场肾脏分配系统和其他市场的公平性、经济效率和目标的道德一致性。 该项目还将为重新设计计算机科学系和博士后工作匹配市场奠定基础；它将开始开发原则性的系统，以促进大学招生以及定量和技术招聘的多样性。 作为这项研究的副产品开发的开源软件解决方案将向公众开放，结果将与教育工作者沟通。该项目将通过开发可扩展的基于人工智能的方法来设计和分析这些市场，从而大大增加传统上通过微观经济理论解决的匹配市场设计的广度。 反过来，匹配市场将成为开发有原则的、可扩展的、基于通用优化的算法（用于不确定性下的决策）的动力和灵感，以及基于人工智能的通用方法，用于将系统与引发的利益相关者价值判断相结合。 研究将在以下三个方向取得进展：1）管理短期不确定性的原则方法。 通常，必须在有关环境的所有信息公开之前做出决定。 该项目将采用基于人工智能的方法在不确定性下做出决策；具体来说，它将设计和创建有原则的方法来学习（以一定成本）环境，这些方法与计算鲁棒匹配策略的新颖方法相结合。2）学习通过动态匹配来平衡公平和效率。 许多匹配市场是动态的：参与者随着时间的推移到达和离开，他们之间的关系以可预测的方式发展。 通过强化学习和近似动态规划，该项目将开发有原则且实用的方法来学习匹配政策，这些政策既提供经济效率收益，又提供公平和/或促进多样性的保证。3) 与人类价值判断保持一致。基于人工智能的匹配方法需要一个优化目标。 定义该目标涉及人类利益相关者（每个人都有自己的价值判断）和自动化系统之间的反馈循环。 这项研究将把人类利益相关者的价值判断整合到自动匹配和资源分配系统中。该奖项反映了 NSF 的法定使命，并通过使用基金会的智力优点和更广泛的影响审查标准进行评估，被认为值得支持。

Markets are systems that empower interested parties -- humans, firms, governments, or autonomous agents -- to exchange goods, services, and information. Due to logistical or societal constraints, many markets, e.g., school choice, rideshare, medical residency, advertising, cadaveric organ allocation, online labor, public housing, refugee placement, as well as barter markets such as kidney exchange, cannot rely solely on prices to match supply and demand. This project will develop connections between artificial intelligence (AI) and matching market theory and practice. Specifically, it will create practical methods for the design and analysis of dynamic matching markets operating under various forms of uncertainty, with complex goals, and under objectives that take into account stakeholders' value judgments in a principled way. This research will improve existing systems as well as enable new markets. It will directly address problems in real-world matching systems such as kidney exchange and will lead to improvements in fairness, economic efficiency, and ethical alignment of objectives in fielded kidney allocation systems and other markets. This project will also lay the groundwork for a redesign of the computer science faculty and post-doc job matching market; and it will begin developing principled systems to promote diversity in university admissions, as well as quantitative and technical hiring. Open source software solutions developed as a byproduct of this research will be made available to the public, and results will be communicated with educators.This project will substantially increase the breadth of matching market design, traditionally addressed via microeconomic theory, by developing scalable AI-based methods for designing and analyzing these markets. In turn, matching markets will serve as impetus and inspiration for the development of principled and scalable general optimization-based algorithms for decision making under uncertainty, as well as general AI-based methods for alignment of systems with elicited stakeholder value judgments. The research will make progress in the following three directions:1) Principled approaches to managing short-term uncertainty. Often, decisions must be made before all information about the environment is revealed. This project will take an AI-based approach to decision making under uncertainty; specifically, it will design and create principled methods to learn (at some cost) about the environment that tie into novel methods for computing robust matching policies.2) Learning to balance fairness and efficiency through dynamic matching. Many matching markets are dynamic: participants arrive and depart over time, and relationships between them evolve in predictable ways. Via reinforcement learning and approximate dynamic programming, this project will develop principled and practical ways to learn matching policies that provide both economic efficiency gains alongside fairness and/or diversity-promoting guarantees.3) Alignment with human value judgments. AI-based matching methods require an objective to optimize. Defining that objective involves a feedback loop between human stakeholders---each with their own value judgments---and automated systems. This research will meld techniques for aggregating value judgments of human stakeholders into automated matching and resource allocation systems.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.