CAREER: Incentives, Fairness, and Efficiency without Monetary Transfers

Purdue University, West Lafayette IN

Investigators

Abstract

This award is funded in whole or in part under the American Rescue Plan Act of 2021 (Public Law 117-2). The Internet and the vast increase in the availability of data have transformed algorithm design, as well as computer science in general. From computational resources and advertising space, to food donations, loans, kidneys, and vaccines, algorithms are increasingly being used to decide how scarce resources are allocated. As opposed to traditional optimization, the input to these algorithms must be solicited from strategic agents, with their own, private preferences over the algorithm's output. And, from resource allocation in the cloud and spectrum auctions to tournaments in major sporting events (such as the Olympics), it is well-understood that these strategic entities will behave to optimize their own benefit to the extent possible while still “following the rules,” leading to unpredictable final outcomes. At the same time, unlike traditional optimization, in many of these modern applications, system designers must also consider whether their system is equitable among its participants. Classic work in Economics, as well as extensive work in the intersection of Computer Science and Economics, provides a rich toolkit for designing algorithms that are immune to strategic manipulations as well as algorithms that balance fairness and efficiency. This project aims to advance and develop this theory with a focus on domains where monetary transfers are not allowed, by taking aim at several fundamental open questions. The project also contains plans to design, develop, and deploy a system that is based on the proposed theoretical research and that serves the local community by enabling local non-profit organizations that fight hunger to allocate their food donations in a more efficient manner. The project will expand the reach of theory into areas where there is a major gap in current understanding, by taking aim at several key theoretical questions in the following three complementary thrusts. (1) Foundations of mechanism design without money. The project takes aim at fundamental questions in this space, with the goal of developing tools for designing truthful mechanisms for a number of paradigms: divisible and indivisible goods, static and dynamic environments, worst-case and Bayesian objectives. (2) Mechanism design with imperfect rationality. There are important domains in which protecting against fully rational, expected utility-maximizing participants is overly cautious. This project puts forward and explores several possibilities for modeling imperfect rationality. (3) Mechanism design with imperfect expressivity. Eliciting complex utility functions is often infeasible, e.g., because of agents' cognitive limitations. The project explores the trade-off between expressiveness and ease of elicitation in mechanism design without money. 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.