Competitive Equilibrium with Chores: Non-convex programs, Algorithms, and Dynamics

Ruta Mehta ( University of Illinois )

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, computability, and market dynamics have been extensively studied for CE 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 computational and dynamic aspects 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. Finally, I will discuss some intriguing behavior of natural price-adjustment dynamics of tatonnement in these markets.

Based on joint works with Shant Boodaghians, Bhaskar Ray Chaudhury, Christian Kroer, and Tianlong Nan.