CAREER: Elicitation and Computational Challenges in Algorithmic Resource Allocation

This project aims to develop algorithms and theoretical analysis for large-scale resource allocation, which involves distributing resources among various users, applications, or tasks. This process is essential in many contexts, including scheduling work shifts, providing aid during disasters, assigning courses to students, matching research papers with reviewers, and many other scenarios requiring distribution of goods, resources, or services. A key example is optimizing worker shift assignments to maximize efficiency while ensuring a balanced distribution of workloads among staff. Another example is coordinating the distribution of supplies and volunteers during disaster relief efforts to ensure that aid reaches those in need as quickly and effectively as possible. By improving resource allocation strategies, the project aims to enhance operational efficiency while achieving balanced distributions of resources to meet the needs of individuals and organizations across various fields. To achieve this, the project tackles three core challenges: (1) Effective Preference Elicitation – In many domains, users have complex preferences. For instance, a worker might be able to take either shift A or B but not both. This research direction focuses on developing methods to gather agent preferences effectively while minimizing cognitive burden. (2) Preference Uncertainty – Users may be uncertain about their preferences. For example, when assigning students to courses, match quality is inherently uncertain. The goal of this project is to develop allocation mechanisms that account for such inaccuracies in agent preferences. (3) Efficient Computation – Scaling algorithms to handle large problem instances is critical. For example, scheduling shifts in large organizations may involve hundreds of workers and thousands of shift slots. The project aims to design computational frameworks that produce balanced and efficient outcomes in such scenarios. The project will yield practical software tools that enhance AI-driven resource allocation. The educational activities will contribute to curriculum development on collective decision-making and further equip graduate students with essential academic skills, including public speaking, research methodologies, and scholarly writing. By integrating techniques from machine learning and optimization, this research takes a comprehensive approach to resource allocation. It examines the full process from preference elicitation to algorithmic implementation and output guarantees. Specifically, the project will: (a) investigate methods for eliciting expressive yet tractable agent preferences; (b) explore automated prompting techniques to incentivize more complete preference reporting; (c) model preference uncertainty using learning-theoretic and statistical approaches; (d) develop simple, interpretable algorithms adaptable to various problem domains; and (e) ensure that final allocations are balanced, efficient, and robust. Through this interdisciplinary effort, the project seeks to advance the theoretical foundations and practical applications of balanced and efficient resource allocation. 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.