CAREER: Scalable and Robust Dynamic Matching Market Design

University Of Maryland, College Park, College Park MD

Investigators

Abstract

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.