CAREER: Multidimensional Utility Maximization when Ordeals are Payments

This CAREER award focuses on designing mechanisms that allocate resources in a way that maximizes "consumer utility," defined as the value of the allocation received minus the payments made. This is particularly important in social services, or generally when charging monetary payments is infeasible. In such cases, to ration demand or prove user need, a non-monetary cost is imposed on consumers, such as waiting in line or filling out labor-intensive paperwork.

The project explores trade-offs between efficient allocation and the burdens imposed on individuals, aiming to develop simple, explainable mechanisms guiding principles on when to use these mechanisms in practice. Through this project, the investigator will also (1) build research communities locally with workshops and online via reading groups, (2) broaden participation in computing through mentoring, awareness, and recruitment, and (3) develop educational materials based on this project's research.

This project will pioneer the field of multidimensional algorithmic utility maximization when ordeals are payments. With an objective of expected (Bayesian) social welfare minus revenue, this optimization problem introduces tension between efficiently allocating and using payments to do so. Allocating multiple items only complicates the problem, as reducing an item's allocation can sometimes yield more utility than charging payments.

The investigation is organized into three thrusts: (1) characterize utility-optimal mechanisms, proving their intractability and solving for optimal mechanisms at the frontier of tractability, (2) approximate optimal utility by upper-bounding the quantity and designing simple, practical mechanisms with provable guarantees, and (3) apply the theory of utility maximization and ordeals to practical domain-specific questions.

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.