Date:
Location:
Ruta Mehta will be presenting at the EconCS seminar meeting this Friday, 3/11, at 1 pm ET. The seminar will be held Zoom only, accessible at the usual link here. Hope to see you there :).
Title: Fair division of goods, bads, and mixed.
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, for example, partnership dissolution, sharing of satellites, and dividing costs for climate resilience. 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). This method is general enough to work with any coordinate-wise monotone function. Finally, I will discuss extensions to 1-homogeneous utility functions and mixed-manna and recent developments.