CAREER: Scalable and Robust Dynamic Matching Market Design

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

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.