Computing Lindahl Equilibrium with and without Funding Caps

Christian Kroer, Dominik PetersCFD @ IJCAI 2025 · OpenReview

TL;DR

This paper introduces a novel convex programming framework for efficiently computing Lindahl equilibria, a fair and stable allocation mechanism for public goods. Crucially, this framework extends to settings with funding caps on individual public goods, resolving a long-standing open problem and enabling practical applications in areas like participatory budgeting.

What Problem Does This Paper Address?

The paper tackles the challenge of computing Lindahl equilibria, a concept from cooperative game theory that ensures fair and stable resource allocation for public goods. While Lindahl equilibria are known to be desirable (lying in the "core" of the game), their computation has been difficult, especially when individual public goods have funding limits (caps). In the "uncapped" setting (no funding limits), Lindahl equilibria are equivalent to maximizing Nash social welfare, which has known computational methods. However, when caps are introduced, this equivalence breaks down, and efficient computation of Lindahl equilibria becomes an open problem. This is a significant issue for real-world applications like participatory budgeting, where funds are often allocated to projects with specific budget constraints.

Methods

The authors introduce a new convex programming formulation for computing Lindahl equilibria. For the uncapped setting, they show this new formulation is related to the standard Nash welfare maximization problem through duality and reformulation. They also demonstrate that the "proportional response dynamics," a known algorithm for computing Lindahl equilibria in the uncapped setting, is equivalent to running mirror descent on their new convex program. This connection provides a new and direct proof of the dynamics' convergence.

The key innovation is how they handle the capped setting. They show that their new convex program can be directly adapted by adding the cap constraints. This modified program then correctly computes Lindahl equilibria, effectively solving the open problem of efficient computation in capped scenarios. This is a significant departure from previous approaches, where adding caps to Nash welfare maximization programs did not yield Lindahl equilibria.

Datasets

Not discussed in the paper. The paper mentions using "participatory budgeting datasets in the Pabulib repository" for experimental evaluation, but does not detail specific datasets or their characteristics beyond mentioning instances from Warsaw and Amsterdam.

Key Insights and Ideas

  • Unified Framework: The paper presents a single convex programming framework that elegantly handles both uncapped and capped public goods settings, unifying previously disparate computational approaches.
  • Mirror Descent Connection: Establishing the equivalence between the proportional response dynamics and mirror descent on their new convex program provides a deeper theoretical understanding of why the dynamics converge and offers a new way to prove convergence rates.
  • Capped Setting Breakthrough: The most significant insight is that their convex program, when augmented with cap constraints, correctly computes Lindahl equilibria. This is a non-trivial result, as similar additions to Nash welfare maximization programs fail to achieve this. This suggests their formulation captures the essential properties of Lindahl equilibria that are robust to caps.
  • Demystifying Dynamics: The connection to mirror descent demystifies the "surprising" numerical performance of proportional response dynamics, showing it's a principled optimization algorithm.

Key Results

  • Efficient Computation for Capped Settings: The paper establishes that Lindahl equilibria can be efficiently computed in the capped public goods setting, resolving an open problem posed by Fain et al. (2016).
  • New Convex Program: A novel convex program is introduced that captures Lindahl equilibria in both uncapped and capped settings.
  • Proportional Response Dynamics Explained: The paper proves that the proportional response dynamics for uncapped public goods is equivalent to mirror descent on their new convex program, providing a new proof of convergence and a convergence rate of $O(\log(nm)/t)$.
  • Experimental Validation: Numerical experiments on participatory budgeting data demonstrate the feasibility of solving their convex program for capped settings, even for large instances.

Limitations and Future Work

  • Strategic Behavior: The paper focuses on computational aspects and does not address strategic behavior or manipulation of Lindahl equilibrium mechanisms, which is a known challenge due to informational requirements.
  • Uniqueness in Utilities: While the uncapped setting guarantees unique Lindahl equilibria (for a given set of utilities), the paper notes that in the capped setting, Lindahl equilibria are not necessarily unique in utilities, and their proposed program selects a specific subset.
  • Dynamics for Capped Settings: The authors leave open the question of whether a nice closed-form update can be derived for a mirror descent-like dynamics in the capped setting, as their current approach relies on general convex optimization solvers.
  • Generalizing Caps: The paper suggests future work on generalizing cap constraints to sets of public goods, which could model more complex decision-making scenarios.
  • Approximation Bounds: The authors believe their work could lead to better approximation bounds for discrete public goods models by analyzing the structure of their convex program.

Summary updated

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. 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, thereby providing a new and very immediate proof of the convergence guarantee for the dynamics. 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. 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.
BibTeX
@inproceedings{kroer2025computing,
  author = {Christian Kroer and Dominik Peters},
  title = {{Computing Lindahl Equilibrium with and without Funding Caps}},
  booktitle = {CFD @ IJCAI},
  year = {2025},
  url = {https://openreview.net/forum?id=gsriBi4Xzn},
}
Figure