Computing Lindahl Equilibrium for Public Goods with and without Funding Caps
Abstract: I will present recent work on computing Lindahl equilibrium, a competitive equilibrium analogue for the allocation of a fixed budget towards divisible public goods. The Lindahl equilibrium is guaranteed to lie in the core, and therefore guarantees both efficiency and fairness properties. I will present two settings: the uncapped and capped setting.
In the uncapped setting, each of the public goods can absorb any amount of funding. In this case, it is known that Lindahl equilibrium is equivalent to maximizing Nash social welfare, and this allocation can be computed by a public-goods variant of the proportional response dynamics. We introduce a new convex programming formulation for computing this solution and show that it is related to Nash welfare maximization through duality and reformulation. We then show that the proportional response dynamics is equivalent to running mirror descent on our new formulation, which has similarities to Shmyrev's convex program for Fisher market equilibrium.
In the capped setting, each public good has an upper bound on the amount of funding it can receive, which is a type of constraint that appears in fractional committee selection and participatory budgeting. In this setting, existence of Lindahl equilibrium was only known via fixed-point arguments. The existence of an efficient algorithm computing one has been a long-standing open question. We prove that our new convex program continues to work when the cap constraints are added, and its optimal solutions are Lindahl equilibria. Thus, we establish that Lindahl equilibrium can be efficiently computed in the capped setting.
Biography: 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.