CAREER: Fair and Efficient Market Design at Scale

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.