9/12/24 | 4:15pm | E51-149
Christian Kroer
Associate Professor
Columbia University
Abstract: We will discuss the problem of how to fairly allocate m chores (or bads) among n agents. We take the approach of competitive equilibrium from equal incomes (CEEI), which is known to lead to strong fairness and optimality properties. CEEI is famously computable in the goods setting via the Eisenberg-Gale convex program. For chores, one may similarly find a CEEI through finding non-zero stationary points of a non-convex program that minimizes the geometric mean of agent disutilities. To date, practical algorithsm for this non-convex program have eluded researchers. We introduce an analogue of the Eisenberg-Gale dual for chores, and show that, while it is not a dual of the non-convex primal program in a formal sense, the solution sets coincide. We then derive a new redundant constraint for the dual, which restricts optimization to a hyperplane that avoids directions of unbounded objective, which have been a principal hindrance for solving the primal program. We next introduce a greedy Frank-Wolfe algorithm for this program and show a new state-of-the-art convergence rate to competitive equilibrium. We show through numerical experiments that our method is highly practical.
Bio: Christian Kroer is an Associate Professor of Industrial Engineering and Operations Research at Columbia University, as well as a member of the Data Science Institute at Columbia. His research interests are at the intersection of operations research, economics, and computation, with a focus on how optimization and AI methods enable large-scale economic solution concepts. He obtained his Ph.D. in computer science from Carnegie Mellon University, and spent a year as a postdoc with the Economics and Computation team at Facebook Research. He is the recipient of an ONR Young Investigator award and an NSF CAREER award.