Computing Lindahl Equilibrium for Public Goods with and without Funding Caps
April 24 @ 12:00 pm - 5:00 pm
Speaker: Dominik Peters
Abstract: Lindahl equilibrium is a solution concept for allocating a fixed budget across several divisible public goods. It always lies in the core, meaning that the equilibrium allocation satisfies desirable stability and proportional fairness properties. We consider a model where agents have separable linear utility functions over the public goods, and the output assigns to each good an amount of spending, summing to at most the available budget.
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. 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 running mirror descent on our new formulation gives rise to a proportional response dynamics, which converges rapidly to an equilibrium. Our new formulation 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. 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.
Short bio: Dominik Peters is a CNRS researcher at Université Paris Dauphine – PSL, working on computational social choice. After postdocs with Ariel Procaccia (Harvard) and Nisarg Shah (Toronto), he is studying topics in voting theory with a focus on proportional representation and participatory budgeting, as well as fair division problems. With his collaborators, he has proposed the Method of Equal Shares, a voting method that is now used by several cities across Europe to allow their citizens to influence how the city government spends its budget.
https://dominik-peters.de/
https://dominik-peters.de/