Abstract:
Fair division is the problem of allocating a set of items among agents in a fair and efficient manner. This age-old problem, mentioned even in the Bible, arises naturally in a wide range of real-life settings. Division based on competitive equilibrium (CE) has emerged as one of the best mechanisms for this problem. The existence and computability of CE have been extensively studied when all items are disposable goods, while the problem is less explored when some of them are nondisposable chores (bads). In this talk, I will discuss recent algorithmic advances on the computation of CE when each item may be a good, a chore, or both (mixed).
I will first consider the case of linear utilities. When all items are goods, the CE set is well-known to be captured by convex programming formulations and thereby forms a convex set. In sharp contrast, with only chores, the CE set may be nonconvex and disconnected. In particular, it is the set of local optima of a non-convex programming formulation with ``open constraints''. I will discuss how to handle this non-convexity through a novel exterior-point method to find an approximate CE in polynomial time (FPTAS). Next, I will briefly sketch how to extend this method to work with 1-homogeneous utility functions and mixed manna. Finally, I will discuss the complexity of the problem in the more general exchange model a.k.a. barter system.
Based on joint works with S. Boodaghians, B. R. Chaudhury, J. Garg, and P. McGlaughlin.
Bio:
Ruta Mehta is an Assistant Professor of Computer Science at the University of Illinois at Urbana-Champaign. Prior to joining UIUC, she was a postdoctoral fellow at the Simons Institute, UC Berkeley, and at the College of Computing, Georgia Tech. She did her Ph.D. from the Indian Institute of Technology Bombay, India. Her research interests lie in theoretical computer science and its interface with economics, games theory, fair division, and learning. For her research, she has received the NSF CAREER Award, the Simons-Berkeley Research Fellowship, and the Best Postdoctoral Award (given by CoC@GT). Her Ph.D. thesis won the ACM India Doctoral Dissertation Award and the IIT-Bombay Excellence in Ph.D. Thesis Award.
