Competitive equilibrium is arguably one of the most fundamental solution concepts within Economics with applications in diverse domains such as ensuring fair and efficient allocation of scarce resources. The existence and computability of CE have been extensively studied when all items are disposable goods. The problem is less explored when some are non-disposable chores (bads), despite being equally relevant, for example, the various labor markets. In this talk, I will discuss recent algorithmic advances in the computation of CE when the item set includes chores.
Surprisingly, this problem stands in sharp contrast to the goods-only case, even under linear (additive) utility functions: for the case of goods, the CE set is known to be a convex set, while with chores, it may be non-convex and disconnected. I will discuss how to handle this non-convexity through new (continuous) optimization methods, and via a novel non-convex formulation, leading to FPTASs. These methods may be of independent interest for finding local optima of certain classes of non-convex programs.
Based on joint works with Shant Boodaghians, Bhaskar Ray Chaudhury, Christian Kroer, and Tianlong Nan.
Short Bio: Ruta Mehta is an Associate Professor of Computer Science at the University of Illinois at Urbana-Champaign. Her research interests lie in theoretical computer science and its interface with economics, games theory, fair division, and learning. Prior to joining UIUC, she was a postdoctoral fellow at the Simons Institute, and at the College of Computing, Georgia Tech advised by Prof. Vijay Vazirani. She did her Ph.D. at the Indian Institute of Technology, Bombay, India, under Prof. Milind Sohoni and Prof. Bharat Adsul. She serves on the editorial boards of Math. of Operations Research (MOR) and Algorithmica. For her research, she has received the NSF CAREER Award, the Simons-Berkeley Research Fellowship, and the Best Postdoctoral Researcher 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.
