Seminar Details

Many stochastic optimization problems from algorithmic mechanism design and operations research involve a principal or seller optimizing with respect to a subsequent choice by an agent or buyer. Examples include posted pricing for a unit-demand buyer with independent values, assortment optimization with independent utilities, and delegated choice. We study these settings through a common framework that we call Utility Configuration. Within this framework, we obtain polynomial-time approximation schemes that improve the state of the art. A key technical insight driving our results is an economically meaningful property we term utility alignment. Informally, a problem is utility aligned if, at optimality, the principal derives most of their utility from realizations where the agent’s utility is also high. Utility alignment allows the algorithm designer to focus on maximizing performance on realizations with high agent utility, which is often an algorithmically simpler task. We prove utility alignment results for all the problems mentioned above, including strong results for unit-demand pricing and delegation, as well as a weaker but very broad guarantee that holds for many other problems under very mild conditions. We also discuss recent extensions to multichoice delegation.