<figure><img src="image_1.png" /></figure>

HAL
open science

# Computing Lindahl Equilibrium for Public Goods with and without Funding Caps

Christian Kroer, Dominik Peters

► To cite this version:

Christian Kroer, Dominik Peters. Computing Lindahl Equilibrium for Public Goods with and without Funding Caps. EC '25: 26th ACM Conference on Economics and Computation, Jul 2025, Stanford, United States. pp.129-129, 10.1145/3736252.3742510. hal-05367819

HAL Id: hal-05367819

https://hal.science/hal-05367819v1

Submitted on 17 Nov 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Computing Lindahl Equilibrium for Public Goods with and without Funding Caps

CHRISTIAN KROER, Columbia University, christian.kroer@columbia.edu

DOMINIK PETERS, CNRS, Université Paris Dauphine - PSL, dominik.peters@lamsade.dauphine.fr

Lindahl equilibrium is a solution concept for allocating a fixed budget across several divisible public goods. It always lies in the weak 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, 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 double 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. 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, 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 approximate Lindahl equilibrium can be efficiently computed in the capped setting to any desired accuracy. Our result also implies that approximately core-stable allocations can be efficiently computed for the class of separable piecewise-linear concave (SPLC) utilities.
CONTENTS

<table><tr><td>1</td><td>Introduction</td><td>3</td></tr><tr><td>1.1</td><td>Contributions</td><td>4</td></tr><tr><td>1.2</td><td>Related Work</td><td>6</td></tr><tr><td>2</td><td>Setup</td><td>7</td></tr><tr><td>2.1</td><td>Lindahl Equilibrium</td><td>7</td></tr><tr><td>2.2</td><td>Pareto-Optimality and the Core</td><td>10</td></tr><tr><td>3</td><td>Convex Optimization Background</td><td>12</td></tr><tr><td>4</td><td>Uncapped Public Goods</td><td>14</td></tr><tr><td>4.1</td><td>Nash Welfare and the Eisenberg-Gale Program</td><td>14</td></tr><tr><td>4.2</td><td>A New Convex Program</td><td>16</td></tr><tr><td>4.3</td><td>Connecting the Nash Social Welfare Program to Our New Program via Duality</td><td>17</td></tr><tr><td>4.4</td><td>A Possible Path to Tâtonnement for Public Goods</td><td>18</td></tr><tr><td>4.5</td><td>Proportional Response Dynamics as Mirror Descent</td><td>19</td></tr><tr><td>4.6</td><td>Convergence Rates</td><td>21</td></tr><tr><td>5</td><td>Capped Public Goods</td><td>24</td></tr><tr><td>5.1</td><td>Adapting the Convex Program</td><td>25</td></tr><tr><td>5.2</td><td>The Convex Program computes a Lindahl Equilibrium</td><td>25</td></tr><tr><td>5.3</td><td>Approximately Optimal Solutions</td><td>28</td></tr><tr><td>5.4</td><td>Discussion of the Convex Program</td><td>30</td></tr><tr><td>5.5</td><td>Computation and Experiments</td><td>31</td></tr><tr><td>5.6</td><td>Computing Core Allocations for Separable Piecewise-Linear Concave Utilities</td><td>32</td></tr><tr><td>6</td><td>Conclusion</td><td>33</td></tr><tr><td></td><td>Acknowledgments</td><td>34</td></tr><tr><td></td><td>References</td><td>34</td></tr><tr><td>A</td><td>Convex Conjugates and Subdifferentials of Some Useful Functions</td><td>39</td></tr><tr><td>B</td><td>Approximately Optimal Solutions</td><td>40</td></tr><tr><td>B.1</td><td>Uncapped Public Goods</td><td>41</td></tr><tr><td>B.2</td><td>Capped Public Goods</td><td>46</td></tr></table>
# 1 Introduction

We consider a setting where a fixed budget $B > 0$ needs to be spent on $m$ divisible public goods. Thus, an outcome is a vector $x = (x_1, \dots, x_m) \in \mathbb{R}_{\ge 0}^m$ summing to at most $B$. Some of the public goods may additionally have caps, i.e., upper bounds on the amount of funding they can receive. How to distribute the spending across the goods is decided based on the preferences of $n$ agents. We will consider agents with separable linear utility functions over the goods. Agents may have heterogeneous weights (which can be interpreted as endowments). We will study the solution concept of Lindahl equilibrium, which is based on a virtual market with personalized prices [Foley, 1970]. This equilibrium notion is known to lead to allocations that are fair to voters, formalized via the concept of the core from cooperative game theory [Fain et al., 2016].

The classic economics literature on public goods, starting with Samuelson [1954], focuses on how to arrive at the socially efficient amount of spending in the face of free-riding incentives. In contrast, we consider a fixed budget and are mostly concerned with how to divide it between different public goods. This approach, sometimes called *portioning* or *fair mixing*, has received increasing attention in computer science over recent years [see, e.g., Airiau et al., 2023, Aziz et al., 2020, Brandl et al., 2021, Fain et al., 2016], due to its many concrete applications. These include *participatory budgeting*, a method used by many cities to let residents vote over how the government will spend a fixed part of its budget [Aziz and Shah, 2021, Rey and Maly, 2023], and *donation platforms*, where donors can influence the distribution of a fixed matching fund [Brandl et al., 2022, Brandt et al., 2024]. The model also captures *committee elections* (i.e., multiwinner voting) in its fractional version [Aziz et al., 2023a, Suzuki and Vollen, 2024], as well as the *cake sharing* problem [Bei et al., 2024]. Voting methods for the public goods model can also be used to settle small-stakes issues such as a lecturer letting students vote over the distribution of class time across topics, or a team to vote over the frequencies with which they will go to different lunch venues. Companies and non-profit organizations can use the principles derived in this model to decide how to fairly and efficiently divide resources among units or grantees.

In many of these applications, it is desirable to select an outcome that is *representative* of the voters, in that every agent has an equal influence on the overall spending (or an influence that is proportional to the weight assigned to the agent). This can be formalized as a group fairness guarantee. In particular, we can require that the spending distribution lie in the (weak) core, which means that no subset of voters can construct an alternative way of spending their endowments in a way that they all prefer. We know that an outcome in the (weak) core always exists thanks to Foley [1970], who gave a definition of what he called *Lindahl equilibrium* (because he was inspired by ideas of Lindahl [1919]), proved its existence, and showed that it always lies in the core. This result was introduced to the computer science literature by Fain et al. [2016].

In the setting where each public good has no cap on funding (we call this the *uncapped setting*), Fain et al. [2016] showed that Lindahl equilibrium is equivalent to the rule that maximizes Nash social welfare (i.e., the product of agent utilities). The Nash rule has its roots in the Nash [1950] bargaining solution, and its objective function has attractive mathematical properties such as scale-freeness [Moulin, 2004]. The Nash rule as applied to the public goods model had already been discussed earlier and independently of Lindahl equilibrium due to its attractive group fairness properties [Bogomolnaia et al., 2005, Guerdjikova and Nehring, 2014]. The connection between Lindahl equilibrium and the Nash rule is convenient since the latter can be efficiently computed via a convex program reminiscent of the classic Eisenberg-Gale program [Eisenberg, 1961, Eisenberg and Gale, 1959] for computing a market equilibrium for private goods. In addition, Brandl et al. [2022] showed that the Nash rule can be computed by running a simple proportional response dynamics which converges to the Nash outcome. They pointed out that the same convex program
had been considered in several unrelated contexts such as in the portfolio selection literature, where
this dynamics had also been discovered and shown to converge [Cover, 1984]. While the dynamics
converges rapidly in practice, a formal bound on the speed of convergence had not been established
by 2022, with Li et al. [2018, page 11] noting that the “algorithm [of Cover] possesses a guarantee
of convergence but [no] convergence rate.”

In the capped setting, where each public good may have a cap on how much funding it can receive, the Nash rule loses its fairness properties and is not equivalent to Lindahl equilibrium. In contrast, Lindahl equilibrium retains its fairness properties, and its existence is known via fixed-point theorems [Foley, 1970]. However, this existence result only applies to strictly monotonic utility functions and thus does not allow agents to have valuations equal to 0 for some goods, and it does not allow for caps except through approximating them through appropriate ‘saturating’ utility functions [Fain et al., 2016, Munagala et al., 2022b]. Most importantly, the existence result is not algorithmic, and how to compute a Lindahl equilibrium was an open question. Fain et al. [2016] asked: “Is computing the Lindahl equilibrium for public goods computationally hard or is there a polynomial time algorithm even [when the public goods are capped]?”

Since then there has been no progress on this question. Indeed, Jiang et al. [2020] again noted
that “we do not know how to compute the Lindahl equilibrium efficiently”. It was even open how to
compute any allocation that lies in the core, not necessarily a Lindahl equilibrium allocation. Cheng
et al. [2020] noted that “it is not known how to compute such a core outcome efficiently even for [...]
approval set utilities”, and Suzuki and Vollen [2024] concluded that “there is no known polynomial
time algorithm for computing fractional core”. The need for a practical algorithm was particularly
pressing in the work of Munagala et al. [2022b] who studied indivisible public goods and were
aiming for allocations that are approximately in the core. Their best result is based on rounding a
Lindahl equilibrium allocation and “yields a 9.27-core, though we do not know how to implement
the resulting algorithm in polynomial time”. To obtain a polynomial-time result, Munagala et al.
[2022b] needed to avoid Lindahl equilibrium and in that case only achieved a 67.37-approximation.

## 1.1 Contributions

In the uncapped setting, we prove that the proportional response dynamics converges to a Lindahl
equilibrium at a rate of log(*nm*)/*t*. We show this by developing a new convex program, distinct
from the standard Eisenberg-Gale-style program for Nash welfare maximization, and then showing
that applying mirror descent to this program is equivalent to the proportional response dynamics,
thereby allowing us to obtain the convergence rate from known results about mirror descent.<fnref n="1" /> We
also show that the dynamics converges to an allocation that approximates the proportional fairness
condition as well as the core.

Our new convex program is related to the Eisenberg-Gale-style program through double duality: we show that it can be obtained by taking the dual, introducing new redundant variables, making a change of variable, and performing another dual derivation on this reformulated dual. The duality and mirror descent relationship that we discover for public goods mirrors existing relationships known in the literature on private goods allocation using Fisher market equilibrium. For the private-good setting, equilibrium is also equivalent to maximizing Nash welfare. An alternative convex program for this equilibrium was developed by Shmyrev [1983, 2009]. A proportional response dynamics exists for the private goods case as well [Wu and Zhang, 2007, Zhang, 2011], and Birnbaum

<footnote n="1">¹While writing the paper, we became aware that Zhao [2023] has recently obtained the same convergence rate bound of log(nm)/t. He obtained the convergence rate via a direct first-order analysis of the multiplicative gradient (MG) method. Zhao notes that “the extraordinary numerical performance of the MG method is rather surprising and somewhat mysterious [because it] is extremely simple”. Our results demystify the performance of the dynamics, by showing that it is equivalent to mirror descent, but on a different convex program.</footnote>
Private goods

$$ \max_{x \ge 0} \sum_{i \in N} B_i \log \langle v_i, x_i \rangle $$

$$ \text{s.t.} \quad \sum_{i \in N} x_{ij} \le 1 \quad \text{for all } j \in M $$

$$ \max_{b \ge 0, p \ge 0} \sum_{i \in N, j \in M} b_{ij} \log v_{ij} - \sum_{j \in M} p_j \log p_j $$

$$ \text{s.t.} \quad \sum_{j \in M} b_{ij} = B_i \quad \text{for all } i \in N $$

$$ \sum_{i \in N} b_{ij} = p_j \quad \text{for all } j \in M $$

The final allocation is obtained as $x_{ij} = b_{ij}/p_j$.

(a) The Eisenberg-Gale program.

(b) The Shmyrev program.

Public goods

$$ \max_{x \ge 0} \sum_{i \in N} B_i \log \langle v_i, x \rangle $$

$$ \text{s.t.} \quad \sum_{j \in M} x_j \le B $$

$$ \max_{b \ge 0, x \ge 0} \sum_{i \in N, j \in M_i} b_{ij} \log v_{ij} - \sum_{i \in N, j \in M_i} b_{ij} \log \frac{b_{ij}}{x_j} $$

$$ \text{s.t.} \quad \sum_{j \in M_i} b_{ij} = B_i \quad \text{for all } i \in N $$

$$ \sum_{i \in N_j} b_{ij} = x_j \quad \text{for all } j \in M $$

(c) The Nash welfare program.

(d) Our program.

<caption>Fig. 1. Comparison of convex programs for computing Fisher market equilibrium (private goods) and Lindahl equilibrium (public goods) for instances with linear utility functions.</caption>

et al. [2011] showed that it is equivalent to mirror descent on the Shmyrev program. Our new program for the uncapped public goods setting is “Shmyrev-like” in its structure. A comparison of these convex programs is shown in Figure 1. We think it is surprising that it is possible to establish these analogous results, since there are important structural differences in the convex programs. For example, for private goods, the convex programs always have rational optimal solutions, while for public goods they may be irrational. In addition, for private goods, the Eisenberg-Gale program has the same number of variables (nm) as the Shmyrev program (after eliminating redundant price variables), while for public goods the Eisenberg-Gale-style program has m variables whereas our new convex program has nm variables. This dimensional difference means that new insights are required for transforming one program into the other through duality. Finally, the nonlinear term in the objective is a somewhat unusual normalized entropy function in our program, whereas it is the usual entropy on the prices in the private goods case.

In the capped setting, we answer the open problem raised by Fain et al. [2016] positively: Lindahl equilibrium can be computed efficiently in the capped setting. Indeed, the caps can be naturally added as constraints to our new convex program, and the resulting program correctly computes a Lindahl equilibrium respecting the caps. (In contrast, as is well-known, adding caps as constraints to the Nash welfare program does not lead to a Lindahl equilibrium.) This also establishes the existence of exact Lindahl equilibrium with caps, without approximations. We also show that approximately optimal solutions to our program form approximate Lindahl equilibria. Thus, using our convex program, an approximate Lindahl equilibrium can be computed in polynomial time
using the ellipsoid method (to any desired accuracy), and it can be computed efficiently in practice by standard solvers with support for exponential cones, such as MOSEK. We present numerical experiments on real-life data from participatory budgeting, showing that solving our program is feasible even for large instances. Finally, we show how to apply our result to compute approximately core-stable allocations for a broader class of utility functions, namely separable piecewise-linear concave utilities (SPLC).

## 1.2 Related Work

**Lindahl equilibrium.** Lindahl equilibrium was introduced by Foley [1970], who named this equilibrium concept after Lindahl [1919] who put forward related ideas of personalized taxation. However, note that there are other distinct ways of formalizing Lindahl's ideas [see van den Nouweland, 2015], including ratio and cost share equilibrium [Kaneko, 1977, Mas-Colell and Silvestre, 1989]. In this work, we use the Foley definition.

**Uncapped setting.** Our interest in Lindahl equilibrium is motivated mainly by their proportional fairness properties (notably the core). Such fairness properties have been studied in many related models, notably the “fair mixing” or “portioning” models [Airiau et al., 2023, Aziz et al., 2020, Bogomolnaia et al., 2005, Brandl et al., 2021, Fain et al., 2016, Gul and Pesendorfer, 2025] that correspond to what we call the uncapped setting. In this setting, Lindahl equilibrium coincides with the maximum Nash welfare solution which has been axiomatically characterized [Guerdjikova and Nehring, 2014] and noted for its strong participation incentives [Brandl et al., 2022] as well as its lowest-possible price of fairness [Michorzewski et al., 2020]. The Nash solution is also well-known to provide fair outcomes in other models, such as for private goods [Caragiannis et al., 2019].

**Capped setting.** What we call the capped setting has also been studied in various special cases under various names, such as cake sharing [Bei et al., 2024], fractional committee elections [Pierczyński and Skowron, 2022, Suzuki and Vollen, 2024], or divisible participatory budgeting [Aziz and Shah, 2021, Fain et al., 2016]. These works have mostly not considered Lindahl equilibrium, since there was no known way of computing one.

**Discrete models.** In discrete models, the public goods can either be fully funded or not at all. This model captures the way many cities run their participatory budgets, and has thus been well-studied including via core-like fairness notions such as EJR [Peters et al., 2021a, Rey and Maly, 2023], that were developed in the large literature on approval-based committee elections [Aziz et al., 2017, Lackner and Skowron, 2023, Peters, 2025]. There also exist proposals for definitions of Lindahl equilibrium for discrete models [Munagala et al., 2022a, Peters et al., 2021b].

**Computation.** In the uncapped setting, the maximum Nash welfare solution (and thus Lindahl equilibrium) can be efficiently computed via an Eisenberg-Gale-style convex program. This program has a simple structure (maximizing a natural objective function over the standard simplex), and Zhao [2023] has cataloged its appearance in many unrelated areas, including portfolio selection for maximizing log investment returns [Cover, 1984], information theory [Csiszár, 1974] and statistics [Vardi and Lee, 1993], and in medical imaging for positron emission tomography [Vardi et al., 1985]. Cover [1984] proposed a dynamics converging to the optimal solution of this program. Convergence proofs were also given by Csiszár [1984] and Brandl et al. [2022]. Later, Zhao [2023] obtained a convergence rate of $log(nm)/t$ for this dynamics. This is the same rate that we establish, though his approach does not connect the dynamics to mirror descent. In the capped setting, very little was known about computation, except for a heuristic algorithm proposed by Fain et al. [2016] that worked well in their experiments.
*Donor coordination.* An important application of the public goods allocation problem we study is *donor coordination*, where a collection of donors wish to coordinate their charitable spending, for example by pooling their donations and voting over the division of the pool between different causes. Brandl et al. [2022] have argued (using an uncapped model with linear utilities) that the Nash rule and thus Lindahl equilibrium is a good solution concept for this use case [see also Greaves and Cotton-Barratt, 2024]. However, a key reason for coordinating donations is the potential presence of caps: some charities may have a limited “room for more funding”. This issue is frequently discussed within Effective Altruism, citing cases similar to Example 5 [Peters, 2019]. As our work shows, the Nash solution does not extend well to settings with limited room for more funding, but Lindahl equilibrium as computed by our new convex program does. Brandt et al. [2024] also discuss Lindahl equilibrium applied to donor coordination, using Leontief utility functions.

*Other applications of the core.* The core has been employed as a fairness property in many other models. For example, Chaudhury et al. [2022] apply it to federated learning.<fnref n="2" /> It has also been used for clustering [Caragiannis et al., 2024, Chen et al., 2019, Kellerhals and Peters, 2024], peer reviewer assignments [Aziz et al., 2023b], and sortition [Ebadian and Micha, 2025].

## 2 Setup

Let $M$ be a set of $m$ public goods, which we sometimes refer to as *projects*. We have an overall *budget* $B > 0$ that we can spend on the public goods. Let $N = \{1, \dots, n\}$ be a set of $n$ agents. Each agent $i \in N$ has an individual budget $B_i > 0$ representing $i$'s weight or endowment. These sum to the overall budget, $\sum_{i \in N} B_i = B$. In many applications, the entitlements are equal: $B_i = B/n$. Each agent $i$ has a valuation $v_{ij} \ge 0$ for each public good $j \in M$. We write $v_i = (v_{ij})_{j \in M}$ for the vector of $i$'s valuations. The *utility* of an agent $i \in N$ for an outcome $x \in \mathbb{R}_{\ge 0}^m$ is $u_i(x) = \langle v_i, x \rangle = \sum_{j \in M} v_{ij}x_j$. Thus, we use separable linear utilities. We write $M_i = \{j \in M : v_{ij} > 0\}$ for the projects that agent $i \in N$ likes, and we write $N_j = \{i \in N : v_{ij} > 0\}$ for the agents that support project $j \in M$. We will assume throughout that $M_i \ne \emptyset$ for all $i \in N$ and that $N_j \ne \emptyset$ for all $j \in M$, since otherwise we may as well remove such agents or public goods from consideration.

In the *uncapped public goods* setting, an *allocation* is a vector $x = (x_j)_{j \in M}$ with $x_j \ge 0$ for all $j \in M$ and $\sum_{j \in M} x_j \le B$. Here, $x_j$ denotes the total spending on project $j$. In this definition, the public goods have no upper bound on how much of them we can spend on them, so in principle the entire budget $B$ could be spent on a single good.

In the *capped public goods* setting, we add the additional constraint that each good $j \in M$ has a maximum amount cap$_j > 0$ that can be spent on it. Thus, in this setting, an *allocation* is a vector $x = (x_j)_{j \in M}$ with $0 \le x_j \le \text{cap}_j$ for all $j \in M$ and $\sum_{j \in M} x_j \le B$. We assume that $\sum_{j \in M} \text{cap}_j \ge B$ (if not then we simply fully fund all the goods). The uncapped setting is the special case where cap$_j = \infty$ (or $B$) for each $j \in M$.

### 2.1 Lindahl Equilibrium

Our goal is to find a *Lindahl equilibrium* which is known to yield a fair and efficient allocation of public goods, in the sense that it yields an allocation that is Pareto efficient and lies in the (weak) core [Fain et al., 2016, Foley, 1970]. Let $p = (p_{ij})_{i \in N, j \in M}$ be a collection of non-negative *personalized prices*, with $p_{ij} \ge 0$ denoting the price that agent $i$ needs to pay per unit of project $j$, and $p_i = (p_{ij})_{j \in M}$ denoting the vector of prices facing $i$.

<footnote n="2">²Chaudhury et al. [2022, Theorem 2] show that the Nash rule satisfies core stability for arbitrary concave utilities. On first sight, this is in contradiction to our claim that Nash fails the core in the capped setting (Example 4). The difference is that Chaudhury et al. [2022] use a much weaker notion of the core which involves scaling utilities by the coalition size, rather than scaling the endowment. Fain et al. [2018, Section 1.6] discuss the distinction between these concepts.</footnote>
**DEFINITION 1 (LINDAHL EQUILIBRIUM).** Let $x$ be an allocation and let $p$ be a collection of non-negative personalized prices. Then $(x, p)$ is a Lindahl equilibrium if

* $x$ is affordable: we have $\langle p_i, x \rangle \le B_i$ for every $i \in N$,

* $x$ is utility-maximizing: for every $i \in N$ and every $y \in \mathbb{R}_{\ge 0}^m$ such that $0 \le y_j \le \text{cap}_j$ for all $j \in M$ and such that $\langle p_i, y \rangle \le B_i$, we have $u_i(x) \ge u_i(y)$,

* $x$ is profit-maximizing: for every $j \in M$, we have $\sum_{i \in N} p_{ij} \le 1$, and whenever $x_j > 0$ then $\sum_{i \in N} p_{ij} = 1$.

We say that an allocation $x$ is a Lindahl equilibrium allocation if there exist prices $p$ such that $(x, p)$ is a Lindahl equilibrium.

The distinctive property of a Lindahl equilibrium is that prices are personalized, but every agent demands the exact same bundle $x$ of public goods. That is the content of the utility maximization condition: it says that every agent $i$ can afford $x$ given the prices $(p_{ij})_{j \in M}$ and $i$'s budget $B_i$, and prefers $x$ among all affordable allocations satisfying the cap constraint.

The interpretation of the profit maximization condition is less clear. Its most important effect is that it imposes some amount of efficiency: an equilibrium can only spend a positive amount of budget on projects that have the maximum total price (and generally prices are higher if agent valuations for the project are higher). The condition can be seen as “profit maximization” if we imagine that there is a central producer of the public goods who takes in money from the agents and produces the public goods (at a cost of 1 unit of money for 1 unit of public good). This interpretation is made formal in the following simple observation.

**LEMMA 1 (EQUIVALENT DEFINITIONS OF PROFIT MAXIMIZATION).** Let $x$ be an allocation and let $p$ be a collection of non-negative personalized prices. Then the following are equivalent:

(a) for every $j \in M$, we have $\sum_{i \in N} p_{ij} \le 1$, and whenever $x_j > 0$ then $\sum_{i \in N} p_{ij} = 1$,

(b) for every $y \in \mathbb{R}_{\ge 0}^m$, we have

$$ \sum_{j \in M} \sum_{i \in N} p_{ij}x_j - \sum_{j \in M} x_j \ge \sum_{j \in M} \sum_{i \in N} p_{ij}y_j - \sum_{j \in M} y_j. $$

*PROOF.* If the prices satisfy (a), then $\sum_{j \in M} \sum_{i \in N} p_{ij}x_j - \sum_{j \in M} x_j = \sum_{j \in M} x_j - \sum_{j \in M} x_j = 0$ and for every $y \in \mathbb{R}_{\ge 0}^m$, we have $\sum_{j \in M} \sum_{i \in N} p_{ij}y_j - \sum_{j \in M} y_j = \sum_{j \in M} y_j - \sum_{j \in M} y_j = 0$, establishing (b).

If the prices satisfy (b), but there is some $j \in M$ with $\sum_{i \in N} p_{ij} > 1$, then the profit attained by $y \in \mathbb{R}_{\ge 0}^m$ is unbounded as $y_j \to \infty$, a contradiction. If the prices satisfy (b), but there is some $j \in M$ with $x_j > 0$ but $\sum_{i \in N} p_{ij} < 1$, then taking $y$ to be identical to $x$ but with $y_j = 0$ gives larger profit, a contradiction. These two contradictions establish (a). $\square$

Note that in condition (b), the producer compares $x$ to every other possible vector $y \in \mathbb{R}_{\ge 0}^m$, even if $y$ violates the cap-constraints or the overall budget constraint. Condition (b) is usually used as part of the definition of Lindahl equilibrium, but we have used condition (a) in our definition because it is simpler and more useful in proofs.

**EXAMPLE 1 (PERSONAL PROJECTS).** Consider the uncapped setting, and suppose that each agent likes exactly one project that nobody else likes, so we have $N = M$, with $v_{ii} = 1$ for each $i \in N$ and $v_{ij} = 0$ for all $i \ne j$. Let $(x, p)$ be a Lindahl equilibrium. Note first that $p_{ii} > 0$, since if $p_{ii} = 0$ then there would be no utility-maximizing bundle for $i$ who would demand unbounded spending on project $i$. Now, for each $i \in N$, the utility maximizing bundles are those that place the highest possible amount on project $i$, given the prices and subject to affordability, which is $B_i/p_{ii}$. Hence, in Lindahl equilibrium $x_i = B_i/p_{ii}$. In particular $x_i > 0$ for each $i$, and the entire endowment of $i$ is spent on project $i$ since $p_{ii}x_i = B_i$. Thus, in order for $x$ to be affordable for $i$, it must be the case that $p_{ij} = 0$ whenever $j \ne i$.
(because $x_j > 0$). By profit maximization, since $x_i > 0$, we get that $p_{ii} = 1$. Thus, $B_i/x_i = p_{ii} = 1$ and so $x_i = B_i$. This shows that there is a unique Lindahl equilibrium allocation $x$ with $x_i = B_i$ for each $i \in N$.

Every Lindahl equilibrium $(x, p)$ can be decomposed: For each $i \in N$ and $j \in M$, write

$$b_{ij} = p_{ij}x_j$$

for the contribution of $i$ towards $j$. This is a decomposition of $x$ (similar to a notion considered by Brandl et al. [2022, Definition 2]) because the values $(b_{ij})_{ij}$ satisfy the following conditions:

* For each $j \in M$, we have $x_j = \sum_{i \in N} b_{ij}$. (This is trivial if $x_j = 0$ and if $x_j > 0$ it follows because $\sum_{i \in N} p_{ij} = 1$.)

* For each $i \in N$, we have $\sum_{j \in M} b_{ij} \le B_i$. (This is simply a restatement of the affordability condition of the definition of Lindahl equilibrium.)

With this interpretation, we can see that $p_{ij}$ equals the fraction of spending on project $j$ that is contributed by agent $i$. This interpretation also appears in the definition of ratio equilibrium [Kaneko, 1977] which is equivalent to Foley's Lindahl equilibrium in the simple model we consider: We take the spending on a public good to be the same as the amount of the public good that is provided, which implies constant returns to scale, where several public goods equilibrium notions coincide [see also Mas-Colell and Silvestre, 1989, Moore, 2006, van den Nouweland, 2015].

Foley [1970] proved the existence of Lindahl equilibrium using a fixed-point theorem, in a model that is more general than ours. However, his result only applies to strictly monotonic preferences, and thus only establishes existence when $v_{ij} > 0$ for all $i \in N$ and $j \in M$. We will allow $v_{ij} = 0$. In the presence of zeros, it makes sense to consider Lindahl equilibria $(x, p)$ that are what we call zero-respecting.

**DEFINITION 2 (ZERO-RESPECTING).** A Lindahl equilibrium $(x, p)$ is zero-respecting if for all $i \in N$ and $j \in M$, whenever $v_{ij} = 0$ and $x_j > 0$ then $p_{ij} = 0$.

This is a natural condition in view of the decomposition we considered above, because in a zero-respecting Lindahl equilibrium, an agent contributes only to projects with positive utility: if $v_{ij} = 0$ then $b_{ij} = 0$. This condition is also imposed in the decomposability condition of Brandl et al. [2022, Definition 2].

The following example shows that not every Lindahl equilibrium is zero-respecting, and that zero-respecting Lindahl equilibria may violate Pareto efficiency. This will motivate imposing a certain sufficient condition introduced below that will avoid this result.

**EXAMPLE 2 (LINDAHL EQUILIBRIUM MAY UNDERSPEND).** Consider the following instance:

<table><thead><tr><th></th><th>B<sub>i</sub></th><th>Project 1</th><th>Project 2</th></tr></thead><tbody><tr><td>Agent 1</td><td>0.5</td><td>1</td><td>0</td></tr><tr><td>Agent 2</td><td>0.5</td><td>0</td><td>1</td></tr><tr><td>cap<sub>j</sub></td><td></td><td>0.25</td><td>&infin;</td></tr></tbody></table>

On this instance, the unique zero-respecting Lindahl equilibrium allocation is $x = (0.25, 0.5)$. To see this, note that each agent will demand the project that the agent likes, no matter the prices. Thus $x_1, x_2 > 0$. By profit maximization and the zero-respecting condition, we have $p_{11} = p_{22} = 1$ and $p_{12} = p_{21} = 0$. Then by the affordability and utility maximization conditions of Lindahl equilibrium, we get $x = (0.25, 0.5)$. Note that the total spending in this instance is 0.75, strictly less than the available budget of $B = 0.5 + 0.5$. In particular, $x$ is Pareto-dominated by the allocation $y = (0.25, 0.75)$.
If we remove the zero-respecting condition, there exist other Lindahl equilibria. In particular, $x' = (0.25, 0.75)$ forms an equilibrium with the prices $p_1 = (1, \frac{1}{3})$ and $p_2 = (0, \frac{2}{3})$.<fnref n="3" />

Note that the formal model of Foley [1970] does not directly support caps, but these can be simulated $\epsilon$-approximately through concave utility functions [Munagala et al., 2022b, Footnote 2]. We will be able to handle caps without any approximations.

## 2.2 Pareto-Optimality and the Core

Next we discuss how the Lindahl equilibrium relates to Pareto optimality and the set of allocations that are in the core. In the uncapped setting with strictly increasing valuations, the relationship between these concepts is straightforward, and was already studied by Foley [1970]. However, as we shall see, there is more nuance in the capped setting and in the presence of valuations equal to 0. We begin by introducing a sufficient condition that excludes examples like Example 2 where intuitively the caps of projects that receive non-zero valuations are too low. We will see that under this sufficient condition, every zero-respecting Lindahl equilibrium spends the entire budget, is Pareto efficient, and lies in the core.

For every $i \in N$, write $F_i = \{f \in N \mid M_i \cap M_f \neq \emptyset\}$ for the set of “friends” of $i$ who agree that at least one common project has a positive valuation.

**DEFINITION 3.** An instance is cap-sufficient if we have $\sum_{j \in M_i} \text{cap}_j \geq \sum_{f \in F_i} B_f$ for all $i \in N$.

There are many interesting settings in which instances are always cap-sufficient, including:

* The uncapped setting where cap_j = +∞ for all j ∈ M.

* All valuations are positive: $v_{ij} > 0$ for all $i \in N$ and $j \in M$. (Proof: In this case, $M_j = M$ and $F_i = N$, so the cap-sufficiency condition is implied by our general assumption that $\sum_{j \in M} \text{cap}_j \geq B$.)

* Each agent has positive utility for goods whose total cap reaches the budget: $\sum_{j \in M_i} \text{cap}_j \geq B$.

We will show that Lindahl equilibrium has particularly desirable properties on cap-sufficient instances. A key consequence of cap-sufficiency is that every voter spends their entire budget.

**PROPOSITION 1.** On a cap-sufficient instance, if $(x, p)$ is a zero-respecting Lindahl equilibrium, then

(i) for every $i \in N$, we have $\langle p_i, x \rangle = B_i$,

(ii) we have $\sum_{j \in M} x_j = B$,

(iii) for every $i \in N$ and every $y \in \mathbb{R}_{\ge 0}^m$ such that $0 \le y_j \le \text{cap}_j$ for all $j \in M$ and such that $\langle v_i, y \rangle \ge \langle v_i, x \rangle$, we have $\langle p_i, y \rangle \ge B_i$.

**PROOF.** (i) Suppose for a contradiction that $\langle p_i, x \rangle < B_i$. We claim that then for all $j \in M_i$, we have $x_j = \text{cap}_j$: Otherwise, if $x_j < \text{cap}_j$, we can increase $x_j$, thereby increasing the utility of $i$, and a sufficiently small increase is affordable since $i$ does not spend all of $B_i$ and satisfies the cap constraints. This contradicts utility maximization.

Now, because $(x, p)$ is zero-respecting, for each $j \in M_i$, only friends of $i$ will contribute to $j$ because $N_j \subseteq F_i$. Thus, $b_{i'j} = 0$ if $i' \in N \setminus F_i$. But then

$$ \sum_{j \in M_i} \text{cap}_j = \sum_{j \in M_i} x_j = \sum_{j \in M_i} \sum_{f \in F_i} b_{fj} \le \sum_{f \in F_i} \langle p_f, x \rangle < \sum_{f \in F_i} B_f, $$

since $\langle p_i, x \rangle < B_i$ by assumption. This contradicts that the instance is cap-sufficient.

<footnote n="3">³Suppose we replace zero-valuations by $\epsilon > 0$, i.e., we set $v_{12} = v_{21} = \epsilon$. Then for all $\epsilon > 0$, every Lindahl equilibrium allocation has $x_2 \ge 0.75$ by Corollary 1 (Pareto optimality). But for $\epsilon = 0$, in a zero-respecting Lindahl equilibrium, $x_2 = 0.5$. Thus, Lindahl equilibrium does not necessarily converge to a zero-respecting Lindahl equilibrium as $\epsilon \to 0$.</footnote>
(ii) Using (i), we deduce that

$$ \sum_{j \in M} x_j = \langle 1, x \rangle = \sum_{j \in M} \sum_{i \in N} p_{ij} x_j = \sum_{i \in N} \sum_{j \in M} p_{ij} x_j = \sum_{i \in N} B_i = B. $$

The second equality follows by distinguishing the cases $x_j > 0$ (use profit maximization) and $x_j = 0$ (does not contribute to the sum).

(iii) For a contradiction, suppose there is $i \in N$ and a cap-respecting allocation $y$ such that $\langle v_i, y \rangle \ge \langle v_i, x \rangle$ but with $\langle p_i, y \rangle < B_i$. Due to (i), we have $\langle p_i, y \rangle < \langle p_i, x \rangle$. Thus, there exists some $j \in M$ such that $p_{ij} > 0$ and $y_j < x_j$. Since $(x, p)$ is zero-respecting, we have $v_{ij} > 0$. Now consider an allocation obtained from $y$ but with the $j$-coordinate increased by a small amount. For a small enough increase, the resulting allocation respects the cap-constraints (because $y_j < x_j \le cap_j$) and is affordable for $i$ (because $\langle p_i, y \rangle < B_i$), but gives $i$ strictly higher utility, contradicting the utility-maximization condition of Lindahl equilibrium. (Note that the constructed allocation may not respect the overall budget constraint, but that is not required by the definition of Lindahl equilibrium.) □

A major reason to be interested in Lindahl equilibrium is that it always lies in the weak core, which is a fairness or stability property formalizing proportional representation.

**DEFINITION 4 (CORE).** An allocation $x$ is in the core if there is no "blocking coalition" $S \subseteq N$ and no objection $z = (z_j)_{j \in M} \in \mathbb{R}^{m \ge 0}$ with $0 \le z_j \le cap_j$ for all $j \in M$, such that $\sum_{j \in M} z_j \le \sum_{i \in S} B_i$ (it can be afforded by the blocking coalition) and for all $i \in S$, we have $\langle v_i, z \rangle \ge \langle v_i, x \rangle$ (every coalition member weakly prefers the objection) and the inequality is strict for at least one $i \in S$. It is in the weak core if there are no such $S$ and $z$ such that $\langle v_i, z \rangle > \langle v_i, x \rangle$ for all $i \in S$.

Foley [1970, Section 6] proved that Lindahl equilibrium allocations are in the weak core, though his model implicitly assumed cap-sufficiency. We can more generally show the following.

**PROPOSITION 2.** Let $(x, p)$ be a Lindahl equilibrium. Then $x$ lies in the weak core. If the instance is cap-sufficient and $(x, p)$ is zero-respecting, then $x$ lies in the core.

**PROOF.** Suppose not, and suppose $S \subseteq N$ is a blocking coalition with objection $z$ satisfying $\sum_{j \in M} z_j \le \sum_{i \in S} B_i$ and the cap constraints. We now claim that $\sum_{i \in S} \langle p_i, z \rangle > \sum_{i \in S} B_i$.

* Under the assumption that $x$ fails the weak core, note that since for every $i \in S$ we have $\langle v_i, z \rangle > \langle v_i, x \rangle$, the utility maximization condition of Lindahl equilibrium implies that $\langle p_i, z \rangle > B_i$. Summing over $i \in S$ establishes the claim.

* Under the assumption that $x$ fails the core, that $(x, p)$ is zero-respecting, and that the instance is cap-sufficient, Proposition 1(iii) implies that since $\langle v_i, z \rangle \ge \langle v_i, x \rangle$ for all $i \in S$, we have $\langle p_i, z \rangle \ge B_i$. Since we have $\langle v_i, z \rangle > \langle v_i, x \rangle$ for at least one $i \in S$, we have $\langle p_i, z \rangle > B_i$ for that $i$ due to utility maximization. Again, summing over $i \in S$ establishes the claim.

Combining the claim with the non-negativity of prices and profit maximization, we have

$$ \sum_{i \in S} B_i < \sum_{i \in S} \langle p_i, z \rangle \le \sum_{i \in N} \langle p_i, z \rangle \le \langle 1, z \rangle \le \sum_{i \in S} B_i, $$

a contradiction. □

As a special case, taking $S = N$ in Proposition 2, we see that Lindahl equilibrium allocations are (weakly) Pareto efficient, establishing a version of the First Welfare Theorem.

**DEFINITION 5 (PARETO-OPTIMALITY).** An allocation $x$ is Pareto-optimal if there is no allocation $x'$ such that $u_i(x') \ge u_i(x)$ for all $i \in N$ and $u_i(x') > u_i(x)$ for some $i \in N$. It is weakly Pareto-optimal if there is no $x'$ with $u_i(x') > u_i(x)$ for all $i \in N$.
**COROLLARY 1.** Let $(x, p)$ be a Lindahl equilibrium. Then $x$ is weakly Pareto optimal. If the instance is cap-sufficient and $(x, p)$ is zero-respecting, then $x$ is Pareto optimal.

As another special case of the core result, it is worth noting that Lindahl equilibria also gives guarantees for individual agents (by considering $S = \{i\}$), leading to an axiom generalizing the individual fair share property of Aziz et al. [2020].

**COROLLARY 2.** Let $x$ be a Lindahl equilibrium allocation, and let $i \in N$. Then for every allocation $z$ with $\sum_{j \in M} z_j \le B_i$ and $z_j \le \text{cap}_j$ for all $j \in M$, we have $u_i(x) \ge u_i(z)$.

In the uncapped setting, this implies that in any Lindahl equilibrium allocation, we have $u_i(x) \ge B_i \cdot \max_j v_{ij}$ for all $i \in N$.

# 3 Convex Optimization Background

This section gives background on convex optimization and the mirror descent algorithm.

*Basic definitions.* Let $f : \mathbb{R}^n \to (-\infty, \infty]$ be a function. It is called proper if there exists $x \in \mathbb{R}^n$ with $f(x) < \infty$. Its subdifferential at $x \in \mathbb{R}^n$ is $\partial f(x) = \{g \in \mathbb{R}^n : f(y) \ge f(x) + \langle g, y-x \rangle \text{ for all } y \in \mathbb{R}^n\}$. Elements of $\partial f(x)$ are called subgradients. The convex conjugate of $f$ is the function $f^* : \mathbb{R}^n \to [-\infty, \infty]$ defined by $f^*(y) = \sup_{x \in \mathbb{R}^n} (\langle y, x \rangle - f(x))$. We use the convention $0 \log 0 = 0$, and in this paper log always denotes the natural logarithm. We write $B \cdot \Delta^m = \{x \in \mathbb{R}^m : \sum_{j=0}^m x_j = B\}$ for the scaled simplex.

**KKT optimality conditions.** We will use the following version of the Karush-Kuhn-Tucker theorem, which also works for non-differentiable objective functions.

**THEOREM 1 (RUSZCZYNSKI, 2011, THM 3.34).** Let $x^*$ be an optimal solution to the program

minimize $f(x)$ subject to $h_i(x) \le 0$ for $i = 1, \dots, m$

where $f : \mathbb{R}^n \to (-\infty, \infty]$ and $h_i : \mathbb{R}^n \to \mathbb{R}$, $i = 1, \dots, m$, are proper convex functions. Assume that $f$ is continuous at some feasible point, and that Slater's constraint qualification is satisfied, so that there is a feasible point $x$ with $h_i(x) < 0$ for $i = 1, \dots, m$. Then there exist $\lambda_1, \dots, \lambda_m \ge 0$ such that

$$0 \in \partial f(x^*) + \sum_{i=1}^{m} \lambda_i \partial h_i(x^*) \quad \text{and} \quad \lambda_i h_i(x^*) = 0 \text{ for } i = 1, \dots, m.$$

Conversely, if $x^*$ satisfies the constraints $h_i(x^*) \le 0$ for $i = 1, \dots, m$ and there exist $\lambda_1, \dots, \lambda_m \ge 0$ satisfying the above conditions, then $x^*$ is a global minimum.

The KKT theorem can be used to characterize the optimal solutions of convex programs. Two such optimization problems will appear repeatedly in our derivations, and so we state them here.

**LEMMA 2.** (a) Let $y \in \mathbb{R}^n$. Suppose $x^*$ minimizes $\sum_{i=1}^n x_i \log x_i - \langle y, x \rangle$ subject to $x \in B \cdot \Delta^n$. Then $x_i^* = B \cdot e^{y_i} / (\sum_{j=1}^n e^{y_j})$ for $i = 1, \dots, n$.

(b) Let $y \in \mathbb{R}_{\ge 0}^n \setminus \{0\}$. Suppose $x^*$ maximizes $\sum_{i=1}^n y_i \log x_i$ subject to $x \in \Delta^n$. Then $x_i^* = y_i / (\sum_{j=1}^n y_j)$ for $i = 1, \dots, n$.

**PROOF.** For (a), see the book by Beck [2017, Example 3.71]. For (b), let us assume that $y_i > 0$ for all $i$, since for $i$ with $y_i = 0$, it is optimal to set $x_i = 0$, and we can ignore these indexes when optimizing the others. Under this assumption, note that any optimal solution must have $x_i > 0$ for all $i$. Applying the KKT theorem, this means that the multipliers of the non-negativity constraints are 0. Thus, the stationarity condition implies that $0 = -y_i/x_i + \lambda$, where $\lambda \in \mathbb{R}$ is the multiplier for the constraint $\sum_i x_i = 1$. Thus, $x_i = \lambda y_i$. Summing over all $i$, we see that $\lambda = 1/(\sum_i y_i)$, which gives the result. $\square$
*Convex programming duality.* We will use the following recipe for deriving the dual of convex programs with linear constraints. The recipe was explicitly given in Cole et al. [2017], though it is also a direct consequence of Fenchel duality [Rockafellar, 1970, Theorem 31.1], as we show for completeness.

**THEOREM 2 (FENCHEL DUALITY FOR LINEARLY CONSTRAINED CONVEX PROGRAMS).** Let $f$ be a proper convex function. The following programs are dual:

* $\min_x f(x) - \langle c, x \rangle$ subject to $Ax \ge b$,

* $\max_{y,z} \langle b, z \rangle - f^*(y)$ subject to $A^T z = y - c$ and $z \ge 0$.

In particular, the two programs have the same objective value, provided that there is a point $x$ with $f(x) < \infty$ and $Ax > b$.

**PROOF:** Consider the concave function

$$h(x) = \begin{cases} \langle c, x \rangle & \text{if } Ax \ge b, \\ -\infty & \text{otherwise.} \end{cases}$$

Its concave conjugate is $h_*(y) = \inf_x \langle y, x \rangle - h(x) = \inf_{x:Ax \ge b} \langle y, x \rangle - \langle c, x \rangle = \inf_{x:Ax \ge b} \langle y - c, x \rangle$. Now, applying Fenchel duality and LP duality, we have

$$ \begin{align*} \min_{x:Ax \ge b} f(x) - \langle c, x \rangle &= \inf_x f(x) - h(x) \\ &= \sup_y h_*(y) - f^*(y) \tag{Fenchel's duality theorem} \\ &= \sup_y \left( \inf_{x:Ax \ge b} \langle y - c, x \rangle - f^*(y) \right) \\ &= \sup_{y:z \ge 0, A^T z = y-c} \left( \sup_{z \ge 0} \langle b, z \rangle - f^*(y) \right) \tag{LP duality} \\ &= \sup_{y,z:z \ge 0, A^T z = y-c} \langle b, z \rangle - f^*(y), \end{align*} $$

showing that the two programs are dual. Fenchel's duality theorem applies provided that $f$ and $h$ have domains whose relative interior intersects [Rockafellar, 1970, Theorem 31.1], which follows from the existence of some $x$ with $f(x) < \infty$ and $Ax > b$. □

*Mirror descent.* The mirror descent (MD) algorithm is a first-order method for convex minimization which generalizes projected gradient descent to allow for more general notions of distance. Given a convex set $X$ and a convex function $f$, the goal is to minimize $f$ over $X$ via first-order updates. MD relies on a Bregman divergence $D_h(x||y)$, which is a convex function that measures the difference between $x$ and $y$. The function $D_h$ is constructed from some 1-strongly convex reference function $h$ as $D_h(x||y) = h(x) - h(y) - \langle \nabla h(y), x - y \rangle$. For example, taking the negative entropy reference function $h(x) = \sum_i x_i \log x_i$, the Bregman divergence becomes the KL divergence, $D_h(x||y) = \sum_i x_i \log(x_i/y_i)$, for $x, y \in \Delta^n$. The update rule for MD is

$$x^{t+1} = \arg \min_{x \in X} \langle \nabla f(x^t), x \rangle + \frac{1}{\eta} D_h(x \| x^t), \quad (1)$$

where $\eta > 0$ is a stepsize parameter. There are a variety of convergence results for MD. We will specifically be interested in the case where a special relationship holds between the objective $f$ and the reference function $h$, known as *relative smoothness*. The function $f$ is said to be 1-smooth relative to the reference function $h$ when it holds for all $x, y \in \text{relint } X$ that

$$f(x) \le f(y) + \langle \nabla f(y), x - y \rangle + D_h(x||y).$$
The following theorem from Birnbaum et al. [2011] shows that when the reference function $h$ is chosen such that relative smoothness holds, the sequence of iterates generated by mirror descent converges at a rate of $O(1/t)$:

**THEOREM 3 (BIRNBAUM ET AL., 2011, THEOREM 3).** Suppose that $f$ is 1-smooth relative to the reference function $h$, and we run mirror descent using $h$ as the distance-generating function with $\eta = 1$. Let $x^*$ be an optimal solution. Then the sequence of iterates generated by mirror descent satisfies:

$$f(x^t) - f(x^*) \le \frac{D_h(x^*||x^0)}{t}$$

# 4 Uncapped Public Goods

We begin by analyzing the uncapped setting, and begin by characterizing the Lindahl equilibrium prices, which will be helpful for understanding the convex programs we discuss. Let $(x, p)$ be a Lindahl equilibrium. Then $\langle v_i, x \rangle > 0$ for each $i \in N$ by utility maximization (since there exists some affordable bundle that gives $i$ positive utility, as prices are finite). In the uncapped setting, one can show that every Lindahl equilibrium is zero-respecting: if $v_{ij} = 0$ and $x_j > 0$, the utility maximizing bundle for agent $i$ contains a positive amount on project $j$, which is only possible if $p_{ij} = 0$ (if the price was positive, the agent could increase utility by redirecting the spending to a good with positive valuation). Now, each agent will only demand public goods that maximize the “bang-per-buck” ratio $v_{ij}/p_{ij}$ among projects with positive valuation. Thus, the quantity $v_{ij}/p_{ij}$ must be equal for all projects $j$ with $x_j > 0$ and $v_{ij} > 0$. Therefore, $p_{ij} \propto v_{ij}$, say with factor of proportionality $\alpha_i$. Because each agent spends their entire budget (Proposition 1 (i), which applies since in the uncapped setting Lindahl equilibrium is always zero-respecting), we have $B_i = \sum_{j \in M_i} p_{ij}x_j = \sum_{j \in M_i} \alpha_i v_{ij}x_j = \alpha_i \langle v_i, x \rangle$ and thus $\alpha_i = B_i/\langle v_i, x \rangle$. Hence, in the uncapped setting,

$$p_{ij} = B_i \cdot \frac{v_{ij}}{\langle v_i, x \rangle} \quad \text{for all } j \in M \text{ with } x_j > 0. \qquad (2)$$

(Note that when $v_{ij} = 0$ and $x_j > 0$, (2) just says $p_{ij} = 0$ which follows because $(x, p)$ is zero-respecting, so (2) also holds for $v_{ij} = 0$.)

Now consider a project $j \in M$ with $x_j = 0$. Because $i$ does not demand it, its bang-per-buck must be weakly below the bang-per-buck of funded projects. From (2), it then follows that

$$p_{ij} \ge B_i \cdot \frac{v_{ij}}{\langle v_i, x \rangle} \quad \text{for all } j \in M \text{ with } x_j = 0. \qquad (3)$$

As we explained in Section 2.1, any Lindahl equilibrium can be decomposed into individual contributions $b_{ij} = p_{ij}x_j$. From (2), it follows that in Lindahl equilibrium,

$$b_{ij} = B_i \cdot \frac{v_{ij}x_j}{\langle v_i, x \rangle} \quad \text{for all } j \in M, \qquad (4)$$

or more simply that $b_{ij} \propto v_{ij}x_j$, so contributions are proportional to the utility $i$ obtains in $x$ from $j$. One can view (4) as a kind of fixed-point property implied by Lindahl equilibrium [Guerdjikova and Nehring, 2014], and it suggests the proportional response dynamics that we will study later.

# 4.1 Nash Welfare and the Eisenberg-Gale Program

In the uncapped setting (i.e. $cap_j = +\infty$ for all $j \in M$), Lindahl equilibrium allocations can be nicely characterized as those maximizing the Nash social welfare $\prod_i u_i(x)$ [Fain et al., 2016]. Such an
allocation can be computed by solving the following convex program:

$$ 
\begin{array}{l}
\max_{x \ge 0} \sum_{i \in N} B_i \log \langle v_i, x \rangle \\
\text{s.t.} \quad \sum_{j \in M} x_j \le B
\end{array}
\qquad (5)
$$

This program is the public-goods analog of the Eisenberg-Gale convex program for computing a Fisher market equilibrium with private goods [Eisenberg, 1961, Eisenberg and Gale, 1959]. By analyzing the KKT conditions of Program 5, one can show that it exactly computes Lindahl equilibrium. We include a proof for completeness.

**THEOREM 4 (FAIN ET AL., 2016, COROLLARY 2.3).** In the uncapped setting, an allocation $x$ is a Lindahl equilibrium allocation if and only if it is an optimal solution to Program 5.

**PROOF.** Let $x$ be an optimal solution to Program 5. Note first that optimality implies $\sum_j x_j = B$ since otherwise we could increase the objective by increasing $x_j$ for some project liked by some agent (except in the trivial case where $v_{ij} = 0$ for all $i$ and $j$ for which there is nothing to prove). Further, every agent has strictly positive utility at $x$ since otherwise the objective value would be $-\infty$. Thus, the objective function is differentiable at $x$. By Theorem 1, there exists $\lambda \ge 0$ (corresponding to the budget constraint) and $(\mu_j)_{j \in M} \ge 0$ (corresponding to the non-negativity constraints) such that for every $j \in M$, we have $0 = -\sum_{i \in N} B_i \frac{v_{ij}}{\langle v_i, x \rangle} + \lambda - \mu_j$. Thus $\lambda \ge \sum_{i \in N} B_i \frac{v_{ij}}{\langle v_i, x \rangle}$, with equality if $x_j > 0$. Multiplying by $x_j$, summing over $j$, and rearranging, we get $\sum_{j \in M} \lambda x_j = \sum_{j \in M} \sum_{i \in N} B_i \frac{v_{ij}x_j}{\langle v_i, x \rangle}$. This simplifies to $\lambda B = \sum_{i \in N} B_i = B$, so $\lambda = 1$. Hence for each $j \in M$, we have

$$ \sum_{i \in N} B_i \frac{v_{ij}}{\langle v_i, x \rangle} \le 1, \text{ with equality if } x_j > 0. $$

Set $p_{ij} = B_i \frac{v_{ij}}{\langle v_i, x \rangle}$. Then $(x, p)$ is a Lindahl equilibrium: The above inequality immediately establishes the profit maximization condition. For utility maximization, note that the “bang-per-buck” of project $j$ to agent $i$ is $v_{ij}/p_{ij} = \langle v_i, x \rangle/B_i$, which is constant, so that all allocations that use up the agent’s entire budget are utility maximizing. Since $\langle p_i, x \rangle = B_i$, it follows that $x$ is utility maximizing for $i$.

Conversely, suppose $(x, p)$ is a Lindahl equilibrium. Set $\lambda = 1$ and $\mu_j = 1 - \sum_{i \in N} B_i \frac{v_{ij}}{\langle v_i, x \rangle}$ for each $j \in M$. For complementary slackness, note that if $x_j > 0$, then from (2) we have $\mu_j = 1 - \sum_{i \in N_j} p_{ij}$, and thus by the profit maximization condition of Lindahl equilibrium, we get $\mu_j = 0$. Complementary slackness also holds for $\lambda$ since $\sum_{j \in M} x_j = B$ by Proposition 1(ii). We also have $\mu_j \ge 0$, combining (2), (3) and the profit maximization condition of Lindahl equilibrium. Finally, it is easy to check stationarity; for every $j \in M$ we have

$$ -\sum_{i \in N} B_i \frac{v_{ij}}{\langle v_i, x \rangle} + \lambda - \mu_j = -\sum_{i \in N} B_i \frac{v_{ij}}{\langle v_i, x \rangle} + \sum_{i \in N} B_i \frac{v_{ij}}{\langle v_i, x \rangle} = 0. $$

Thus, by Theorem 1, $x$ is an optimal solution to Program 5. $\square$

Fain et al. [2016, Theorem 2.2] also present Eisenberg-Gale-style programs for computing Lindahl equilibria for certain non-linear utility functions called “scalar separable non-satiating” including CES and Cobb-Douglas utilities.
Interestingly, for Fisher market equilibrium, the Eisenberg-Gale program always admits a rational solution [Devanur et al., 2008, Vazirani, 2012]. However, this is not the case in our public goods setting,<fnref n="4" /> as the following example shows [see also Airiau et al., 2023, Theorem 5].

**EXAMPLE 3 (IRRATIONAL LINDAHL EQUILIBRIUM ALLOCATION).** Consider the uncapped setting with 4 agents with equal budgets $B_i = \frac{1}{4}$ and with three projects. The agents have the following valuations:

<table><thead><tr><th></th><th>$B_i$</th><th>Project 1</th><th>Project 2</th><th>Project 3</th></tr></thead><tbody><tr><td>Agent 1</td><td>0.25</td><td>1</td><td>0</td><td>0</td></tr><tr><td>Agent 2</td><td>0.25</td><td>1</td><td>0</td><td>1</td></tr><tr><td>Agent 3</td><td>0.25</td><td>1</td><td>1</td><td>0</td></tr><tr><td>Agent 4</td><td>0.25</td><td>0</td><td>1</td><td>1</td></tr><tr><td>cap<sub>j</sub></td><td></td><td>$\infty$</td><td>$\infty$</td><td>$\infty$</td></tr></tbody></table>

By Theorem 4, a Lindahl equilibrium allocation $x$ forms an optimal solution to Program 5. Since projects 2 and 3 are symmetric and the objective function of Program 5 is strictly convex, we have $x_2 = x_3$. Since $B = 1$, we deduce that $x_1 = 1 - 2x_2$. Thus, the objective function of Program 5 can be written as $\frac{1}{4}(\log(1 - 2x_2) + 2\log(1 - x_2) + \log(2x_2))$. Exponentiating, this is equivalent to maximizing $(1 - 2x_2)(1 - x_2)^2(2x_2)$. Setting its derivative to 0, we find that it has its unique maximum at $x_2 = \frac{1}{16}(7 - \sqrt{17}) \approx 0.1798$. Thus, $x$ is irrational and the unique Lindahl equilibrium allocation.

## 4.2 A New Convex Program

We will present a new convex program which also captures the Lindahl equilibrium concept in the uncapped setting. As we will see, this convex program will yield several useful results. First, we will use it to show that the proportional response dynamics for uncapped public goods can indeed be interpreted as mirror descent with the entropy distance, just as in the Fisher market setting. Secondly, extending this convex program will allow us to give the first computational results for the capped public goods setting. Our new convex program is in the spirit of the Shmyrev convex program for Fisher markets for private goods [Shmyrev, 1983, 2009], though there are important differences. The convex program is as follows:

$$ 
\begin{array}{ll}
\max_{b \ge 0, x \ge 0} & \displaystyle\sum_{i \in N, j \in M_i} b_{ij} \log v_{ij} - \sum_{i \in N, j \in M_i} b_{ij} \log (b_{ij} / x_j) \\
\text{s.t.} & \displaystyle\sum_{j \in M_i} b_{ij} = B_i, \quad \forall i \in N \\
& \displaystyle\sum_{i \in N_j} b_{ij} = x_j, \quad \forall j \in M
\end{array}
\qquad (6)
$$

The convexity of this program can be deduced, for example, from the log sum inequality.

The program has two sets of variables, though one is implied by the other. The $x_j$ variable has the same interpretation as in Program 5: it is the amount of budget allocated to project $j$. The $b_{ij}$ variables can be interpreted as the share of agent $i$'s budget $B_i$ that they allocate towards project $j$. Note that each $x_j$ variable is directly implied by the choice of the $b_{ij}$ variables across agents $i$. It is only there as a convenience variable, and we could replace each occurrence of it in Program 6 by $\sum_{i \in N_j} b_{ij}$. Indeed, in our proofs, we will mostly work directly with this formulation that optimizes only over the $b_{ij}$ variables.

<footnote n="4">⁴For Fisher markets, the proof sets up a system of linear inequalities whose variables correspond to the reciprocals of equilibrium prices, $1/p_j$. However, profit maximization in Lindahl equilibrium (which has no analog in Fisher markets) involves the sum $\sum_i p_{ij}$ which is not linear in the reciprocals of prices. Thus, the Fisher market argument does not generalize.</footnote>
To gain some intuition for Program 6, suppose that we already knew the optimum value of the $x_j$ variables, and thus can treat them as constants and use Program 6 to merely compute the values of the $b_{ij}$ variables. If we drop the bottom constraint, the program decomposes into a separate optimization for each $i \in N$. From Lemma 2(a), these optimum values satisfy $b_{ij}^* \propto v_{ij}x_j$, which exactly matches the condition (4) that we derived earlier from the definition of Lindahl equilibrium.

While our program has some similarity to the Shmyrev program for private goods [Birnbaum et al., 2011, Shmyrev, 2009], it has the following important differences. First, the Shmyrev program contains variables corresponding to prices, which do not appear in our program. Second, the original primal variables $x_j$ appear directly in our program, whereas in Shmyrev's program these are a non-linear function of the corresponding $b$ variables. Third, we have a somewhat unusual term that looks like a partially-normalized entropy in our objective, whereas Shmyrev's program only requires using a typical negative entropy term over prices.

## 4.3 Connecting the Nash Social Welfare Program to Our New Program via Duality

Program 5 and Program 6 can be related to each other through “double duality”. We need the following lemma, which derives the convex conjugate of a convex function that will appear in the dual of Program 5. The proof is in Section A.

**LEMMA 3.** Consider some $q \in \mathbb{R}^{n \times m}$ and let $q_j$ be the $j$-th column of $q$. For $j \in M$, let $g_j(q_j) = \sum_{i \in N} e^{q_{ij}}$ and let $g(q) = B \cdot \max_{j \in M} g_j(q_j)$. Then the convex conjugate of $g$ satisfies

$$g^*(\beta) = \sum_{ij} \beta_{ij} \log \frac{\beta_{ij}}{\bar{x}_j(\beta)} - \beta_{ij} \quad \text{for all } \beta \ge 0,$$

$$\text{where } \bar{x}_j(\beta) = B \cdot \frac{\sum_i \beta_{ij}}{\sum_{j'} \beta_{j'j}}.$$

Now we can state the result formalizing the relationship between the two programs: their dual programs are equivalent. This result is an analog of a result for private goods, where the Shmyrev and the Eisenberg-Gale program also share a dual after reformulation [Cole et al., 2017].

**THEOREM 5 (DOUBLE DUALITY).** Program 6 is the dual of the dual of Program 5, after reformulation.

**PROOF.** For convenience, we rewrite Program 5 by adding variables encoding agent utilities:

$$\begin{array}{l}
\min_{x \ge 0, u} - \sum_{i \in N} B_i \log u_i \\
\text{s.t. } u_i \le \langle v_i, x \rangle, \forall i \in N \\
\qquad \sum_{j \in M} x_j \le B
\end{array}
\qquad (7)$$

Using the Fenchel duality in Theorem 2, we can compute the dual of Program 7 by noting that the convex conjugate of $f(u_i) = -B_i \log u_i$ is $f^*(\mu_i) = B_i \log B_i - B_i - B_i \log(-\mu_i)$, and introducing dual variables $\beta_i$ for the constraints involving $u_i$, dual variable $\lambda$ for the budget constraint, and dual variables $\eta_j$ for the non-negativity constraints on the $x_j$.

$$\begin{array}{l}
\max_{\lambda \ge 0, \beta \ge 0, \eta \ge 0, \mu} -B\lambda - \sum_{i \in N} (B_i \log B_i - B_i - B_i \log(-\mu_i)) \\
\text{s.t.} - \sum_{i \in N} \beta_i v_{ij} + \lambda - \eta_j = 0, \forall j \in M \\
\qquad - \beta_i = \mu_i, \forall i \in N
\end{array}
\qquad (8)$$

We can clean up this program by eliminating the $\mu_i$ variables (replacing them by $-\beta_i$), eliminating the $\eta_j$ variables (thereby turning equality into inequality constraints), and dropping constant terms
from the objective. Thereby we obtain the following program as the “official” dual of Program 5.

$$ 
\begin{array}{ll}
\min_{\lambda \ge 0, \beta \ge 0} & B\lambda - \sum_{i \in N} B_i \log \beta_i \\
\text{s.t.} & \sum_{i \in N} \beta_i v_{ij} \le \lambda, \forall j \in M
\end{array}
\qquad (9)
$$

Now we rewrite Program 9 by introducing a redundant set of variables $\lambda_{ij}$, which will represent the “bid” $\beta_i v_{ij}$ that agent $i$ makes on project $j$. This gives the following program:

$$ 
\begin{array}{ll}
\min_{\lambda \ge 0, \beta \ge 0} & B\lambda - \sum_{i \in N} B_i \log \beta_i \\
\text{s.t.} & \sum_{i \in N} \lambda_{ij} \le \lambda, \forall j \in M \\
& \beta_i v_{ij} \le \lambda_{ij}, \forall i \in N, j \in M
\end{array}
\qquad (10)
$$

(One can show that in optimal solutions to this program, we have $\lambda = 1$, and $\lambda_{ij}$ corresponds to the Lindahl price of $j$ for $i$, and $\beta_i$ corresponds to the maximum bang-per-buck ratio facing agent $i$. The first constraint corresponds to profit maximization of Lindahl equilibrium.)

Having removing the summation from the bottom constraint in Program 9, we can now apply the logarithm to the bottom constraint of program (10) and get a separation into individual terms. We note that in optimum, the value of $\lambda$ is the maximum over $j \in M$ of the value of $\sum_{i \in N} \lambda_{ij}$, so we can replace $\lambda$ in the objective function by a maximum. In addition, we perform two changes of variable: we write $\gamma_i = -\log \beta_i$ and $q_{ij} = \log \lambda_{ij}$. Thereby we arrive at the following program:

$$ 
\begin{array}{ll}
\min_{q, \gamma} & B \cdot (\max_{j \in M} \sum_{i \in N} e^{q_{ij}}) + \sum_{i \in N} B_i \gamma_i \\
\text{s.t.} & \log v_{ij} \le q_{ij} + \gamma_i, \forall i \in N, j \in M
\end{array}
\qquad (11)
$$

Next we derive the dual of (11), again using the Fenchel dual from Theorem 2. For $j \in M$, let $g_j(q) = \sum_{i \in N} e^{q_{ij}}$ and let $g(q) = B \cdot \max_{j \in M} g_j(q)$. Write $b_{ij}$ for the dual variables for the constraints in Program 11. Then the dual of (11) is

$$ 
\begin{array}{ll}
\max_{b \ge 0} & \sum_{ij} b_{ij} \log v_{ij} - g^*(b) \\
\text{s.t.} & \sum_{j \in M} b_{ij} = B_i, \forall i \in N
\end{array}
\qquad (12)
$$

By Lemma 3, the term $g^*(b)$ equals $\sum_{ij} b_{ij} \log \frac{b_{ij}}{\tilde{x}_j(b)} - b_{ij}$, where $\tilde{x}_j(b) = B \cdot \sum_i b_{ij} / \sum_{ij'} b_{ij'}$. In Program 12, the denominator $\sum_{ij'} b_{ij'}$ is constrained to equal $B$, so we can simplify the expression to $\tilde{x}_j(b) = \sum_i b_{ij} = x_j(b)$. This yields the desired Program 6. $\square$

Since the EG program and Program 6 are connected via the same dual, we know that the solution to Program 6 must imply a solution to the primal EG (through computing the implied dual solutions via KKT conditions, which can easily be done) and thus a Lindahl equilibrium. One can also show directly that Program 6 yields Lindahl equilibria. We defer this proof to the section on the capped setting, where we show it for that more general case (Theorem 8).

## 4.4 A Possible Path to Tâtonnement for Public Goods

Finally, we briefly remark that the dual program (10) can be rewritten in a way that eliminates the variables $\lambda$ and $\beta_i$ and thereby turns it into an unconstrained minimization problem. This yields
the following program:

$$ \min_{\{\lambda_{ij}\}_{ij}} B \cdot (\max_{j \in M} \sum_{i \in N} \lambda_{ij}) - \sum_{i \in N} B_i \min_{j \in M} \log \frac{\lambda_{ij}}{v_{ij}} \quad (13) $$

One interesting property of this program is that it has a tâtonnement-like interpretation. The $\lambda_{ij}$ variables can be viewed as personalized prices offered to each agent $i$ for project $j$. In this interpretation, each agent chooses their favorite projects among those minimizing $\lambda_{ij}/v_{ij}$, i.e. ones that maximize their bang-per-buck, and spends their entire budget $B_i$ on such projects. Formally, let $y_i \in \Delta^m$ be such that $y_{ij} > 1$ only when project $j$ minimizes $\lambda_{ij}/v_{ij}$. Then $B_i \cdot y_{ij}$ specifies how much of their budget agent $i$ allocates to an optimal bang-per-buck project $j$. Similarly, let $x \in B \cdot \Delta^m$ be such that $x_j > 0$ only if $\sum_{i \in N} \lambda_{ij} = \max_{j \in M} \sum_{i \in N} \lambda_{ij}$. Then $x$ specifies a budget allocation proposed by the price-setter. Then we have that a subgradient is any $g \in \mathbb{R}^{n \times m}$ such that

$$ g_{ij} = x_j - y_{ij} \frac{B_i}{\lambda_{ij}}, $$

for any pair $(x, y)$ satisfying the above conditions. This subgradient can be interpreted as a measure of discrepancy. The price-setter is proposing a set of per-agent prices $\lambda$ and a corresponding budget allocation $x$. In turn, agent $i$ computes their preferred allocation under $\lambda_i$, where $y_{ij} \frac{B_i}{\lambda_{ij}}$ is the amount they would have to spend to obtain $B_i \cdot y_{ij}$ units of project $j$ at price $\lambda_{ij}$. The subgradient $g_{ij}$ is then the discrepancy between the price-setter's proposal and the agent's preferred allocation. It is positive (and thus suggests an increase in price) if the agent spends less than the proposed allocation on the project; it is negative (and thus suggests a decrease in price) if the agent spends more. The subgradient is zero exactly when the price-setter's proposed allocation is optimal for each agent, meaning the proposed prices support the allocation. Deriving some form of convergence results for this program would be an interesting direction for future work.

## 4.5 Proportional Response Dynamics as Mirror Descent

It is known that the Lindahl equilibrium for the uncapped public goods setting can be computed by a simple dynamics [Brandl et al., 2022] which we call the proportional response dynamics in analogy to a similar dynamics for private-good Fisher markets [Wu and Zhang, 2007, Zhang, 2011]. At each iteration $t$, the proportional response dynamics have some current budget allocation $x^t = (x_1^t, \dots, x_m^t)$ summing to $B$ and with $x_j^t > 0$ for all $j \in M$. Let $u_i^t = \langle v_i, x^t \rangle$ be the current utility of agent $i$ under this allocation. Note that $u_i^t > 0$ because $x_j^t > 0$ for all $j$ and we assume that $M_i \neq \emptyset$. Then the next budget allocation in the dynamics is

$$ x_j^{t+1} = \sum_{i \in N} B_i \frac{x_j^t v_{ij}}{u_i^t}. $$

This dynamics can be interpreted as each agent $i$ independently deciding how they wish to allocate their share of the budget $B_i$ in the next round. Specifically, agent $i$ allocates spending proportional to how much utility each project provided them at round $t$. This spending allocation matches the property in (4) we derived earlier from the definition of Lindahl equilibrium. We will show that the proportional response dynamics is the mirror descent algorithm applied to our new convex program.

In order to derive this relationship, we first reformulate Program 6 to an equivalent version: we eliminate the redundant $x_j$ variables, convert the problem into a minimization problem, and define
the shorthand function $x_j(b) = \sum_{i \in N_j} b_{ij}$. Then we get the following convex program:

$$ \begin{array}{ll} \min_{b \ge 0} & f(b) := - \sum_{i \in N, j \in M_i} b_{ij} \left( \log v_{ij} - \log \left( \frac{b_{ij}}{x_j(b)} \right) \right) \\ \text{s.t.} & \sum_{j \in M_i} b_{ij} = B_i, \quad \forall i \in N \end{array} \tag{14} $$

**THEOREM 6 (EQUIVALENCE OF MIRROR DESCENT AND PR DYNAMICS).** Assume that the mirror descent algorithm on Program 14 is initialized at a point $b^0 = (b_{ij}^0)_{i \in N, j \in M_i}$ such that $\sum_{j \in M_i} b_{ij}^0 = B_i$ and $b_{ij}^0 > 0$ for all $i \in N$ and $j \in M_i$, and that the proportional response dynamics is initialized at the corresponding allocation $x^0 = (x_j(b^0))_{j \in M}$. Then the proportional response dynamics is equivalent to applying the mirror descent algorithm with the negative entropy reference function and stepsize $\eta = 1$ to Program 14.

**PROOF.** Note first that $f$ is differentiable at any $b$ such that $b_{ij} > 0$ for all $i \in N$ and $j \in M_i$. This holds by assumption for $b^0$, and we will see that if it holds for the initial point then it holds throughout. We can rewrite the objective function $f$ as follows:

$$ f(b) = - \sum_{i \in N, j \in M_i} b_{ij} \log v_{ij} + \sum_{i \in N, j \in M_i} b_{ij} \log b_{ij} - \sum_{j \in M} x_j(b) \log x_j(b). $$

The derivative of the objective in Program 14 with respect to $b_{ij}$ is

$$ \nabla_{ij} f(b) = -\log v_{ij} + (\log b_{ij} + 1) - (\log x_j(b) + 1) = -\log v_{ij} + \log(b_{ij}/x_j(b)). \tag{15} $$

Let $x_j^t = \sum_{i \in N_j} b_{ij}^t$. We now apply the mirror descent update rule (given by Eq. (1)) using the negative entropy reference function $h$ and stepsize $\eta = 1$. The induced Bregman divergence $D_h(b_i || b_i^t)$ is the KL divergence (since $b_i$ and $b_i^t$ both sum to $B_i$). Thus, we get the following update for each $i \in N$, where the arg min is taken over all $b_i = (b_{ij})_{j \in M_i}$ such that $\sum_{j \in M_i} b_{ij} = B_i$:

$$ \begin{aligned} b_i^{t+1} &= \arg \min_{b_i} \sum_{j \in M_i} b_{ij} \left( -\log v_{ij} + \log(b_{ij}^t/x_j^t) \right) + \sum_{j \in M_i} b_{ij} \log(b_{ij}^t/b_{ij}^t) \\ &= \arg \min_{b_i} \sum_{j \in M_i} b_{ij} \left( -\log v_{ij} + \log(b_{ij}^t/x_j^t) \right) \end{aligned} $$

By Lemma 2(a), for each $i \in N$, the solution to this optimization problem satisfies

$$ b_{ij}^{t+1} \propto \exp \left( \log(v_{ij}x_j^t) \right) \propto v_{ij}x_j^t. $$

In order to get a feasible solution we must normalize the above such that $\sum_{j \in M_i} b_{ij}^{t+1} = B_i$. Let $u_i^t = \sum_{j \in M_i} v_{ij}x_j^t$, noting that this is positive under our running assumption that $M_i \neq \emptyset$. Applying normalization, we get

$$ b_{ij}^{t+1} = \frac{B_i}{u_i^t} v_{ij} x_j^t, $$

Now if we sum over $i$ we get the proportional response dynamics. Moreover, we see that $b_{ij}^{t+1} > 0$ for all $i \in N$ and $j \in M_i$ since $v_{ij} > 0$ and $x_j^t > 0$. □
## 4.6 Convergence Rates

We have shown that the proportional response dynamics is equivalent to mirror descent with unit stepsize. Next we wish to apply the convergence-rate result from Theorem 3. Thus, we need to show that the objective in Program 14 is 1-smooth relative to the entropy reference function.

LEMMA 4 (1-SMOOTHNESS). The objective function $f$ from Program 14 is 1-smooth relative to the reference function $h(b) = \sum_{i \in N, j \in M_i} b_{ij} \log b_{ij}$, that is, for all $a = (a_{ij})_{i \in N, j \in M_i}$ and $b = (b_{ij})_{i \in N, j \in M_i}$ such that $a_{ij}, b_{ij} > 0$ for all $i \in N$ and $j \in M_i$ and such that $\sum_{j \in M_i} a_{ij} = \sum_{j \in M_i} b_{ij} = B_i$ for all $i \in N$, we have

$$f(a) \le f(b) + \langle \nabla f(b), a - b \rangle + D_h(a \| b)$$

PROOF. Note that $f(b)$ and $h(b)$ are differentiable when $b_{ij} > 0$ for all $i \in N$ and $j \in M_i$. For $a$ and $b$ as in the lemma statement, using (15), we have

$$ 
\begin{align*}
& f(a) - f(b) - \langle \nabla f(b), a - b \rangle \\
&= - \sum_{i \in N, j \in M_i} a_{ij} (\log v_{ij} - \log \frac{a_{ij}}{x_j(a)}) + \sum_{i \in N, j \in M_i} b_{ij} (\log v_{ij} - \log \frac{b_{ij}}{x_j(b)}) - \sum_{i \in N, j \in M_i} (a_{ij} - b_{ij}) (\log \frac{b_{ij}}{x_j(b)} - \log v_{ij}) \\
&= \sum_{i \in N, j \in M_i} a_{ij} \log(a_{ij}/x_j(a)) - \sum_{i \in N, j \in M_i} b_{ij} \log(b_{ij}/x_j(b)) - \sum_{i \in N, j \in M_i} (a_{ij} - b_{ij}) \log(b_{ij}/x_j(b)) \\
&= D_g(a \| b),
\end{align*}
$$

where $D_g$ is the Bregman divergence for the entropy-like function $g(b) = \sum_{i \in N, j \in M_i} b_{ij} \log(b_{ij}/x_j(b))$. It remains to show that $D_g(a \| b) \le D_h(a \| b)$:

$$ 
\begin{align*}
& D_h(a \| b) - D_g(a \| b) \\
&= \sum_{i \in N, j \in M_i} a_{ij} \log a_{ij} - \sum_{i \in N, j \in M_i} b_{ij} \log b_{ij} - \sum_{i \in N, j \in M_i} (a_{ij} - b_{ij}) \log b_{ij} \\
&\quad - \sum_{i \in N, j \in M_i} a_{ij} \log (a_{ij}/x_j(a)) + \sum_{i \in N, j \in M_i} b_{ij} \log (b_{ij}/x_j(b)) + \sum_{i \in N, j \in M_i} (a_{ij} - b_{ij}) \log (b_{ij}/x_j(b)) \\
&= \sum_{i \in N, j \in M_i} a_{ij} \log x_j(a) - \sum_{i \in N, j \in M_i} b_{ij} \log x_j(b) - \sum_{i \in N, j \in M_i} (a_{ij} - b_{ij}) \log x_j(b) \\
&= \sum_{i \in N, j \in M_i} a_{ij} \log(x_j(a)/x_j(b)) = \sum_{j \in M} x_j(a) \log(x_j(a)/x_j(b)) \ge 0
\end{align*}
$$

The last step follows by noting that the second-to-last expression is the KL divergence between $x(a)$ and $x(b)$, which is always nonnegative. $\square$

Now we can combine Lemma 4 with Theorem 3 to get a $D_h(b^* \| b^0)/t$ rate of convergence for the proportional response dynamics. If we start the dynamics at the uniform allocation $b_{ij}^0 = B_i/|M_i|$, we can upper bound the Bregman divergence $D_h(b^* \| b^0)$ as follows:

$$ 
\begin{align*}
D_h(b^* \| b^0) &= h(b^*) - h(b^0) \\
&= \sum_{i \in N} \sum_{j \in M_i} b_{ij}^* \log \frac{b_{ij}^*}{B_i/|M_i|} \tag{definitions of $h$ and $b^0$} \\
&= \sum_{i \in N} B_i \sum_{j \in M_i} q_{ij} \log \frac{q_{ij}}{1/|M_i|} \tag{writing $q_{ij} := b_{ij}^* / B_i$} \\
&= \sum_{i \in N} B_i \log |M_i| + \sum_{i \in N} B_i \sum_{j \in M_i} q_{ij} \log q_{ij} \tag{using $\sum_{j \in M_i} q_{ij} = 1$}
\end{align*}
$$
$$ \leq B \log m. \quad (\text{using } |M_i| \leq m \text{ and } \sum_{j \in M_i} q_{ij} \log q_{ij} \leq 0) $$

Combining this with Theorem 3 and Lemma 4, we obtain the desired rate of convergence for the proportional response dynamics.

**COROLLARY 3 (CONVERGENCE RATE OF THE PR DYNAMICS).** Let $b^*$ be an optimal solution to Program 14. Then the sequence of iterates of the proportional response dynamics satisfies

$$ f(b^t) - f(b^*) \leq \frac{B \log(m)}{t}. $$

For the particular case of $B = 1$, we therefore see that proportional response dynamics converges at a rate of $\log(m)/t$.

**4.6.1** *Convergence of Nash Social Welfare.* The convergence rate of Corollary 3 is stated in terms of the objective function $f$ of our new convex program (Program 14). We can deduce that the same convergence rate applies with respect to the Nash welfare objective. For an allocation $x$, let us write $\varphi(x) = -\sum_{i \in N} B_i \log \langle v_i, x \rangle$ for its objective value in Program 5 (interpreted as a minimization problem). Then we can establish the following connection between the objective value of a solution in the two programs, which we can think of as a consequence of the double duality between the two programs, though we give a direct proof in Section B.1.

**LEMMA 5.** Let $b$ be a feasible solution to Program 14. Then

$$ f(b) \geq \varphi(x(b)) + \sum_{i \in N} B_i \log B_i, $$

which holds with equality if $b$ is an optimal solution to Program 14.

Lemma 5 implies that $\varphi(x(b^t)) - \varphi(x(b^*)) \leq f(b^t) - f(b^*)$. Plugging this into Corollary 3, we obtain the following convergence bound for the (log) Nash product objective.

**COROLLARY 4 (CONVERGENCE OF NASH PRODUCT OBJECTIVE).** Let $b^*$ be an optimal solution to Program 14. Then the sequence of iterates of the proportional response dynamics satisfies

$$ \varphi(x(b^t)) - \varphi(x(b^*)) \leq \frac{B \log(m)}{t} $$

The convergence rate of Corollary 4 was recently independently obtained by Zhao [2023], after it had been an open question for almost forty years after the discovery of the dynamics by Cover [1984]. Zhao [2023] derived this rate directly. Our result gives a deeper explanation of the performance of the proportional response dynamics: it is equivalent to mirror descent with the entropy reference function applied to Program 14.

*Convergence of Proportional Fairness and Core.* Finally, we will give a convergence bound in terms of fairness properties of the allocation $x^t$. We will do this by showing that an allocation that has approximately optimal Nash social welfare must also approximate these fairness properties.

The first such property is known as proportional fairness (PF). This property was first introduced in the context of fairly allocating bandwidth in networks [Kelly et al., 1998], and has also been studied in the allocation of indivisible private goods [Caragiannis et al., 2019, App. D] as well as for public goods [Banerjee et al., 2023] and in the distortion of voting rules [Ebadian et al., 2024].

An allocation $x$ is proportionally fair if

$$ \sum_{i \in N} B_i \frac{u_i(y)}{u_i(x)} \leq B \quad \text{for all allocations } y \iff \sum_{i \in N} B_i \frac{v_{ij}}{u_i(x)} \leq 1 \quad \text{for all } j \in M. $$
That these two conditions are equivalent follows from linearity of $u_i(y)$ and the definition of allocations requiring that $\sum_{j \in M} y_j \le B$. Intuitively, the PF condition says that the multiplicative utility gain of moving from $x$ to another allocation cannot be too high. Note for example that if some agent has utility 0 in allocation $x$, then the left-hand side is infinite (by considering some $j$ with $v_{ij} > 0$), and thus $x$ is not proportionally fair.

It is known that Lindahl equilibrium allocations are proportionally fair, and indeed our proof of Theorem 4, which shows that allocations that maximize the Nash social welfare are Lindahl equilibrium allocations, establishes proportional fairness as an intermediate step.

Let us define the PF value of an allocation $x$ as

$$PF(x) = \max_{j \in M} \sum_{i \in N} B_i \frac{v_{ij}}{u_i(x)},$$

so that an allocation is proportionally fair if and only if $PF(x) \le 1$.

We will show that allocations that approximately maximize the Nash social welfare satisfy an approximate version of the PF condition, in the sense of having a PF value not much higher than 1. Recall that we write $\varphi(x) = - \sum_{i \in N} B_i \log(v_i, x)$ for the (negative) Nash social welfare of an allocation $x$. Let $\varphi^*$ denote Nash social welfare of the optimum allocation (i.e., the minimum value of $\varphi$). Write $B_{\min} = \min_{i \in N} B_i$.

**THEOREM 7 (APPROXIMATE NASH GIVES APPROXIMATE PF).** Let $0 \le \varepsilon < \frac{1}{2}$ such that $\varepsilon < \frac{B_{\min}}{2}$, and consider an allocation $x$ with $\varphi(x) \le \varphi^* + \varepsilon$, i.e., that is $\varepsilon$-optimal w.r.t. Nash social welfare. Then

$$PF(x) \le \frac{1 + 2n\sqrt{\varepsilon/B} + n\varepsilon/B}{1 - \sqrt{2\varepsilon/B_{\min}}}.$$

The proof uses $\varepsilon$-KKT conditions and appears in Section B.1.

For the special case where $B = 1$ and $B_i = 1/n$ for all $i \in N$, the bound of Theorem 7 reads as

$$PF(x) = \max_{j \in M} \sum_{i \in N} \frac{v_{ij}}{n u_i(x)} \le \frac{1 + 2n\sqrt{\varepsilon} + n\varepsilon}{1 - \sqrt{2n\varepsilon}} = 1 + \frac{1 + 2n\sqrt{\varepsilon} + n\varepsilon - (1 - \sqrt{2n\varepsilon})}{1 - \sqrt{2n\varepsilon}}.$$

For $\varepsilon < \frac{1}{8n}$, one can show that the right-hand side is upper bounded by $1 + 8n\sqrt{\varepsilon}$ and thus

$$PF(x) \le 1 + 8n\sqrt{\varepsilon}.$$

It is known that an approximately proportionally fair allocation lies in a (multiplicatively) approximate core [see, e.g., Ebadian et al., 2024, Prop. 2.6]. We include a proof for completeness.

**LEMMA 6 (APPROXIMATE PF IMPLIES APPROXIMATE CORE).** Let $x$ be an allocation with $PF(x) \le \alpha$. Then $x$ lies in the $\alpha$-approximate core, in the sense that there is no blocking coalition $S$ with objection $z$ such that $\sum_{j \in M} z_j \le \sum_{i \in S} B_i$ and such that $u_i(z) > \alpha \cdot u_i(x)$ for all $i \in S$.

**PROOF.** We show the contrapositive. Suppose that $x$ admits a blocking coalition $S$ with objection $z$ such that $\sum_{j \in M} z_j \le \sum_{i \in S} B_i := B_S$ and $u_i(z) > \alpha u_i(x)$ for all $i \in S$. Consider the allocation $y = \frac{B}{B_S} z$. Then $u_i(y) = \frac{B}{B_S} u_i(z)$ by linearity of $u_i$. Thus $u_i(y) > \alpha \frac{B}{B_S} u_i(x)$ for all $i \in S$ and hence

$$\sum_{i \in N} B_i \frac{u_i(y)}{u_i(x)} \ge \sum_{i \in S} B_i \frac{u_i(y)}{u_i(x)} > \sum_{i \in S} B_i \alpha \frac{B}{B_S} = \alpha B.$$

Dividing by $B$, this implies that $PF(x) > \alpha$. $\square$

We can combine all these results into convergence results with respect to PF value and core approximation.
COROLLARY 5 (CONVERGENCE OF PF VALUE AND CORE). For each $t \ge 1$, let

$$ \varepsilon_t = \frac{B \log(m)}{t} \quad \text{and} \quad \alpha_t = \frac{1 + 2n\sqrt{\varepsilon_t/B} + n\varepsilon_t/B}{1 - \sqrt{2\varepsilon_t/B_{\min}}} $$

Note that $\varepsilon_t \to 0$ and $\alpha_t \to 1$ as $t \to \infty$. The sequence $(b^t)_{t \ge 1}$ of iterates of the proportional response dynamics induces a sequence of allocations $x^t = x(b^t)$ such that for each $t \ge 1$ that is large enough such that $\varepsilon_t < \min\{\frac{1}{2}, \frac{B_{\min}}{2}\}$, we have that $\mathrm{PF}(x^t) \le \alpha_t$, and $x^t$ lies in the $\alpha_t$-approximate core.

This follows by chaining together Corollary 4 (convergence rate in terms of Nash welfare), Theorem 7 (PF value guaranteed by Nash approximation), and Lemma 6 (PF value implies core approximation).

REMARK 1 (COMPUTATION OF APPROXIMATE CORE SOLUTIONS). The results in this section also imply that in the uncapped public goods setting, an approximate core allocation can be computed in polynomial time by finding an approximately Nash welfare optimal allocation, for example using the ellipsoid algorithm [see, e.g., Vishnoi, 2021, Theorem 13.1]. Another way to compute an approximate core solution is to find an allocation with low PF value [Fain et al., 2018, Appendix B]. An entirely different method of computing core allocations is proposed by Martinez Mori and Toriello [2025], who give a cutting plane algorithm for computing core outcomes in a class of NTU games that includes the uncapped public goods model.

It is also possible to show that an allocation $x$ with a low PF value (such as $\mathrm{PF}(x) \le 1 + \varepsilon$) forms an approximate Lindahl equilibrium using the prices $p_{ij} = B_i v_{ij} / u_i(x)$ which is well-defined since $u_i(x) > 0$ when the PF value is finite. Note that an approximate version of profit maximization is then satisfied by definition of PF value since $\sum_{i \in N} p_{ij} = \mathrm{PF}(x) \le 1 + \varepsilon$ for each $j \in M$, and affordability and utility maximization hold exactly (observing that for each agent, the bang-per-buck ratio is constant across projects). Note that this is a different notion of approximate Lindahl equilibrium than the one we will consider later (Definition 6).

## 5 Capped Public Goods

Next we study the capped public goods setting, where we have a constraint $x_j \le \mathrm{cap}_j$ for each good $j \in M$. One may naïvely attempt to add this constraint to Program 5 maximizing Nash welfare, but this will not lead to a Lindahl equilibrium and not even to a weak core solution.

EXAMPLE 4 (MAX NASH WELFARE IS NOT LINDAHL). Consider the following instance:<fnref n="5" />

<table><thead><tr><th></th><th>B<sub>i</sub></th><th>Project 1</th><th>Project 2</th><th>Project 3</th><th>Project 4</th></tr></thead><tbody><tr><td>Agent 1</td><td>2</td><td>1</td><td>1</td><td>0</td><td>0</td></tr><tr><td>Agent 2</td><td>2</td><td>1</td><td>0</td><td>1</td><td>0</td></tr><tr><td>Agent 3</td><td>2</td><td>0</td><td>0</td><td>0</td><td>1</td></tr><tr><td>cap<sub>j</sub></td><td></td><td>3</td><td>&infin;</td><td>&infin;</td><td>&infin;</td></tr></tbody></table>

The allocation that maximizes Nash welfare subject to the cap constraints is $x = (3, 0, 0, 3)$. This allocation violates the weak core: consider the blocking coalition $S = \{1, 2\}$ and the objection $z = (3, 0.5, 0.5, 0)$ which gives each $i \in S$ a utility of $u_i(x) = 3.5$ which is strictly higher than $u_i(x) = 3$. Thus, by Proposition 2, $x$ is not a Lindahl equilibrium. This is not an artifact of having zero-valuations; replacing $1$s by $10$ and $0$s by $1$ leads to the same situation.

<footnote n="5">⁵This example is similar to well-known instances in (indivisible) approval-based multi-winner voting where the PAV rule fails the core [Aziz et al., 2017, Peters, 2025, Peters and Skowron, 2020].</footnote>
This failure of the Nash rule to extend to capped settings has been noted several times. Suzuki and Vollen [2024, Proposition 4.1] provide an example similar to the one above. Garg et al. [2021, Comment A.1] write that Lindahl equilibrium “does not transform into a Fisher market”. While the Nash optimum fails the core, it can be shown that it satisfies a 2-approximation to it [Munagala et al., 2022b, Corollary 3.5].

## 5.1 Adapting the Convex Program

We will show in this section that Program 6 can be used to compute a Lindahl equilibrium in the capped public goods setting through a simple modification: we simply add a constraint $x_j \le cap_j$ for all $j \in M$. Surprisingly, we will show that this works, even though the exact same constraint does not work for the original EG program (Program 5) for maximizing Nash welfare. Thus, we obtain the first efficient algorithm for capped public goods, thereby resolving an open problem first posed by Fain et al. [2016].

Our modified program for capped public goods is as follows, where as before we write $x_j(b) = \sum_{i \in N_j} b_{ij}$ as a shorthand:

$$ \begin{array}{ll} \max_{b \ge 0} & \displaystyle\sum_{i \in N, j \in M_i} b_{ij} \left( \log v_{ij} - \log \left( \frac{b_{ij}}{x_j(b)} \right) \right) \\ \text{s.t.} & \displaystyle\sum_{j \in M_i} b_{ij} \le B_i \quad \text{for all } i \in N \\ & x_j(b) \le cap_j \quad \text{for all } j \in M \end{array} \qquad (16) $$

Note that the agents' budget constraints are written as inequalities in this version of the problem, since the caps may preclude feasible solutions from exhausting all agents' budgets (except when the instance is cap-sufficient, see Definition 3 and Proposition 1).

We will require that all valuations have been rescaled such that $v_{ij} > 1$ for all $v_{ij} \ne 0$,$^6$ to ensure that the terms “$b_{ij} \log v_{ij}$” in the objective function have a positive coefficient. Without the rescaling, optimal solutions may not spend the entire budget of an agent even when it is possible to do so. Rescaling is without loss of generality, since the Lindahl equilibrium is invariant to scaling valuations by a positive constant (even different constants for different agents). We did not have to do this rescaling in the uncapped version of the program, because we used an equality constraint for agent budgets in that version.

## 5.2 The Convex Program computes a Lindahl Equilibrium

In this section, we will prove that Program 16 computes a zero-respecting Lindahl equilibrium. This provides the first existence proof of Lindahl equilibrium in the capped public goods setting that does not use a fixed-point theorem. It also proves the existence of an equilibrium that is zero-respecting, which does not quite follow from the existence result of Foley [1970], since his model does not allow for caps and does not allow for valuations equal to 0 (since it assumes strictly monotonic valuations). In addition, as explained in Footnote 3, zero-respecting equilibria cannot be obtained by a limit argument that replaces zero valuations by $\epsilon$ and letting $\epsilon \to 0$. The zero-respecting property is intuitively attractive, since it prevents agents from having to contribute their budget to goods that they do not have a positive valuation for.

Our proof proceeds by analyzing the KKT conditions (Theorem 1) applied to Program 16. In the notation of Theorem 1, the objective function is obtained by multiplying by $-1$, giving $f(b) = - \sum_{i \in N, j \in M_i} b_{ij} \log v_{ij} + \sum_{j \in M} h(b_j)$ where $b_j$ is the vector $(b_{ij})_{i \in N_j}$ and $h$ is the function defined as $h(x) = \sum_i x_i \log \frac{x_i}{\sum_k x_k}$ when all $x_i$ are non-negative (and $h(0) = 0$), and $+\infty$ otherwise.

<footnote>$^6$A similar normalization is used by Brandl et al. [2022].</footnote>
To write down the KKT conditions, we need to compute the subdifferential of $f$.

**LEMMA 7 (SUBDIFFERENTIAL OF OBJECTIVE FUNCTION).** Let $f$ be the negative of the objective function of Program 16, and let $b = (b_{ij})_{i \in N, j \in M_i}$ be a feasible point. If there is some $i \in N$ and $j \in M_i$ such that $b_{ij} = 0$ but $x_j(b) > 0$, then $\partial f(b) = \emptyset$. Otherwise, for all vectors $g = (g_{ij})_{i \in N, j \in M_i}$, we have

$$ g \in \partial f(b) \implies \begin{cases} \text{for all } j \in M \text{ s.t. } x_j(b) > 0, \text{ and all } i \in N_j, & g_{ij} = -\log v_{ij} + \log \frac{b_{ij}}{x_j(b)}, \\ \text{for all } j \in M \text{ s.t. } x_j(b) = 0, & \sum_{i \in N_j} e^{g_{ij} + \log v_{ij}} \le 1. \end{cases} $$

The detailed proof is in Section A.

Based on this computation of the subdifferential of the objective function of Program 16, we can now prove that an optimal solution to the program will form a Lindahl equilibrium.

**THEOREM 8 (OPTIMAL SOLUTIONS ARE LINDAHL).** Assume that valuations are rescaled such that $v_{ij} > 1$ for all $v_{ij} \neq 0$. Let $b^*$ be an optimal solution to Program 16 with induced allocation $x^* = (x_j(b^*))_{j \in M}$. Then there exist zero-respecting prices $p$ such that $(x^*, p)$ forms a Lindahl equilibrium for the capped public goods setting.

**PROOF.** We apply the KKT conditions of Theorem 1 to Program 16, noting that Slater's constraint qualification is satisfied by a solution setting all $b_{ij}$ to a sufficiently small but positive value. For convenience, let us label the constraints of the program using the notation of the KKT conditions:

$$ \begin{align*} h_i^{(1)}(b) &= \sum_{j \in M_i} b_{ij} - B_i && \text{for all } i \in N, \\ h_j^{(2)}(b) &= \sum_{i \in N_j} b_{ij} - \text{cap}_j && \text{for all } j \in M, \\ h_{ij}^{(3)}(b) &= -b_{ij} && \text{for all } i \in N \text{ and } j \in M_i. \end{align*} $$

All these functions are affine and thus differentiable, with singleton subdifferentials.

Let $b^*$ be an optimal solution to Program 16. By Theorem 1, we know that there exists a subgradient $g^* \in \partial f(b^*)$ such that

$$ g^* + \sum_{i \in N} \lambda_i \nabla h_i^{(1)}(b^*) + \sum_{j \in M} \mu_j \nabla h_j^{(2)}(b^*) + \sum_{i \in N, j \in M_i} \eta_{ij} \nabla h_{ij}^{(3)}(b^*) = 0, \quad (17) $$

with $\lambda_i, \mu_j, \eta_{ij} \ge 0$ and such that complementary slackness holds. Equation (17) can be equivalently stated as

$$ g_{ij}^* + \lambda_i + \mu_j - \eta_{ij} = 0 \quad \text{for all } i \in N \text{ and } j \in M_i. \quad (18) $$

Let us now understand the implications of (17). We go through each project $j \in M$, and distinguish the cases where $x_j^* = \text{cap}_j$, where $0 < x_j^* < \text{cap}_j$, and where $x_j^* = 0$.

* Consider a project $j \in M$ with $x_j^* = \text{cap}_j$. Let $i \in N_j$. Note that $b_{ij}^* > 0$, since otherwise the subdifferential is empty, contradicting $g^* \in \partial f(b^*)$. Thus, by complementary slackness, $\eta_{ij} = 0$. Then the $ij$'th component of (17) implies

$$ 0 = -\log v_{ij} + \log \frac{b_{ij}^*}{x_j^*} + \lambda_i + \mu_j $$

and thus, because $\mu_j \ge 0$, that

$$ 0 \ge -\log v_{ij} + \log \frac{b_{ij}^*}{x_j^*} + \lambda_i. $$

Rearranging and exponentiating both sides, we conclude that

$$ v_{ij} \ge e^{\lambda_i} \frac{b_{ij}^*}{x_j^*}. $$
* Consider a project $j \in M$ with $0 < x_j^* < \text{cap}_j$. Let $i \in N_j$. Again note that $b_{ij}^* > 0$ since otherwise the subdifferential $\partial f(b^*)$ is empty. Then, by complementary slackness, $\mu_j = \eta_{ij} = 0$. Thus, the $ij$'th component of (17) implies

$$0 = g_{ij}^* + \lambda_i = -\log v_{ij} + \log \frac{b_{ij}^*}{x_j^*} + \lambda_i.$$

Rearranging and exponentiating both sides, we conclude that

$$v_{ij} = e^{\lambda_i} \frac{b_{ij}^*}{x_j^*}.$$

* Finally, consider a project $j \in M$ with $x_j^* = 0$. Thus by complementary slackness, $\mu_j = 0$. Let $i \in N_j$. By definition of $x_j^*$, we have $b_{ij}^* = 0$. The $ij$'th component of (17) implies

$$0 = g_{ij}^* + \lambda_i - \eta_{ij}.$$

Writing $w_{ij} = g_{ij}^* + \log v_{ij}$ and noting that $\eta_{ij} \ge 0$, we get

$$0 \le w_{ij} - \log v_{ij} + \lambda_i.$$

Rearranging and exponentiating both sides, we conclude that

$$v_{ij} \le e^{\lambda_i} e^{w_{ij}}.$$

Collecting all our conclusions, we have found that for $i \in N$ and $j \in M_i$,

$$v_{ij} = \begin{cases} \ge e^{\lambda_i} \frac{b_{ij}^*}{x_j^*} & \text{if } x_j^* = \text{cap}_j, \\ = e^{\lambda_i} \frac{b_{ij}^*}{x_j^*} & \text{if } 0 < x_j < \text{cap}_j, \\ \le e^{\lambda_i} e^{w_{ij}} & \text{if } x_j^* = 0. \end{cases} \quad (19)$$

We now form a Lindahl equilibrium using the following prices for $i \in N$ and $j \in M_i$:

$$p_{ij} = \begin{cases} \frac{b_{ij}^*}{x_j^*} & \text{if } x_j^* > 0, \\ e^{w_{ij}} & \text{if } x_j^* = 0. \end{cases} \quad (20)$$

For $i, j$ such that $v_{ij} = 0$, we set $p_{ij} = 0$ and $b_{ij}^* = 0$. It follows from these definitions that the prices are zero-respecting. Note that with these prices, the identity $p_{ij}x_j^* = b_{ij}^*$ holds for all $i \in N$ and $j \in M_i$ (by case analysis on whether $x_j^* = 0$).

We claim that $(x^*, p)$ forms a Lindahl equilibrium.

For profit maximization, note that if $x_j^* > 0$, then $\sum_{i \in N} p_{ij} = \sum_{i \in N_j} b_{ij}^* / x_j^* = 1$ by definition of $x_j^*$ and using $p_{ij} = 0$ when $v_{ij} = 0$, and if $x_j^* = 0$, then $\sum_{i \in N} p_{ij} = \sum_{i \in N_j} e^{w_{ij}} \le 1$ from the subdifferential characterization in Lemma 7.

For the affordability condition, for each $i \in N$ we have

$$\langle p_i, x^* \rangle = \sum_{j \in M} p_{ij} x_j^* = \sum_{j \in M_i} b_{ij}^* \le B_i,$$

using the identity $p_{ij}x_j^* = b_{ij}^*$ and the feasibility of $b^*$ in Program 16.

It remains to prove utility maximization. Fix an agent $i \in N$. We will show that $x^*$ is utility maximizing subject to the budget constraint $\langle p_i, x \rangle \le B_i$. We divide the proof of this into two parts, based on whether agent $i$ spends their entire budget under $p_i$ or not.

First suppose that $\sum_{j \in M_i} b_{ij}^* < B_i$. We want to show that this only occurs when all projects $j \in M$ with $v_{ij} > 0$ have $x_j^* = \text{cap}_j$. Suppose for a contradiction that $x_j^* < \text{cap}_j$ for some $j \in M_i$. By complementary slackness, we have $\lambda_i = \mu_j = 0$. Thus, (17) implies $g_{ij}^* \ge 0$. If $x_j^* > 0$, then we
have $g_{ij}^* = -\log v_{ij} + \log(b_{ij}^*/x_j^*)$ and thus $g_{ij}^* < 0$ because $v_{ij} > 1$ by assumption and $b_{ij}^*/x_j^* \le 1$ by definition of $x_j^*$, a contradiction. Otherwise, if $x_j^* = 0$, then $e^{g_{ij}^*+\log v_{ij}} \le 1$ by the subdifferential characterization in Lemma 7, which implies $g_{ij}^* + \log v_{ij} \le 0$. Hence $g_{ij}^* \le -\log v_{ij} < 0$ since $v_{ij} > 1$, again a contradiction.

Thus, we have shown that if agent $i$ does not spend their whole budget, then they are already achieving the maximal possible utility under any feasible allocation (because $x_j^* = \text{cap}_j$ for all $j \in M$ such that $v_{ij} > 0$), and thus $x^*$ is utility maximizing for $i$.

Next consider the case where $\sum_{j \in M_i} b_{ij}^* = B_i$. Combining (19) and (20), we have that the “bang per buck” of project $j \in M_i$ satisfies

$$ \frac{v_{ij}}{p_{ij}} \begin{cases} \ge e^{\lambda_i} & \text{if } x_j^* = \text{cap}_j, \\ = e^{\lambda_i} & \text{if } 0 < x_j^* < \text{cap}_j, \\ \le e^{\lambda_i} & \text{if } x_j^* = 0. \end{cases} \qquad (21) $$

Now, an affordable bundle $y$ is utility maximizing for $i$ (among bundles satisfying the cap constraints) if and only if (i) for every project with $\frac{v_{ij}}{p_{ij}} > e^{\lambda_i}$, we have $y_j = \text{cap}_j$, and (ii) for every project with $\frac{v_{ij}}{p_{ij}} < e^{\lambda_i}$, we have $y_j = 0$, and (iii) the whole budget is spent. Because $x^*$ is such a bundle, it is utility maximizing for $i$.

More formally, let $y = (y_j)_{j \in M}$ be an allocation such that $0 \le y_j \le \text{cap}_j$ for all $j \in M$ and $\langle p_i, y \rangle \le B_i$. Then for every $j \in M$ with $x_j^* = 0$ we have $y_j - x_j^* \ge 0$, and for every $j \in M$ with $x_j^* = \text{cap}_j$ we have $y_j - x_j^* \le 0$. Thus

$$ \begin{align*} u_i(y) - u_i(x^*) &= \sum_{j \in M} v_{ij}(y_j - x_j^*) \\ &= \sum_{\substack{j \in M_i \\ x_j^*=0}} v_{ij}(y_j - x_j^*) + \sum_{\substack{j \in M_i \\ 0<x_j^*<\text{cap}_j}} v_{ij}(y_j - x_j^*) + \sum_{\substack{j \in M_i \\ x_j^*=\text{cap}_j}} v_{ij}(y_j - x_j^*) \\ &\le \sum_{\substack{j \in M_i \\ x_j^*=0}} e^{\lambda_i} p_{ij}(y_j - x_j^*) + \sum_{\substack{j \in M_i \\ 0<x_j^*<\text{cap}_j}} e^{\lambda_i} p_{ij}(y_j - x_j^*) + \sum_{\substack{j \in M_i \\ x_j^*=\text{cap}_j}} e^{\lambda_i} p_{ij}(y_j - x_j^*) \\ &= e^{\lambda_i} \sum_{j \in M_i} p_{ij}(y_j - x_j^*) = e^{\lambda_i} (\langle p_i, y \rangle - \langle p_i, x^* \rangle) \le 0. \end{align*} $$

In the last line we used that $(x^*, p)$ is zero-respecting for the second equality, and we used that $\langle p_i, y \rangle \le B_i = \langle p_i, x^* \rangle$ for the last inequality. It follows that $u_i(y) \le u_i(x^*)$, establishing the utility maximization condition. $\square$

## 5.3 Approximately Optimal Solutions

We have now seen in Theorem 8 that an optimal solution to our convex program forms a Lindahl equilibrium in the capped public goods setting. This makes for a direct existence proof (since the feasible set of the program is compact and the objective function is continuous), but it does not immediately give us a way to compute a Lindahl equilibrium allocation. Indeed, even what it means to compute a Lindahl equilibrium is ill-defined since, as we saw in Example 3, there are simple rational instances where all Lindahl equilibria are irrational, so that no algorithm could write down the Lindahl equilibrium exactly. In addition, algorithms for convex programming do not produce exactly optimal but only $\epsilon$-optimal solutions.

To get around this issue, we will show that an approximate solution to our convex program produces an approximate Lindahl equilibrium. Our proof needs to relax the conditions of budget
feasibility, utility maximization, and profit maximization in the definition of Lindahl equilibrium, leading to the following approximate equilibrium concept.

**DEFINITION 6 (ε-LINDAHL EQUILIBRIUM).** Let $\varepsilon \ge 0$. A pair $(x, p)$ of a vector $x = (x_j)_{j \in M}$ such that $0 \le x_j \le cap_j$ for all $j \in M$ and a set of personalized prices $p$ forms an $\varepsilon$-Lindahl equilibrium if

* $x$ is approximately budget-feasible: $\sum_{j \in M} x_j \le B + \varepsilon$ (i.e., $x$ may overshoot the total budget),

* $x$ is affordable: we have $\langle p_i, x \rangle \le B_i$ for every $i \in N$,

* $x$ is approximately utility-maximizing: for every $i \in N$ and every $y \in \mathbb{R}_{\ge 0}^m$ such that $0 \le y_j \le cap_j$ for all $j \in M$ and such that $\langle p_i, y \rangle \le B_i$, we have $u_i(x) \ge u_i(y) - \varepsilon$,

* $x$ is approximately profit-maximizing: for every $j \in M$ we have $\sum_{i \in N} p_{ij} \le 1$, and whenever $x_j > 0$ then $\sum_{i \in N} p_{ij} \ge 1 - \varepsilon/x_j$.

We are not claiming that this is the most natural definition of $\varepsilon$-Lindahl equilibrium (especially because the way we relax profit maximization is not natural), but it does imply that the associated allocation approximately satisfies the core, where the core definition is relaxed in an additive sense by $\varepsilon$ and the allocation itself overshoots the budget by $\varepsilon$.

**LEMMA 8 (ε-LINDAHL EQUILIBRIUM IMPLIES ε-CORE).** Suppose $(x, p)$ forms an $\varepsilon$-Lindahl equilibrium in the sense of Definition 6, with $\sum_{j \in M} x_j \le B + \varepsilon$. Then there does not exist a blocking coalition $S \subseteq N$ and objection $z = (z_j)_{j \in M} \in \mathbb{R}_{\ge 0}^m$ with $0 \le z_j \le cap_j$ for all $j \in M$, such that $\sum_{j \in M} z_j \le \sum_{i \in S} B_i$ and $u_i(z) > u_i(x) + \varepsilon$ for all $i \in S$.

**PROOF.** The proof is similar to the exact case (Proposition 2).

Suppose $S \subseteq N$ is a blocking coalition with objection $z$ satisfying $\sum_{j \in M} z_j \le \sum_{i \in S} B_i$. Since for every $i \in S$ we have $u_i(x) < u_i(z) - \varepsilon$, the utility maximization condition of $\varepsilon$-Lindahl equilibrium implies that $z$ cannot be affordable for $i$, so that $\langle p_i, z \rangle > B_i$. Summing over $i \in S$, we get that $\sum_{i \in S} \langle p_i, z \rangle > \sum_{i \in S} B_i$. Thus, due to the non-negativity of prices and the first part of the approximate profit maximization condition of $\varepsilon$-Lindahl equilibrium, we have

$$ \sum_{i \in S} B_i < \sum_{i \in S} \langle p_i, z \rangle \le \sum_{i \in N} \langle p_i, z \rangle \le \langle 1, z \rangle \le \sum_{i \in S} B_i, $$

a contradiction. $\square$

We are now ready to state our approximation result.

**THEOREM 9 (APPROXIMATE SOLUTIONS GIVE $\varepsilon$-LINDAHL EQUILIBRIUM).** Let $0 < \varepsilon \le \min\{1, \text{cap}_{\min}\}$ where $\text{cap}_{\min} = \min_{j \in M} cap_j$. Assume that $v_{ij} > 1$ whenever $v_{ij} > 0$, that $B \ge 1$, and that $cap_j \le B$ for all $j \in M$. There is an algorithm computing an $\varepsilon$-Lindahl equilibrium for the capped public goods setting running in polynomial time (with a logarithmic dependence on $1/\varepsilon$).

The algorithm of Theorem 9 works by slightly perturbing the input instance, and then solving Program 16 to an appropriately chosen accuracy of $C \cdot \varepsilon^3$, where $C$ depends single-exponentially on problem parameters (number of public goods, agent endowments, caps, largest $v_{ij}$). Thus, the runtime claim of Theorem 9 is based on using an algorithm for solving the convex program that has a logarithmic or polylogarithmic dependence on the desired accuracy $1/\varepsilon$ of the solution, such as the ellipsoid algorithm or interior-point methods. If using a solution algorithm for convex programming with a polynomial dependence on the accuracy (like most first-order methods), the runtime would be exponential in problem parameters.

The proof of Theorem 9 appears in Section B.2. It makes use of $\varepsilon$-KKT conditions. As a first step, we prove that approximately optimal solutions to Program 16 approximately maximize agent utilities, under the additional assumption that every project receives a total funding of at least $t$, i.e., $x_j > t$ for all $j \in M$, for some given $t > 0$. We then remove the latter assumption by perturbing
the input instance slightly so that every project is guaranteed at least *t* funding; this perturbation causes the approximation errors in the budget feasibility and profit maximization conditions.

## 5.4 Discussion of the Convex Program

*Comparison to Fisher markets.* It is interesting to contrast our program with the Fisher market setting with private goods. There, the Eisenberg-Gale program also does not allow the introduction of saturating constraints on the primal variables (which correspond to a maximum amount of a good that an agent may receive). Yet it is not possible to add such constraints to the Shmyrev program for Fisher markets either, because that program does not contain the original primal variables encoding the allocation (in contrast to our public-goods program). Instead, the allocation is obtained through a nonlinear function of the optimization variables in the Shmyrev program.<fnref n="7" /> Thus, *Program 6* allows for a type of saturating consumption constraint that has previously never been possible for either private or public goods.

*Scale-freeness.* Subject to our requirement that $v_{ij} > 1$ whenever $v_{ij} \neq 0$, the optimal solution to our program does not change if the valuations of some agent *i* are multiplied by a positive constant $\alpha > 0$, since this operation just adds a constant term $B_i \log \alpha$ to the objective. The program is also invariant to changing the “currency” by multiplying all the budgets $B_i$ and all the caps by a common positive constant $\beta > 0$. This is because the feasible solutions of the program before the change are in bijection with the feasible solutions of the program after the change (mapping $b_{ij} \mapsto \beta \cdot b_{ij}$), and this bijection preserves the objective value of each solution up to multiplying it by $\beta$.

*Discontinuity as $v_{ij} \to 0$.* Given that our program computes a Lindahl equilibrium that is zero-respecting, its output is not continuous as $v_{ij} \to 0$. This is unavoidable due to *Example 2* (see *Footnote 3*), and unsurprising in light of our normalization of valuations.

*Not all Lindahl equilibria are optimal solutions.* In the uncapped setting, every Lindahl equilibrium forms an optimum of both *Program 6* and the Eisenberg-Gale program. As the following example shows, this is not the case for the capped setting, where *Program 16* captures only a strict subset of Lindahl equilibria. The example also shows that Lindahl equilibria are not unique in utilities.

**EXAMPLE 5 (LINDAHL EQUILIBRIUM IS NOT UNIQUE IN UTILITIES).** Consider the following instance:

<table><thead><tr><th></th><th>$B_i$</th><th>Project 1</th><th>Project 2</th><th>Project 3</th></tr></thead><tbody><tr><td>Agent 1</td><td>1</td><td>1</td><td>1</td><td>0</td></tr><tr><td>Agent 2</td><td>1</td><td>1</td><td>0</td><td>1</td></tr><tr><td>cap<sub>j</sub></td><td></td><td>1</td><td>$\infty$</td><td>$\infty$</td></tr></tbody></table>

This instance is cap-sufficient, since each agent has a positive valuation for an uncapped project. Let us determine the set of zero-respecting Lindahl equilibria $(x, p)$. By *Corollary 1*, $x$ is Pareto-optimal, and therefore $x_1 = 1$ and $x_2 + x_3 = 1$. For each $\gamma \in [0, 1]$, one can check that $x = (1, 1-\gamma, \gamma)$ forms a Lindahl equilibrium together with the prices $p_1 = (\gamma, 1, 0)$ and $p_2 = (1-\gamma, 0, 1)$. It follows that, in the capped setting, Lindahl equilibria are not unique in utilities: in the equilibrium allocation $(1, 1, 0)$, agent 1 obtains utility 2, but in the equilibrium allocation $(1, 0, 1)$, agent 1 obtains utility 1.

Note that the allocation $x^* = (1, \frac{1}{2}, \frac{1}{2})$ is the unique allocation that is intuitively fair and respects the symmetry of the instance, but this allocation is not the only Lindahl equilibrium. However, *Program 16* uniquely selects $x^*$, because on this instance its objective function simplifies to $-b_{11} \log b_{11} - b_{21} \log b_{21}$ which is maximized by $b_{11} = b_{21} = 0.5$, leaving each agent a budget of 0.5 to spend on other projects.

<footnote n="7">⁷It is known that spending constraints on a per-buyer basis can be introduced to the Shmyrev program [Birnbaum et al., 2011], but these are very different from saturating constraints on the primal variables.</footnote>
<figure><img src="image_3.png" /><figcaption>Fig. 2. Results of our experiments on Pabulib instances, showing the solve time of the MOSEK solver as a function of the number of projects in the instance. The largest instances are from Warsaw and Amsterdam.</figcaption></figure>

An intuitive reason for why our program does not capture all Lindahl equilibria is that the KKT conditions that we analyzed in the proof of Theorem 8 impose an additional constraint on the contributions of agents to projects that are fully funded ($x_j = cap_j$), saying that every agent's bang-per-buck ratio for that good should exceed their “normal” bang-per-buck ratio $e^{\lambda_i}$ by a common agent-independent factor $e^{\mu_j}$. On the above example, this leads the program to select the most natural equilibrium (and this remains the case if the caps and endowments are varied), suggesting that our convex program might define a desirable decision rule for selecting Lindahl equilibria.

## 5.5 Computation and Experiments

Let us briefly discuss how to solve Program 16. Numerically, the program can be solved using any conic convex optimization solver supporting exponential cones, such as MOSEK, COPT, Clarabel, ECOS, or SCS, by formulating the program as

$$ 
\begin{array}{ll}
\max_{b \ge 0, x \ge 0, t} & \sum_{i \in N, j \in M_i} b_{ij} \log v_{ij} - t_{ij} \\
\text{s.t.} & (x_j, b_{ij}, -t_{ij}) \in \mathcal{K}_{\text{exp}} \text{ for all } i \in N, j \in M_i \\
& \sum_{j \in M_i} b_{ij} \le B_i \text{ for all } i \in N \\
& x_j = \sum_{i \in N_j} b_{ij} \text{ for all } j \in M \\
& x_j \le cap_j \text{ for all } j \in M
\end{array}
$$

where $\mathcal{K}_{\text{exp}} = \{(x_1, x_2, x_3) : x_1 \ge x_2 e^{x_3/x_2}\}$ is the (primal) exponential cone. We built a simple online tool for solving moderate-size instances with the SCS solver [O'Donoghue et al., 2016], available at dominik-peters.de/demos/lindahl/. From a complexity-theoretic perspective, an $\epsilon$-optimal solution to Program 16 can be computed in polynomial time using the ellipsoid method [see, e.g., Vishnoi, 2021, Theorem 13.1].

To evaluate the performance of computing Lindahl equilibrium via Program 16, we implemented it using the MOSEK solver and applied it to the participatory budgeting datasets in the Pabulib repository [Faliszewski et al., 2023]. We find that the program can be solved quite quickly, with solve times shown in Section 5.5. The longest solve time we encountered was 822s (or 1489s including the time to write down the encoding) for an instance from Warsaw with 14 897 voters (with 11 426 distinct approval sets) and 134 projects.
<figure><img src="image_4.png" /><figcaption>Fig. 3. An example of a piecewise-linear concave function.</figcaption></figure>

For the uncapped setting, Zhao and Freund [2023, Section 4.2] present some experiments on the performance of the proportional response dynamics, and find that it outperforms several alternative solution methods.

## 5.6 Computing Core Allocations for Separable Piecewise-Linear Concave Utilities

We have set up the capped setting with the caps interpreted as an exogenous constraint. An alternative interpretation is as a capped utility function $u_i(x) = \sum_{j \in M} v_{ij} \min(x_j, \text{cap}_j)$. This view suggests a variety of generalizations: for example, we might want to allow different agents to specify different caps. We can generalize further to separable piecewise-linear concave utilities (SPLC). These are utility functions that can be written as a sum over goods (separable), with the term corresponding to a good being a (non-decreasing) piecewise-linear concave function of $x_j$. See Figure 3 for an example.

This class of utility functions is well-studied for private goods, both for Fisher markets and Arrow-Debreu exchange markets. For these markets, just as for linear utilities, equilibrium exists and is rational under mild conditions; however computing an equilibrium becomes PPAD-complete [Chen and Teng, 2009, Deligkas et al., 2024, Vazirani and Yannakakis, 2011]. A complementary pivot algorithm for computing an equilibrium has been proposed [Garg et al., 2015]. This algorithm is based on linear complementarity [Eaves, 1971, 1976], which interestingly can also be used to show existence of Lindahl equilibria [Munagala et al., 2022b, Appendix A].

We leave the problem of computing Lindahl equilibria for SPLC utilities open, but we show how our result for the capped setting can be used to at least compute an allocation in the core (up to any desired approximation factor). We do this by reducing an SPLC instance to a capped instance (with each piece of the piecewise-linear utilities becoming its own separate good), and show that a Lindahl equilibrium for this instance is core-stable with respect to the SPLC utilities.<fnref n="8" />

We begin with formal definitions. A function $f: [0, B] \to \mathbb{R}_{\ge 0}$ with $f(0) = 0$ is piecewise-linear concave if it can be decomposed into a finite number of linear segments, specified by their lengths $\ell^1, \dots, \ell^k$ (with $\ell^1 + \dots + \ell^k = B$) and slopes $s^1, \dots, s^k$ with $s^1 \ge \dots \ge s^k \ge 0$. Explicitly, for each $i \in [k]$, writing $a^i = \ell^1 + \dots + \ell^{i-1}$ for the left endpoint of the $i$th segment, we have $f(a^i + x) = f(a^i) + s^i x$ for $x \in [0, \ell^i]$. Figure 3 shows an example. A utility function $u_i$ is called separable piecewise-linear concave (SPLC) if there exist piecewise-linear concave functions $f_{ij}$ for all $j \in M$ such that $u_i(x) = \sum_{j \in M} f_{ij}(x_j)$ for all allocations $x$. Note that by subdividing segments if necessary, we may assume that for each project $j$, all agents $i$ agree on the total number $k_j$ of segments in $f_{ij}$ as well as their lengths. At the same time, we can choose this common subdivision in a minimal way, so that from one segment to the next, there is always at least one agent whose

<footnote n="8">⁸However, it is not clear that it is also a Lindahl equilibrium with respect to SPLC utilities, since we assign different prices to different segments of a public good, while Lindahl equilibrium requires a single set of individualized prices for each good.</footnote>
slope strictly decreases. Let us write $s_{ij}^t$ for the slope of the $t$th segment of $f_{ij}$, and let us write $\ell_j^t$ for the length of the $t$th segment for project $j$.

Any instance of the public goods problem with SPLC utility functions can be translated into an instance with linear utility functions and with caps, using the following construction.

**DEFINITION 7 (SPLC INSTANCES).** Suppose we are given an SPLC instance $I$ specified by the slopes $(s_{ij}^t)_{i \in N, j \in M, t \in [k_j]}$ and lengths $(\ell_j^t)_{j \in M, t \in [k_j]}$ of the segments. We construct a public goods instance $I'$ with linear utility functions on the same set of agents $N$ and with a new set of projects given by the disjoint union $M' = \cup_{j \in M} \{j^1, \dots, j^{k_j}\}$, with $\text{cap}_{jt} = \ell_j^t$. The project $j^t$ will describe how much of project $j$ will be funded in the area of its $t$th segment. Finally, we take valuations $v_{ij^t} = s_{ij}^t$.

Let us say that an SPLC instance is *well-behaved* if the derived instance is cap-sufficient in the sense of **Definition 3**. This is guaranteed to be the case, for example, if for every agent $i$, the total length of segments with positive slope across all projects is at least $B$. Similar sufficient conditions are used for private goods equilibria [e.g., Vazirani and Yannakakis, 2011, Section 2].

**PROPOSITION 3 (REDUCTION FROM SPLC TO CAPS).** Let $I$ be a well-behaved instance of the public goods problem with SPLC utilities. Then any zero-respecting Lindahl equilibrium for the instance $I'$ as constructed in **Definition 7** can be transformed into a core allocation for the SPLC instance $I$.

**PROOF.** Suppose that $x'$ is a zero-respecting Lindahl equilibrium allocation for $I'$. By **Corollary 1**, $x'$ is Pareto-optimal. Note that we always have $s_{ij}^t \le s_{ij}^{t-1}$ by concavity, and for at least one agent the inequality is strict (by minimality of the chosen common subdivision). Thus, Pareto-optimality implies that if $x'_{jt} > 0$ then $x'_{jt-1} = \text{cap}_{jt-1} = \ell_j^{t-1}$. This allows us to define an allocation $x$ for the instance $I$ by setting $x_j = \sum_{t=1}^{k_j} x'_{jt}$. We now argue that $x$ is in the core.

Suppose not, and there is some blocking coalition $S \subseteq N$ and objection $z = (z_j)_{j \in M}$ such that $\sum_{j \in M} z_j \le \sum_{i \in S} B_i$ and for all $i \in S$, we have $u_i(z) \ge u_i(x)$, with strict inequality for at least one $i \in S$. We construct a core objection $z'$ for $x'$, contradicting its core stability (**Proposition 2**). For each $j \in M$, let $t$ be chosen minimal such that $\ell_j^1 + \cdots + \ell_j^{t-1} \le z_j < \ell_j^1 + \cdots + \ell_j^t$. Then set $z'_{jr} = \text{cap}_{jr} = \ell_j^r$ for $r = 1, \dots, t-1$ and $z'_{jt} = z_j - (\ell_j^1 + \cdots + \ell_j^{t-1})$, as well as $z'_{jr} = 0$ for $r = t+1, \dots, k_j$. Then it is easy to see that $u'_i(z') = u_i(z)$ for all $i$, and similarly $u'_i(x') = u_i(x)$ for all $i$, and thus $z'$ is a core deviation to $x'$, a contradiction. $\square$

Thus, by (approximately) solving our convex program on the derived instance $I'$, we can find an (approximate) core allocation for the SPLC instance $I$.

# 6 Conclusion

We have developed a new class of convex programs that can be used to efficiently compute Lindahl equilibria both in the uncapped and the capped setting. These new programs open up many opportunities for future research.

In the uncapped setting, our new program might lead to new proofs of known results for the well-studied maximum Nash welfare rule. This might include the result about participation incentives of Brandl et al. [2022] or the axiomatic characterization of Guerdjikova and Nehring [2014]. Perhaps our program could also shed light on the other uses of the Eisenberg-Gale program across statistics, information theory, and medical imaging, as discussed in **Section 1.2**. For the capped setting, our computability result has implications for the discrete public goods model, because it allows the efficient implementation of the 9.27-approximation to the core obtained by Munagala et al. [2022b], rather than having to rely on their 67.37-approximation. Munagala et al. [2022b] used Lindahl equilibrium as a black box to obtain their approximation result; reasoning about the structure of our convex program might lead to even better bounds.
Since our focus has been on computational questions, we have not considered strategic aspects. Lindahl equilibrium is well-known to have high informational requirements, and in particular we need to know the truthful valuations of the agents to compute it. Interpreted as a decision rule [Gul and Pesendorfer, 2025], Lindahl equilibrium is not strategyproof and can be manipulated both in a free-riding sense [Brandl et al., 2021, Section 5.3], and in some paradoxical ways [Aziz et al., 2020, Theorem 3(ii)], even in the uncapped setting. Manipulability is unavoidable if one desires a Pareto-efficient and core-stable solution, both in the uncapped setting [Brandl et al., 2021, Theorem 2 and Theorem 3] and in the capped setting [Bei et al., 2024, Theorem 6.2]. These impossibilities apply even for approval (0/1) preferences. For more general linear utilities, strategyproofness is only attainable by dictatorial-type rules [Hylland, 1980], even in the uncapped setting.

We leave several interesting technical questions open. Is the optimum of our program unique in utilities? This is known to be true for the uncapped setting, by strict convexity (in utilities) of the Eisenberg-Gale program. Can we develop first-order methods for the capped settings, or derive a natural dynamics converging to an equilibrium? Applying mirror descent to our program does not appear to lead to a nice closed-form update like in the uncapped setting. Are there versions of our convex program that work for non-linear utilities? Finally, can the cap constraint be generalized? For example, one could apply cap constraints on the total spending of sets of public goods. This would allow us to model multi-issue and multi-round decision making settings [see, e.g., Banerjee et al., 2023, Section 5]. It would also allow us to embed private goods in the model [as in Conitzer et al., 2017], and potentially connect the notions of Fisher market equilibrium and Lindahl equilibrium.

## Acknowledgments

We thank the anonymous reviewers at EC 2025 for useful feedback. We thank Matthias Greger for suggesting the perturbation strategy used in Theorem 9. Christian Kroer was supported by the Office of Naval Research awards N00014-22-1-2530 and N00014-23-1-2374, and the National Science Foundation awards IIS-2147361 and IIS-2238960. Dominik Peters was supported by the French government under management of Agence Nationale de la Recherche as part of the “Investissements d'avenir” program, reference ANR-19-P3IA-0001 (PRAIRIE 3IA Institute) as well as the project ANR-22-CE26-0019 (CITIZENS).

## References

* Stéphane Airaiau, Haris Aziz, Ioannis Caragiannis, Justin Kruger, Jérôme Lang, and Dominik Peters. 2023. Portioning using ordinal preferences: Fairness and efficiency. *Artificial Intelligence* 314 (2023), 103809. doi:10.1016/j.artint.2022.103809 [→ p. 3, 6, 16]

* Haris Aziz, Anna Bogomolnaia, and Hervé Moulin. 2020. Fair mixing: The case of dichotomous preferences. *ACM Transactions on Economics and Computation (TEAC)* 8, 4, Article 18 (2020), 27 pages. doi:10.1145/3417738 [→ p. 3, 6, 12, 34]

* Haris Aziz, Markus Brill, Vincent Conitzer, Edith Elkind, Rupert Freeman, and Toby Walsh. 2017. Justified Representation in approval-based committee voting. *Social Choice and Welfare* 48, 2 (2017), 461–485. doi:10.1007/s00355-016-1019-3 [→ p. 6, 24]

* Haris Aziz, Xinhang Lu, Mashbat Suzuki, Jeremy Vollen, and Toby Walsh. 2023a. Best-of-both-worlds fairness in committee voting. In *Proceedings of the 19th International Conference on Web and Internet Economics (WINE)*. 676. Full version arXiv:2303.03642. [→ p. 3]

* Haris Aziz, Evi Micha, and Nisarg Shah. 2023b. Group fairness in peer review. In *Advances in Neural Information Processing Systems*, Vol. 36. 64885–64895. https://proceedings.neurips.cc/paper_files/paper/2023/file/ccba10dd4e80e7276054222bb95d467c-Paper-Conference.pdf [→ p. 7]

* Haris Aziz and Nisarg Shah. 2021. Participatory budgeting: Models and approaches. In *Pathways Between Social Science and Computational Social Science: Theories, Methods, and Interpretations*, Tamás Rudas and Gábor Péli (Eds.). Springer, 215–236. doi:10.1007/978-3-030-54936-7 10 [→ p. 3, 6]

* Siddhartha Banerjee, Vasilis Gkatzelis, Safwan Hossain, Billy Jin, Evi Micha, and Nisarg Shah. 2023. Proportionally fair online allocation of public goods with predictions. In *Proceedings of the 32nd International Joint Conference on Artificial Intelligence (IJCAI)*. 20–28. doi:10.24963/ijcai.2023/3 [→ p. 22, 34]
Amir Beck. 2017. *First-Order Methods in Optimization*. Society for Industrial and Applied Mathematics (SIAM). doi:10.1137/1.9781611974997 [→ p. 12, 39]

Xiaohui Bei, Xinhang Lu, and Warut Suksompong. 2024. Truthful cake sharing. *Social Choice and Welfare* (2024), 1–35. doi:10.1007/s00355-023-01503-0 [→ p. 3, 6, 34]

Benjamin Birnbaum, Nikhil R. Devanur, and Lin Xiao. 2011. Distributed algorithms via gradient descent for Fisher markets. In *Proceedings of the 12th ACM Conference on Electronic Commerce (EC)*. 127–136. doi:10.1145/1993574.1993594 [→ p. 4, 14, 17, 30]

Anna Bogomolnaia, Hervé Moulin, and Richard Stong. 2005. Collective choice under dichotomous preferences. *Journal of Economic Theory* 122, 2 (2005), 165–184. doi:10.1016/j.jet.2004.05.005 [→ p. 3, 6]

Florian Brandl, Felix Brandt, Matthias Greger, Dominik Peters, Christian Stricker, and Warut Suksompong. 2022. Funding public projects: A case for the Nash product rule. *Journal of Mathematical Economics* 99 (2022), 102585. doi:10.1016/j.jmateco.2021.102585 [→ p. 3, 6, 7, 9, 19, 25, 33]

Florian Brandl, Felix Brandt, Dominik Peters, and Christian Stricker. 2021. Distribution rules under dichotomous preferences: two out of three ain't bad. In *Proceedings of the 22nd ACM Conference on Economics and Computation (EC)*. 158–179. doi:10.1145/3465456.3467653 [→ p. 3, 6, 34]

Felix Brandt, Matthias Greger, Erel Segal-Halevi, and Warut Suksompong. 2024. Coordinating charitable donations. arXiv:2305.10286 [econ.TH] [→ p. 3, 7]

Ioannis Caragiannis, David Kurokawa, Hervé Moulin, Ariel D. Procaccia, Nisarg Shah, and Junxing Wang. 2019. The unreasonable fairness of maximum Nash welfare. *ACM Transactions on Economics and Computation (TEAC)* 7, 3 (2019), 1–32. doi:10.1145/3355902 [→ p. 6, 22]

Ioannis Caragiannis, Evi Micha, and Nisarg Shah. 2024. Proportional fairness in non-centroid clustering. In *Advances in Neural Information Processing Systems*, Vol. 37. 19139–19166. https://proceedings.neurips.cc/paper_files/paper/2024/file/220cbc7435d6a56205c87d73d15d9eda-Paper-Conference.pdf [→ p. 7]

Ioannis Chatzigeorgiou. 2013. Bounds on the Lambert function and their application to the outage analysis of user cooperation. *IEEE Communications Letters* 17, 8 (2013), 1505–1508. doi:10.1109/LCOMM.2013.070113.130972 arXiv:1601.04895 [→ p. 43]

Bhaskar Ray Chaudhury, Linyi Li, Mintong Kang, Bo Li, and Ruta Mehta. 2022. Fairness in federated learning via core-stability. In *Advances in Neural Information Processing Systems*, Vol. 35. 5738–5750. https://proceedings.neurips.cc/paper_files/paper/2022/file/25e92e33ac8c35fd49f394c37f21b6da-Paper-Conference.pdf [→ p. 7]

Xingyu Chen, Brandon Fain, Liang Lyu, and Kamesh Munagala. 2019. Proportionally fair clustering. In *Proceedings of the 36th International Conference on Machine Learning (ICML)*. PMLR, 1032–1041. https://proceedings.mlr.press/v97/chen19d.html [→ p. 7]

Xi Chen and Shang-Hua Teng. 2009. Spending is not easier than trading: On the computational equivalence of Fisher and Arrow-Debreu equilibria. In *Proceedings of the 20th International Symposium on Algorithms and Computation (ISAAC)*. 647–656. doi:10.1007/978-3-642-10631-6_66 [→ p. 32]

Yu Cheng, Zhihao Jiang, Kamesh Munagala, and Kangning Wang. 2020. Group fairness in committee selection. *ACM Transactions on Economics and Computation (TEAC)* 8, 4, Article 23 (2020), 18 pages. doi:10.1145/3417750 [→ p. 4]

Richard Cole, Nikhil R. Devanur, Vasilis Gkatzelis, Kamal Jain, Tung Mai, Vijay V. Vazirani, and Sadra Yazdanbod. 2017. Convex program duality, Fisher markets, and Nash social welfare. In *Proceedings of the 2017 ACM Conference on Economics and Computation (EC)*. 459–460. doi:10.1145/3033274.3085109 [→ p. 13, 17]

Vincent Conitzer, Rupert Freeman, and Nisarg Shah. 2017. Fair public decision making. In *Proceedings of the 2017 ACM Conference on Economics and Computation (EC)*. 629–646. doi:10.1145/3033274.3085125 [→ p. 34]

Thomas Cover. 1984. An algorithm for maximizing expected log investment return. *IEEE Transactions on Information Theory* 30, 2 (1984), 369–373. doi:10.1109/TIT.1984.1056869 [→ p. 4, 6, 22]

Imre Csiszár. 1974. On the computation of rate-distortion functions (corresp.). *IEEE Transactions on Information Theory* 20, 1 (1974), 122–124. doi:10.1109/TIT.1974.1055146 [→ p. 6]

Imre Csiszár. 1984. Information geometry and alternating minimization procedures. *Statistics and Decisions* Supplemental Issue No. 1 (1984), 205–237. https://dominik-peters.de/archive/csiszar1984.pdf [→ p. 6]

Argyrios Deligkas, John Fearnley, Alexandros Hollender, and Themistoklis Melissourgos. 2024. Constant inapproximability for Fisher markets. In *Proceedings of the 25th ACM Conference on Economics and Computation (EC)*. 13–39. doi:10.1145/3670865.3673533 [→ p. 32]

Nikhil R. Devanur, Christos H. Papadimitriou, Amin Saberi, and Vijay V. Vazirani. 2008. Market equilibrium via a primal-dual algorithm for a convex program. *Journal of the ACM* (JACM) 55, 5 (2008), 1–18. doi:10.1145/1411509.1411512 [→ p. 16]

Anulekha Dhara and Joydeep Dutta. 2011. *Optimality Conditions in Convex Optimization: A Finite-Dimensional View*. CRC Press. doi:10.1201/b11156 [→ p. 44]

B. Curtis Eaves. 1971. On the basic theorem of complementarity. *Mathematical Programming* 1, 1 (1971), 68–75. doi:10.1007/BF01584073 [→ p. 32]
B. Curtis Eaves. 1976. A finite algorithm for the linear exchange model. *Journal of Mathematical Economics* 3, 2 (1976), 197-203. doi:10.1016/0304-4068(76)90028-8 [→ p. 32]

Soroush Ebadian, Anson Kahng, Dominik Peters, and Nisarg Shah. 2024. Optimized distortion and proportional fairness in voting. *ACM Transactions on Economics and Computation (TEAC)* 12, 1, Article 3 (2024), 39 pages. doi:10.1145/3640760 [→ p. 22, 23]

Soroush Ebadian and Evi Micha. 2025. Boosting sortition via proportional representation. In *Proceedings of 24th International Conference on Autonomous Agents and Multiagent Systems (AAMAS)*. 667-675. https://www.ifaamas.org/Proceedings/aamas2025/pdfs/p667.pdf [→ p. 7]

Edmund Eisenberg. 1961. Aggregation of utility functions. *Management Science* 7, 4 (1961), 337-350. doi:10.1287/mnsc.7.4.337 [→ p. 3, 15]

Edmund Eisenberg and David Gale. 1959. Consensus of subjective probabilities: The pari-mutuel method. *The Annals of Mathematical Statistics* 30, 1 (1959), 165-168. doi:10.1214/aoms/1177706369 [→ p. 3, 15]

Brandon Fain, Ashish Goel, and Kamesh Munagala. 2016. The core of the participatory budgeting problem. In *Proceedings of the 12th International Conference on Web and Internet Economics (WINE)*. 384-399. doi:10.1007/978-3-662-54110-4_27 [→ p. 3, 4, 5, 6, 7, 14, 15, 25]

Brandon Fain, Kamesh Munagala, and Nisarg Shah. 2018. Fair allocation of indivisible public goods. In *Proceedings of the 2018 ACM Conference on Economics and Computation (EC)*. 575-592. doi:10.1145/3219166.3219174 [→ p. 7, 24]

Piotr Faliszewski, Jarosław Flis, Dominik Peters, Grzegorz Pierczyński, Piotr Skowron, Dariusz Stolicki, Stanisław Szufa, and Nimrod Talmon. 2023. Participatory budgeting: Data, tools, and analysis. In *Proceedings of the 32nd International Joint Conference on Artificial Intelligence (IJCAI)*. 2667-2674. doi:10.24963/ijcai.2023/297 [→ p. 31]

Duncan K. Foley. 1970. Lindahl's solution and the core of an economy with public goods. *Econometrica* (1970), 66-72. doi:10.2307/1909241 [→ p. 3, 4, 6, 7, 9, 10, 11, 25]

Jugal Garg, Ruta Mehta, Milind Sohoni, and Vijay V. Vazirani. 2015. A complementary pivot algorithm for market equilibrium under separable, piecewise-linear concave utilities. *SIAM J. Comput.* 44, 6 (2015), 1820-1847. doi:10.1137/140971002 [→ p. 32]

Nikhil Garg, Ashish Goel, and Benjamin Plaut. 2021. Markets for public decision-making. *Social Choice and Welfare* 56, 4 (2021), 755-801. doi:10.1007/s00355-020-01298-4 [→ p. 25]

Hilary Greaves and Owen Cotton-Barratt. 2024. A bargaining-theoretic approach to moral uncertainty. *Journal of Moral Philosophy* 21, Issue 1-2 (2024), 127-169. doi:10.1163/17455243-20233810 [→ p. 7]

Ani Guerdjikova and Klaus Nehring. 2014. Weighing experts, weighing sources: The diversity value. (2014). https://dominik-peters.de/archive/guerdjikova2014.pdf Working Paper. [→ p. 3, 6, 14, 33]

Faruk Gul and Wolfgang Pesendorfer. 2025. Pseudo Lindahl equilibrium as a collective choice rule. *The Review of Economic Studies* (2025), rdaf043. doi:10.1093/restud/rdaf043 arXiv:2008.09932 [econ.TH] [→ p. 6, 34]

Jean-Baptiste Hiriart-Urruty. 1982. *ε*-subdifferential calculus. In *Convex Analysis and Optimization*, Jean-Pierre Aubin and Richard B. Vinter (Eds.). Research Notes in Mathematics, Vol. 57. Pitman, 43-92. https://dominik-peters.de/archive/hiriarturruty1982.pdf [→ p. 44]

Jean-Baptiste Hiriart-Urruty and Claude Lemaréchal. 2013. *Convex Analysis and Minimization Algorithms I: Fundamentals*. Grundlehren der mathematischen Wissenschaften, Vol. 305. Springer. doi:10.1007/978-3-662-02796-7 [→ p. 41]

Aanund Hylland. 1980. Strategyproofness of voting procedures with lotteries as outcomes and infinite sets of strategies. (1980). https://dominik-peters.de/archive/hylland1980.pdf Unpublished. [→ p. 34]

Zhihao Jiang, Kamesh Munagala, and Kangning Wang. 2020. Approximately stable committee selection. In *Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC)*. 463-472. doi:10.1145/3357713.3384238 [→ p. 4]

Mamoru Kaneko. 1977. The ratio equilibrium and a voting game in a public goods economy. *Journal of Economic Theory* 16, 2 (1977), 123-136. doi:10.1016/0022-0531(77)90001-1 [→ p. 6, 9]

Leon Kellerhals and Jannik Peters. 2024. Proportional fairness in clustering: A social choice perspective. In *Advances in Neural Information Processing Systems*, Vol. 37. 111299-111317. https://proceedings.neurips.cc/paper_files/paper/2024/file/c981fd12b1d5703f19bd8289da9fc996-Paper-Conference.pdf [→ p. 7]

Frank P. Kelly, Aman K. Maulloo, and David K. H. Tan. 1998. Rate control for communication networks: Shadow prices, proportional fairness and stability. *Journal of the Operational Research Society* 49, 3 (1998), 237-252. doi:10.1057/palgrave.jors.2600523 [→ p. 22]

Hidetoshi Komiya. 1988. Elementary proof for Sion's minimax theorem. *Kodai Mathematical Journal* 11, 1 (1988), 5-7. doi:10.2996/kmj/1138038812 [→ p. 39]

Martin Lackner and Piotr Skowron. 2023. *Multi-Winner Voting with Approval Preferences*. Springer. doi:10.1007/978-3-031-09016-5 [→ p. 6]

Yen-Huan Li, Carlos A. Riofrio, and Volkan Cevher. 2018. A general convergence result for mirror descent with Armijo line search. arXiv:1805.12232 [math.OC] [→ p. 4]
Erik Lindahl. 1919. Just taxation—a positive solution. Translated from German (Die Gerechtigkeit der Besteuerung, Lund 1919, Part I, Chap. 4, pp. 85–98: Positive Lösung) by Elizabeth Henderson. In *Classics in the Theory of Public Finance*, Richard A. Musgrave and Alan T. Peacock (Eds.). Palgrave Macmillan (1958), 168–176. doi:10.1007/978-1-349-23426-4_11 [→ p. 3, 6]

Juan Carlos Martinez Mori and Alejandro Toriello. 2025. Cooperation and the design of public goods. In *Proceedings of the 26th ACM Conference on Economics and Computation (EC)*. 511. doi:10.1145/3736252.3742582 arXiv:2506.05251 [cs.GT] [→ p. 24]

Andreu Mas-Colell and Joaquim Silvestre. 1989. Cost share equilibria: A Lindahlian approach. *Journal of Economic Theory* 47, 2 (1989), 239–256. doi:10.1016/0022-0531(89)90019-7 [→ p. 6, 9]

Marcin Michorzewski, Dominik Peters, and Piotr Skowron. 2020. Price of fairness in budget division and probabilistic social choice. In *Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI)*. 2184–2191. doi:10.1609/aaai.v34i02.5594 [→ p. 6]

James C. Moore. 2006. *General Equilibrium and Welfare Economics: An Introduction*. Springer. doi:10.1007/978-3-540-32232-8 [→ p. 9]

Hervé Moulin. 2004. *Fair Division and Collective Welfare*. MIT Press. doi:10.7551/mitpress/2954.001.0001 [→ p. 3]

Kamesh Munagala, Yiheng Shen, and Kangning Wang. 2022a. Auditing for core stability in participatory budgeting. In *Proceedings of the 18th International Conference on Web and Internet Economics (WINE)*. 292–310. doi:10.1007/978-3-031-22832-2_17 [→ p. 6]

Kamesh Munagala, Yiheng Shen, Kangning Wang, and Zhiyi Wang. 2022b. Approximate core for committee selection via multilinear extension and market clearing. In *Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)*. 2229–2252. doi:10.1137/1.9781611977073.89 [→ p. 4, 10, 25, 32, 33]

John F. Nash. 1950. The bargaining problem. *Econometrica* 18, 2 (1950), 155–162. doi:10.2307/1907266 [→ p. 3]

Angelia Nedić and Asuman Ozdaglar. 2009. Approximate primal solutions and rate analysis for dual subgradient methods. *SIAM Journal on Optimization* 19, 4 (2009), 1757–1780. doi:10.1137/070708111 [→ p. 41]

Brendan O'Donoghue, Eric Chu, Neal Parikh, and Stephen Boyd. 2016. Conic optimization via operator splitting and homogeneous self-dual embedding. *Journal of Optimization Theory and Applications* 169, 3 (June 2016), 1042–1068. http://stanford.edu/~boyd/papers/scs.html [→ p. 31]

Dominik Peters. 2019. Economic design for effective altruism. *The Future of Economic Design: The Continuing Development of a Field as Envisioned by Its Researchers* (2019), 381–388. doi:10.1007/978-3-030-18050-8_53 [→ p. 7]

Dominik Peters. 2025. The core of approval-based committee elections with few seats. In *Proceedings of the 34th International Joint Conference on Artificial Intelligence (IJCAI)*. arXiv:2501.18304 [cs.GT] [→ p. 6, 24]

Dominik Peters, Grzegorz Pierczyński, Nisarg Shah, and Piotr Skowron. 2021b. Market-based explanations of collective decisions. In *Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI)*. 5656–5663. doi:10.1609/aaai.v35i6.16710 [→ p. 6]

Dominik Peters, Grzegorz Pierczyński, and Piotr Skowron. 2021a. Proportional participatory budgeting with additive utilities. In *Advances in Neural Information Processing Systems*, Vol. 34. 12726–12737. https://proceedings.neurips.cc/paper_files/paper/2021/file/69f8ea31de0c05050b2ae571fbab1f95-Paper.pdf [→ p. 6]

Dominik Peters and Piotr Skowron. 2020. Proportionality and the limits of welfarism. In *Proceedings of the 21st ACM Conference on Economics and Computation (EC)*. 793–794. Full version arXiv:1911.11747. [→ p. 24]

Grzegorz Pierczyński and Piotr Skowron. 2022. Core-stable committees under restricted domains. In *Proceedings of the 18th International Conference on Web and Internet Economics (WINE)*. 311–329. doi:10.1007/978-3-031-22832-2_18 [→ p. 6]

Simon Rey and Jan Maly. 2023. The (computational) social choice take on indivisible participatory budgeting. arXiv:2303.00621 [cs.GT] https://arxiv.org/abs/2303.00621 [→ p. 3, 6]

Ralph Tyrell Rockafellar. 1970. *Convex Analysis*. Princeton Mathematical Series, Vol. 28. Princeton University Press. doi:10.1515/9781400873173 [→ p. 13]

Andrzej Ruszczynski. 2011. *Nonlinear Optimization*. Princeton University Press. doi:10.2307/j.ctvcm4hcj [→ p. 12]

Paul A. Samuelson. 1954. The pure theory of public expenditure. *The Review of Economics and Statistics* 36, 4 (1954), 387–389. doi:10.2307/1925895 [→ p. 3]

Vadim I. Shmyrev. 1983. On an approach to the determination of equilibrium in elementary exchange models. In *Doklady Akademii Nauk SSSR*, Vol. 268:5, 1062–1066. https://www.mathnet.ru/eng/dan10141 (In Russian). [→ p. 4, 16]

Vadim I. Shmyrev. 2009. An algorithm for finding equilibrium in the linear exchange model with fixed budgets. *Journal of Applied and Industrial Mathematics* 3, 4 (2009), 505. doi:10.1134/S1990478909040097 [→ p. 4, 16, 17]

Jean-Jacques Strodiot, V. Hien Nguyen, and Norbert Heukemes. 1983. ε-optimal solutions in nondifferentiable convex programming and some related questions. *Mathematical Programming* 25 (1983), 307–328. doi:10.1007/BF02594782 [→ p. 40]

Mashbat Suzuki and Jeremy Vollen. 2024. Maximum flow is fair: A network flow approach to committee voting. In *Proceedings of the 25th ACM Conference on Economics and Computation (EC)*. 964–983. doi:10.1145/3670865.3673603 [→ p. 3, 4, 6, 25]
Hirofumi Uzawa. 1958. Iterative methods for concave programming. In *Studies in Linear and Non-Linear Programming*, K. Arrow, L. Hurwicz, and H. Uzawa (Eds.). Stanford University Press, 154–165. doi:10.1017/CBO9780511664496.011 (reprint) https://dominik-peters.de/archive/uzawa1958.pdf. [→ p. 41]

Anne van den Nouweland. 2015. Lindahl and equilibrium. In *Individual and Collective Choice and Social Welfare: Essays in Honor of Nick Baigent*, Constanze Binder, Giulio Codognato, Miriam Teschl, and Yongsheng Xu (Eds.). Springer, 335–362. doi:10.1007/978-3-662-46439-7_18 [→ p. 6, 9]

Yehuda Vardi and D. Lee. 1993. From image blurring to optimal investments: Maximum likelihood solutions for positive linear inverse problems. *Journal of the Royal Statistical Society Series B: Statistical Methodology* 55, 3 (1993), 569–598. doi:10.1111/j.2517-6161.1993.tb01925.x [→ p. 6]

Yehuda Vardi, Larry A. Shepp, and Linda Kaufman. 1985. A statistical model for positron emission tomography. *Journal of the American statistical Association* 80, 389 (1985), 8–20. doi:10.1080/01621459.1985.10477119 [→ p. 6]

Vijay V. Vazirani. 2012. The notion of a rational convex program, and an algorithm for the Arrow-Debreu Nash bargaining game. *Journal of the ACM (JACM)* 59, 2 (2012), 1–36. doi:10.1145/2160158.2160160 [→ p. 16]

Vijay V. Vazirani and Mihalis Yannakakis. 2011. Market equilibrium under separable, piecewise-linear, concave utilities. *Journal of the ACM (JACM)* 58, 3 (2011), 1–25. doi:10.1145/1970392.1970394 [→ p. 32, 33]

Nisheeth K. Vishnoi. 2021. *Algorithms for Convex Optimization*. Cambridge University Press. doi:10.1017/9781108699211 https://convex-optimization.github.io/. [→ p. 24, 31, 50]

Fang Wu and Li Zhang. 2007. Proportional response dynamics leads to market equilibrium. In *Proceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC)*. 354–363. doi:10.1145/1250790.1250844 [→ p. 4, 19]

Li Zhang. 2011. Proportional response dynamics in the Fisher market. *Theoretical Computer Science* 412, 24 (2011), 2691–2698. doi:10.1016/j.tcs.2010.06.021 [→ p. 4, 19]

Renbo Zhao. 2023. Convergence rate analysis of the multiplicative gradient method for PET-type problems. *Operations Research Letters* 51, 1 (2023), 26–32. doi:10.1016/j.orl.2022.11.010 [→ p. 4, 6, 22]

Renbo Zhao and Robert M. Freund. 2023. Analysis of the Frank-Wolfe method for convex composite optimization involving a logarithmically-homogeneous barrier. *Mathematical Programming* 199, 1 (2023), 123–163. doi:10.1007/s10107-022-01820-9 [→ p. 32]
A Convex Conjugates and Subdifferentials of Some Useful Functions

LEMMA 3. Consider some $q \in \mathbb{R}^{n \times m}$ and let $q_j$ be the j-th column of $q$. For $j \in M$, let $g_j(q_j) = \sum_{i \in N} e^{q_{ij}}$ and let $g(q) = B \cdot \max_{j \in M} g_j(q_j)$. Then the convex conjugate of $g$ satisfies

$$g^*(\beta) = \sum_{ij} \beta_{ij} \log \frac{\beta_{ij}}{\bar{x}_j(\beta)} - \beta_{ij} \quad \text{for all } \beta \ge 0,$$

$$\text{where } \tilde{x}_j(\beta) = B \cdot \left( \frac{\sum_i \beta_{ij}}{\sum_{ij'} \beta_{ij'}} \right).$$

PROOF. We compute the convex conjugate of $g$ using standard formulas for the conjugate of a separable function, rescalings of a function, and the exponential function [see, e.g., Beck, 2017, Sections 4.3 and 4.4]. We also use Sion's minimax theorem [Komiya, 1988] which states that if $X$ is convex, $Y$ is convex and compact, and $f$ is a real-valued function on $X \times Y$ that is concave in its first argument and convex in its second argument, then $\sup_{X \in X} \min_{Y \in Y} f(x, y) = \min_{Y \in Y} \sup_{X \in X} f(x, y)$. Finally, given $\beta = (\beta_{ij})_{i \in N, j \in M}$, we write $\beta_j = (\beta_{i,j})_{i \in N}$.

Putting all of this together, we derive that

$$g^*(\beta) = \sup_q \langle \beta, q \rangle - g(q) = \sup_q \min_{j \in M} \langle \beta, q \rangle - B \cdot g_j(q_j) \quad \text{(definition of $g$)}$$

$$= \sup_q \min_{x \in B \cdot \Delta^m} \langle \beta, q \rangle - \sum_{j \in M} x_j \cdot g_j(q_j) \quad \text{(minimum attained at a vertex)}$$

$$= \min_q \sup_{x \in B \cdot \Delta^m} \langle \beta, q \rangle - \sum_{j \in M} x_j \cdot g_j(q_j), \quad \text{(Sion's minimax theorem)}$$

$$= \min_{x \in B \cdot \Delta^m} \sum_{j \in M} \sup_{q_j} \langle \beta_j, q_j \rangle - x_j \cdot g_j(q_j), \quad \text{(conjugate of a separable function)}$$

$$= \min_{x \in B \cdot \Delta^m} \sum_{j \in M} x_j \cdot g_j^*(\beta_j/x_j) \quad ((\alpha f)^*(y) = \alpha f^*(y/\alpha))$$

$$= \min_{x \in B \cdot \Delta^m} \sum_{j \in M} x_j \cdot \left( \sum_{i \in N} \frac{\beta_{ij}}{x_j} \log \frac{\beta_{ij}}{x_j} - \frac{\beta_{ij}}{x_j} \right) \quad \text{(exp*($y$) = $y \log y - y$)}$$

$$= \min_{x \in B \cdot \Delta^m} \sum_{ij} \beta_{ij} \log \frac{\beta_{ij}}{x_j} - \beta_{ij} = \sum_{ij} \beta_{ij} \log \frac{\beta_{ij}}{\bar{x}_j(\beta)} - \beta_{ij}, \quad \text{(Lemma 2(b))}$$

as required. $\square$

In order to prove Lemma 7 we will need the following lemma regarding the convex conjugate of $h$.

LEMMA A.1. Let $h: \mathbb{R}^n_{\ge 0} \to \mathbb{R}$ be the function given by $h(x) = \sum_i x_i \log \frac{x_i}{\sum_k x_k}$ for $x \ne 0$ and $h(0) = 0$ by the convention that $0 \log 0 = 0$. Its convex conjugate $h^*$ is the indicator of the set $\{y: \sum_i e^{y_i} \le 1\}$, so $h^*(y) = 0$ if $\sum_i e^{y_i} \le 1$ and $h^*(y) = +\infty$ otherwise.

PROOF. Let $\varphi(p) = \sum_i p_i \log p_i$ be the negative entropy function, and recall that the convex conjugate of the negative entropy function is the log-sum-exp function $\varphi^*(y) = \log \sum_i e^{y_i}$ [see, e.g., Beck, 2017, Section 4.4.8]. Note that $h(x) = \|x\|_1 \varphi(x/\|x\|_1)$. Thus, writing $S = \|x\|_1$, we have

$$h^*(y) = \sup_{x \in \mathbb{R}_{\ge 0}^n} \langle y, x \rangle - h(x) \quad \text{(definition of the convex conjugate)}$$
$$
\begin{align*}
&= \sup_{S \ge 0} \sup_{p \in \Delta^n} \langle y, Sp \rangle - S\varphi(p) \\
&= \sup_{S \ge 0} \sup_{p \in \Delta^n} \left( \langle y, p \rangle - \varphi(p) \right) \\
&= \sup_{S \ge 0} S \cdot \varphi^*(y) \tag*{\text{(definition of the convex conjugate)}} \\
&= \sup_{S \ge 0} S \log \sum_i e^{y_i}.
\end{align*}
$$

Thus, $h^*(y) = 0$ if $\sum_i e^{y_i} \le 1$ (with the supremum attained at $S = 0$) and $h^*(y) = +\infty$ otherwise (letting $S \to +\infty$). $\square$

LEMMA 7 (SUBDIFFERENTIAL OF OBJECTIVE FUNCTION). Let $f$ be the negative of the objective function of Program 16, and let $b = (b_{ij})_{i \in N, j \in M_i}$ be a feasible point. If there is some $i \in N$ and $j \in M_i$ such that $b_{ij} = 0$ but $x_j(b) > 0$, then $\partial f(b) = \emptyset$. Otherwise, for all vectors $g = (g_{ij})_{i \in N, j \in M_i}$, we have

$$
g \in \partial f(b) \iff \begin{cases} \text{for all } j \in M \text{ s.t. } x_j(b) > 0, \text{ and all } i \in N_j, & g_{ij} = -\log v_{ij} + \log \frac{b_{ij}}{x_j(b)}, \\ \text{for all } j \in M \text{ s.t. } x_j(b) = 0, & \sum_{i \in N_j} e^{g_{ij} + \log v_{ij}} \le 1. \end{cases}
$$

PROOF. We can write $f(b) = - \sum_{i \in N, j \in M_i} b_{ij} \log v_{ij} + \sum_{j \in M} h(b_j)$ where $b_j$ is the vector $(b_{ij})_{i \in N_j}$ and $h$ is the function defined as $h(x) = \sum_i x_i \log \frac{x_i}{\sum_k x_k}$ when all $x_i$ are non-negative, $h(0) = 0$ by the convention that $0 \log \frac{0}{0} = 0$, and $+\infty$ otherwise.

We begin by computing the subdifferential of $h$, using that its convex conjugate $h^*(y)$ is $h^*(y) = 0$ if $\sum_i e^{y_i} \le 1$ and $h^*(y) = +\infty$ otherwise, as shown in Lemma A.1. Hence

$$
\partial h(x) = \{g : h(x) + h^*(g) \le \langle x, g \rangle\} = \{g : \sum_i e^{g_i} \le 1 \text{ and } h(x) \le \langle x, g \rangle\}.
$$

For $x = 0$, we have $h(x) \le \langle x, g \rangle$ for all $g$ since $h(0) = 0$. Hence $\partial h(0) = \{g : \sum_i e^{g_i} \le 1\}$. For $x \in \mathbb{R}^n_{\ge 0}$ such that $x_i > 0$ for all $i$, note that $h$ is differentiable, so $\partial h(x) = \{(\log \frac{x_i}{\sum_k x_k})_{i=1}^n\}$. For $x \in \mathbb{R}^n_{\ge 0}$ such that $x \ne 0$ but $x_i = 0$ for some $i$, we have $\partial h(x) = \emptyset$ since if $g \in \partial h(x)$, then $g_j = \log \frac{x_i}{\sum_k x_k}$ for every $j$ with $x_j > 0$ (like in the fully interior case), which gives that $\sum_{j:x_j>0} e^{g_i} = 1$ which would force $g_i = -\infty$ in order to guarantee that $\sum_i e^{g_i} \le 1$.

From this characterization of the subdifferential of $h$, the subdifferential of $f$ can be determined immediately because the subdifferential of a sum of convex functions is equal to the sum of the subdifferentials and noting that $\partial(-b_{ij} \log v_{ij}) = \{-\log v_{ij}\}$. $\square$

**B Approximately Optimal Solutions**

In this section, we will study properties of solutions that are $\varepsilon$-optimal. Given the problem of minimizing a function $f$ over some feasible set, we say that a feasible solution $x$ is $\varepsilon$-optimal if $f(x) \le f(y) + \varepsilon$ for all feasible solutions $y$.

Our main tool for this analysis is a version of the KKT theorem for *approximately* optimal solutions. It is stated in terms of the $\varepsilon$-subdifferential of a convex function, which is defined as

$$
\begin{align*}
\partial_{\varepsilon} f(x) &= \{g \in \mathbb{R}^n : f(y) \ge f(x) + \langle g, y-x \rangle - \varepsilon \text{ for all } y \in \mathbb{R}^n\} \\
&= \{g \in \mathbb{R}^n : f(x) + f^*(g) \le \langle g, x \rangle + \varepsilon\}
\end{align*}
$$

where the second line gives a standard equivalent definition using the convex conjugate $f^*$ of $f$.

THEOREM 10 (STRODIOT ET AL., 1983, THM 2.4 AND THM 3.2). Let $x^*$ be an $\varepsilon$-optimal solution to the program

$$
\text{minimize } f(x) \text{ subject to } h_i(x) \le 0 \text{ for } i = 1, \dots, m
$$
PROOF. Write $x = x(b)$ for the allocation induced by $b$, and consider the following optimization problem:

$$ \begin{array}{ll} \min_{b \ge 0} & f^{\dagger}(b) := - \sum_{i \in N, j \in M_i} b_{ij} (\log v_{ij} - \log (b_{ij} / x_j)) \\ \text{s.t.} & \sum_{j \in M} b_{ij} = B_i, \forall i \in N \end{array} \tag{22} $$

This is the same optimization problem as Program 14, except that we replaced the term $x_j(b)$ by the constant $x_j$. Clearly, $b$ is a feasible solution for Program 22 and $f(b) = f^{\dagger}(b)$. Let $b^*$ be an optimal solution to Program 22. Then $f^{\dagger}(b^*) \le f^{\dagger}(b)$. Noting that Program 22 decomposes into a separate optimization problem for each $i \in N$, from Lemma 2(a), we can write the optimal solution $b^*$ explicitly as

$$ b_{ij}^* = B_i \frac{v_{ij} x_j}{\langle v_i, x \rangle}. \tag{23} $$

Hence

$$ \begin{aligned} f^{\dagger}(b^*) &= - \sum_{i \in N, j \in M_i} B_i \frac{v_{ij} x_j}{\langle v_i, x \rangle} \log \left( B_i \frac{v_{ij} x_j}{\langle v_i, x \rangle} \right) \\ &= - \sum_{i \in N} B_i \log \left( \frac{\langle v_i, x \rangle}{B_i} \right) \sum_{j \in M_i} \frac{v_{ij} x_j}{\langle v_i, x \rangle} \\ &= - \sum_{i \in N} B_i \log \langle v_i, x \rangle + \sum_{i \in N} B_i \log B_i = \varphi(x) + \sum_{i \in N} B_i \log B_i. \end{aligned} $$

Hence we have shown that $f(b) = f^{\dagger}(b) \ge f^{\dagger}(b^*) = \varphi(x(b)) + \sum_{i \in N} B_i \log B_i$, as required.

Finally, if $b$ is an optimal solution to Program 14, then the KKT conditions of that program imply that $b$ satisfies the equations (23) (see Theorem 8), and thus $b^* = b$, so the claimed inequality holds with equality. $\square$

For the latter result, we now prove that any outcome that approximately maximizes Nash social welfare also approximates the proportional fairness criterion. We will do so via the $\varepsilon$-KKT conditions from Theorem 10. To apply these conditions, we will need the $\varepsilon$-subdifferential of the negative logarithm, since this function appears in the definition of Nash social welfare. We are not aware of a formula for this $\varepsilon$-subdifferential having appeared in the literature, so we derive it from scratch.

LEMMA B.2. For $0 \le \varepsilon < \frac{1}{2}$, the $\varepsilon$-subdifferential of the negative logarithm is

$$ \partial_{\varepsilon}(-\log x)(x) = \left[ \frac{1}{x} W_{-1}(-e^{-(\varepsilon+1)}), \frac{1}{x} W_{0}(-e^{-(\varepsilon+1)}) \right] \subseteq \left[ \frac{-1-2\sqrt{\varepsilon}}{x}, \frac{-1+\sqrt{2\varepsilon}}{x} \right], $$

where $W$ refers to the Lambert $W$ function.

PROOF. Let $0 \le \varepsilon < \frac{1}{2}$. We begin by considering the function $f(u) = u - \log u$ for $u > 0$, depicted below.

<figure><img src="image_5.png" /></figure>
Its derivatives are $f'(u) = 1 - \frac{1}{u}$ and $f''(u) = 1/u^2 > 0$. Thus, the function has its minimum at $u = 1$ with $f(1) = 1$, and is strictly decreasing on $(0, 1)$ and strictly increasing on $(1, +\infty)$. We will show that

$$f(u) \leq 1 + \varepsilon \iff u \in [-W_0(-e^{-(1+\varepsilon)}), -W_{-1}(-e^{-(1+\varepsilon)})], \quad (24)$$

where $W$ refers to the Lambert $W$ function (see Wikipedia). By continuity of $f$ and looking at its derivatives, the range of $u \in (0, +\infty)$ for which $f(u) \le 1 + \varepsilon$ is clearly an interval, whose endpoints are the solutions to the equation $f(u) = 1 + \varepsilon$. Note that

$$u - \log u = 1 + \varepsilon \Leftrightarrow \log u - u = -(1 + \varepsilon) \Leftrightarrow ue^{-u} = e^{-(1+\varepsilon)} \Leftrightarrow -ue^{-u} = -e^{-(1+\varepsilon)}. \quad (25)$$

Now, for given $z \in (-1/e, 0)$, the equation $we^w = z$ has two real solutions which are $W_{-1}(z)$ and $W_0(z)$ by definition of the Lambert $W$ function, with $W_{-1}(z) < -1 < W_0(z) < 0$. Thus, condition (25) is equivalent to

$$u \in \{-W_{-1}(-e^{-(1+\varepsilon)}), -W_0(-e^{-(1+\varepsilon)})\},$$

thereby establishing (24).

It is useful to also give a looser version of (24) that is phrased in terms of elementary functions. For this, we will use the following inequalities of the logarithm:

$$\log(1 - t) < -t - \frac{t^2}{2} \quad \text{for } t > 0, \quad (26)$$

$$\log(1 + y) < y - \frac{y^2}{4} \quad \text{for } y \in (0, \sqrt{2}). \quad (27)$$

These can be obtained from Taylor expansions or by showing that the functions $h(t) = \log(1 - t) - (-t - \frac{t^2}{2})$ and $k(y) = \log(1 + y) - (y - \frac{y^2}{4})$ are strictly negative on the relevant domain, by analyzing the monotonicity properties of those functions through their derivatives.

Now note that

$$f(1 - \sqrt{2\varepsilon}) = (1 - \sqrt{2\varepsilon}) - \log(1 - \sqrt{2\varepsilon}) \stackrel{(26)}{>} (1 - \sqrt{2\varepsilon}) + \sqrt{2\varepsilon} + \varepsilon = 1 + \varepsilon$$

and

$$f(1 + 2\sqrt{\varepsilon}) = 1 + 2\sqrt{\varepsilon} - \log(1 + 2\sqrt{\varepsilon}) \stackrel{(27)}{>} 1 + 2\sqrt{\varepsilon} - 2\sqrt{\varepsilon} + \varepsilon = 1 + \varepsilon,$$

where we could invoke (27) because $y = 2\sqrt{\varepsilon} < 2\sqrt{1/2} = \sqrt{2}$ since $\varepsilon < \frac{1}{2}$ by assumption.

From this, it follows that

$$f(u) \le 1 + \varepsilon \implies u \in [1 - \sqrt{2\varepsilon}, 1 + 2\sqrt{\varepsilon}]. \quad (28)$$

A similar lower bound is obtained by Chatzigeorgiou [2013, Theorem 1].

We now turn to determining the $\varepsilon$-subdifferential of $g(x) = -\log x$. Recall that $g^*(y) = -1 - \log(-y)$. The $\varepsilon$-subdifferential can be written using the convex conjugate: for all $x > 0$,

$$\partial_{\varepsilon} g(x) = \{y : g(x) + g^*(y) \le xy + \varepsilon\} \quad (\text{definition})$$

$$= \{y : -\log(x) - 1 - \log(-y) \le xy + \varepsilon\}$$

$$= \{y : -xy - \log(-xy) \le 1 + \varepsilon\}$$

$$= \{y : -xy \in [-W_0(-e^{-(1+\varepsilon)}), -W_{-1}(-e^{-(1+\varepsilon)})]\} \quad (\text{by (24)})$$

$$= \left[ \frac{1}{x} W_{-1}(-e^{-(1+\varepsilon)}), \frac{1}{x} W_0(-e^{-(1+\varepsilon)}) \right]$$

$$\subseteq \left[ \frac{-1-2\sqrt{\varepsilon}}{x}, \frac{-1+\sqrt{2\varepsilon}}{x} \right], \quad (\text{by (28)})$$

as desired.

□
Recall from Section 4.6.1 that the PF value of an allocation x is

$$PF(x) = \max_{j \in M} \sum_{i \in N} B_i \frac{v_{ij}}{u_i(x)}.$$

We will show that allocations that approximately maximize the Nash social welfare has a PF value not much higher than 1. Recall that we write $\varphi(x) = - \sum_{i \in N} B_i \log \langle v_i, x \rangle$ for the (negative) Nash social welfare of an allocation x. Let $\varphi^*$ denote Nash social welfare of the optimum allocation (i.e., the minimum). Write $B_{\min} = \min_{i \in N} B_i$.

**THEOREM 7 (APPROXIMATE NASH GIVES APPROXIMATE PF).** Let $0 \le \varepsilon < \frac{1}{2}$ such that $\varepsilon < \frac{B_{\min}}{2}$, and consider an allocation x with $\varphi(x) \le \varphi^* + \varepsilon$, i.e., that is $\varepsilon$-optimal w.r.t. Nash social welfare. Then

$$PF(x) \le \frac{1 + 2n\sqrt{\varepsilon/B} + n\varepsilon/B}{1 - \sqrt{2\varepsilon/B_{\min}}}.$$

**PROOF.** To apply the $\varepsilon$-KKT conditions, we will need some elementary calculus rules for the $\varepsilon$-subdifferential [Hiriart-Urruty, 1982, see also Dhara and Dutta, 2011, Section 2.6]: for $\lambda > 0$, we have $\partial_{\varepsilon}(\lambda f)(x) = \lambda \partial_{\varepsilon/\lambda} f(x)$, and for two convex functions $f_1, f_2$ defined on the same domain, we have

$$\partial_{\varepsilon}(f_1 + f_2)(x) = \bigcup_{\varepsilon_1, \varepsilon_2 \ge 0, \varepsilon_1 + \varepsilon_2 \le \varepsilon} \partial_{\varepsilon_1} f_1(x) + \partial_{\varepsilon_2} f_2(x). \quad (29)$$

Finally, for an affine function, the $\varepsilon$-subdifferential is singleton: $\partial_{\varepsilon}(ax + b)(x) = \{a\}$ for all $\varepsilon \ge 0$. Now consider the following program for maximizing Nash social welfare.

$$
\begin{array}{ll}
\max_{x,u} & \displaystyle \sum_{i \in N} B_i \log u_i \\
\text{s.t.} & \displaystyle \sum_{j \in M} x_j \le B \\
& u_i \le \sum_{j \in M} v_{ij} x_j \quad \text{for all } i \in N \\
& x_j \ge 0 \quad \text{for all } j \in M
\end{array}
$$

Writing this in the notation of Theorem 10, we are looking at the following program:

$$
\begin{array}{ll}
\min_{x,u} & \displaystyle - \sum_{i \in N} B_i \log u_i \\
\text{s.t.} & \displaystyle \sum_{j \in M} x_j - B \le 0 \\
& u_i - \sum_{j \in M} v_{ij} x_j \le 0 \quad \text{for all } i \in N \\
& -x_j \le 0 \quad \text{for all } j \in M
\end{array}
$$

Consider an $\varepsilon$-optimal solution $(x^*, u^*)$ to this program, and let $\lambda, (\mu_i)_{i \in N}, (\eta_j)_{j \in M} \ge 0$ be the multipliers promised by Theorem 10 corresponding to the three types of constraints, together with error values $\varepsilon_i$ corresponding to the objective and constraints. However, due to the condition "$-\varepsilon + \sum_{i=0}^m \varepsilon_i \le 0$" in Theorem 10, we can just upper bound all these individual error values by $\varepsilon$ and therefore won't need to track the individual ones.

Write $f(u) = - \sum_{i \in N} B_i \log u_i$ for the objective function. Then

$$\partial_{\varepsilon} f(u^*) = \bigcup_{\substack{(\tilde{\varepsilon}_i)_{i \in N} \ge 0 \\ \sum_{i \in N} \tilde{\varepsilon}_i \le \varepsilon}} \{(\tilde{u}_i)_{i \in N} : B_i \frac{-1-2\sqrt{\tilde{\varepsilon}_i/B_i}}{u_i^*} \le \tilde{u}_i \le B_i \frac{-1+\sqrt{2\tilde{\varepsilon}_i/B_i}}{u_i^*} \text{ for all } i \in N\}$$
$$ \subseteq \{(\bar{u}_i)_{i \in N} : B_i \frac{-1-2\sqrt{\varepsilon/B_i}}{u_i^*} \le \bar{u}_i \le B_i \frac{-1+\sqrt{2\varepsilon/B_i}}{u_i^*} \text{ for all } i \in N\}. \quad (\text{using } \bar{\varepsilon}_i \le \varepsilon) $$

Thus, from the stationarity condition in Theorem 10 applied to the $u_i^*$ variable, it follows that there exist $(\bar{u}_i)_{i \in N}$ such that

$$ 0 = \bar{u}_i + \mu_i \quad \text{for all } i \in N, \quad (30) $$

where $(\bar{u}_i)_{i \in N}$ is an element of $\partial_{\bar{\varepsilon}} f(u^*)$ and thus satisfies

$$ B_i \frac{-1-2\sqrt{\varepsilon/B_i}}{u_i^*} \le \bar{u}_i \le B_i \frac{-1+\sqrt{2\varepsilon/B_i}}{u_i^*} \quad \text{for all } i \in N. \quad (31) $$

By the stationarity condition applied to the variable $x_j$, we get

$$ 0 = \lambda - \sum_{i \in N} v_{ij} \mu_i - \eta_j \quad \text{for all } j \in M. \quad (32) $$

Rearranging and multiplying by $x_j^*$ we deduce

$$ \lambda x_j^* = \sum_{i \in N} \mu_i v_{ij} x_j^* + \eta_j x_j^* \quad \text{for all } j \in M. \quad (33) $$

Note that the complementary slackness condition of Theorem 10 (which in weaker form guarantees $"-\varepsilon \le \sum_{i=1}^m \lambda_i h_i(x^*)"$) implies $-\varepsilon \le \sum_{j \in M} \eta_j(-x_j^*)$ (since we can drop terms corresponding to other constraints because they are all non-positive). Hence $\sum_{j \in M} \eta_j x_j^* \le \varepsilon$.

Now, summing (33) over all $j \in M$, we obtain

$$ \begin{aligned} \lambda B &= \sum_{i \in N} \mu_i u_i^* + \sum_{j \in M} \eta_j x_j^* \\ &\stackrel{(30)}{=} \sum_{i \in N} (-\bar{u}_i) u_i^* + \sum_{j \in M} \eta_j x_j^* \\ &\stackrel{(31)}{\le} \sum_{i \in N} B_i (1 + 2\sqrt{\varepsilon/B_i}) + \varepsilon \end{aligned} \quad (34) $$

Thus, from (32), we get

$$ \sum_{i \in N} v_{ij} \mu_i = \lambda - \eta_j \le \lambda \stackrel{(34)}{\le} \frac{1}{B} \sum_{i \in N} \left(B_i \left(1 + 2\sqrt{\varepsilon/B_i}\right) + \varepsilon\right). \quad (35) $$

Also

$$ \sum_{i \in N} v_{ij} \mu_i \stackrel{(30)}{=} \sum_{i \in N} v_{ij} (-\bar{u}_i) \stackrel{(31)}{\ge} \sum_{i \in N} v_{ij} B_i \frac{1-\sqrt{2\varepsilon/B_i}}{u_i^*} = \sum_{i \in N} B_i \frac{v_{ij}}{u_i^*} (1 - \sqrt{2\varepsilon/B_i}). \quad (36) $$

Putting (35) and (36) together, we obtain

$$ \sum_{i \in N} B_i \frac{v_{ij}}{u_i^*} (1 - \sqrt{2\varepsilon/B_i}) \le \frac{1}{B} \sum_{i \in N} \left(B_i (1 + 2\sqrt{\varepsilon/B_i}) + \varepsilon\right) $$

which we can simplify to

$$ \sum_{i \in N} B_i \frac{v_{ij}}{u_i^*} (1 - \sqrt{2\varepsilon/B_i}) \le 1 + \sum_{i \in N} \left(2\sqrt{\varepsilon B_i}/B + \varepsilon/B\right). $$

Using $B_i \le B$ and noting that the assumption $\varepsilon < \frac{B_{\min}}{2}$ implies that $1 - \sqrt{2\varepsilon/B_i} > 1 - \sqrt{2\varepsilon/B_{\min}} > 0$, we obtain

$$ \sum_{i \in N} B_i \frac{v_{ij}}{u_i^*} \le \frac{1 + 2n\sqrt{\varepsilon/B} + n\varepsilon/B}{1 - \sqrt{2\varepsilon/B_{\min}}}. $$

Since this holds for all $j \in M$, this proves the desired bound on the PF value of $x^*$. □
## B.2 Capped Public Goods

In this section, we use $\varepsilon$-KKT conditions to show that $\varepsilon$-optimal solutions to our convex program form approximate Lindahl equilibria. In the proof, we will need a version of Pinsker's inequality (connecting $L_1$ distance and KL divergence) that works even if one distribution is sub-normalized.

**LEMMA B.3.** Let $p = (p_1, \dots, p_n) \ge 0$ and $q = (q_1, \dots, q_n) \ge 0$ be non-negative vectors with $\sum_i p_i = 1$ (so $p$ is a probability distribution) and $\sum_i q_i \le 1$ (so $q$ is a sub-probability distribution). Then $\|p-q\|_1 \le \sqrt{2KL(p\|q)}$.

**PROOF.** Write $s = \sum_i q_i \le 1$, and consider the two probability distributions $\hat{p} = (p_1, \dots, p_n, 0)$ and $\hat{q} = (q_1, \dots, q_n, 1-s)$. Note that $KL(\hat{p}\|\hat{q}) = KL(p\|q) + 0 \log \frac{0}{1-s} = KL(p\|q)$. Now, by the standard version of Pinsker's inequality, $\|\hat{p} - \hat{q}\|_1 \le \sqrt{2KL(\hat{p}\|\hat{q})}$. Hence

$$ \|p - q\|_1 = \sum_i |p_i - q_i| = \|\hat{p} - \hat{q}\|_1 - |(1-s) - 0| \le \|\hat{p} - \hat{q}\|_1 \le \sqrt{2KL(\hat{p}\|\hat{q})} = \sqrt{2KL(p\|q)}. \quad \square $$

As the first part of the argument, we show that approximate solutions satisfy an approximate utility maximization condition, under the assumption that each project receives some minimum amount of spending, i.e. $x_j \ge t$ for all $j \in M$.

**LEMMA B.4.** Let $t > 0$ and $0 \le \varepsilon \le 1$. Assume that $v_{ij} > 1$ whenever $v_{ij} > 0$ and that $cap_j \le B$ for all $j \in M$. Let $b$ be an $\varepsilon$-optimal solution to Program 16 such that $x_j(b) \ge t$ for all $j \in M$. Fix an agent $i \in N$ such that $\sum_{j \in M_i} b_{ij} = B_i$, and consider the personalized prices $p_{ij} = b_{ij}/x_j$ for all $j \in M_i$. Then for

$$ \varepsilon' = (m+1)Be^{2Fi} (\sqrt{2\varepsilon/t} + 2\varepsilon/t), \quad \text{where } F_i = \frac{B \log(v_{\max} \cdot n) + 1}{\frac{1}{2m} \min(B_i, \text{cap}_{\min})}, $$

the allocation $x = x(b)$ maximizes $i$'s utility up to $\varepsilon'$. More precisely, for every allocation $y$ satisfying the cap constraints and satisfying $\langle p_i, y \rangle \le B_i$, we have $u_i(x) \ge u_i(y) - \varepsilon'$.

The assumption that $cap_j \le B$ for all $j \in M$ is used in the proof for technical reasons (to bound the magnitude of bundles $y$ considered in the utility maximization condition) but it is innocuous in a practical sense.

**PROOF.** Suppose $b$ forms an $\varepsilon$-optimal solution to the convex program and is such that there is some $t > 0$ with $x_j(b) \ge t$ for all $j \in M$. Write $p_{ij} := b_{ij}/x_j(b)$ for $i \in N$, $j \in M_i$.

By Theorem 10 ($\varepsilon$-KKT), there exists $g \in \partial_{\varepsilon} f(b)$ and multipliers $\lambda_i, \mu_j, \eta_{ij} \ge 0$ such that

$$ g_{ij} + \lambda_i + \mu_j - \eta_{ij} = 0 $$

and $\varepsilon$-complementary slackness holds with slackness errors $\varepsilon_{\lambda_i}, \varepsilon_{\mu_j}, \varepsilon_{\eta_{ij}} \ge 0$ satisfying $\sum_{i \in N} \varepsilon_{\lambda_i} + \sum_{j \in M} \varepsilon_{\mu_j} + \sum_{i \in N, j \in M_i} \varepsilon_{\eta_{ij}} \le \varepsilon$ and

$$ \lambda_i (B_i - \sum_j b_{ij}) \le \varepsilon_{\lambda_i}, \quad \mu_j (\text{cap}_j - \sum_i b_{ij}) \le \varepsilon_{\mu_j}, \quad \eta_{ij} b_{ij} \le \varepsilon_{\eta_{ij}}. $$

**Computing the subdifferential.** Next, let us understand the consequences of $g \in \partial_{\varepsilon} f(b)$. For this, it is convenient to first compute the $\varepsilon$-subdifferential of the function $h(x) = \sum_i x_i \log \frac{x_i}{\sum_k x_k}$. Using that its convex conjugate $h^*(y)$ satisfies $h^*(y) = 0$ if $\sum_i e^{y_i} \le 1$ and $h^*(y) = +\infty$ otherwise, as shown in Lemma A.1, we find that

$$ \begin{aligned} \partial_{\varepsilon} h(x) &= \{w : h(x) + h^*(w) \le \langle x, w \rangle + \varepsilon\} \\ &= \left\{w : \sum_i e^{w_i} \le 1 \text{ and } \langle w, x \rangle \ge \sum_i x_i \log \frac{x_i}{\sum_k x_k} - \varepsilon\right\}. \end{aligned} $$
Therefore, by the summation rule for $\epsilon$-subdifferentials (see Eq. (29) and surrounding text), it follows that the vector $g \in \partial_{\epsilon} f(b)$ can be written as $g_{ij} = -\log v_{ij} + w_{ij}$ for some $(w_{ij})_{i \in N, j \in M_i}$ such that $\sum_{i \in N_j} e^{w_{ij}} \le 1$ for all $j \in M$ and that satisfy the following:

$$ \sum_{i \in N_j} b_{ij} w_{ij} \ge \sum_{i \in N_j} b_{ij} \log \frac{b_{ij}}{x_j(b)} - \epsilon \quad \text{for all } j \in M. $$

We can rewrite this latter condition as

$$ \sum_{i \in N_j} b_{ij} (\log p_{ij} - \log e^{w_{ij}}) \le \epsilon \quad \text{for all } j \in M $$

which implies

$$ x_j(b)KL((p_{ij})_{i \in N_j} \| (e^{w_{ij}})_{i \in N_j}) \le \epsilon \quad \text{for all } j \in M. $$

Applying Pinsker's inequality (Lemma B.3, which is applicable since $\sum_{i \in N_j} e^{w_{ij}} \le 1$) and using that $x_j(b) \ge t$, we find that

$$ \|(p_{ij})_{i \in N_j} - (e^{w_{ij}})_{i \in N_j}\|_1^2 \le 2\epsilon/t \quad \text{for all } j \in M, $$

and since $\| \cdot \|_{\infty} \le \| \cdot \|_1$, we get

$$ |p_{ij} - e^{w_{ij}}| \le \sqrt{2\epsilon/t} \quad \text{for all } j \in M \text{ and } i \in N_j. \quad (37) $$

**Stationarity condition.** Now, the stationarity conditions become

$$ \log v_{ij} = w_{ij} + \lambda_i + \mu_j - \eta_{ij}. $$

Exponentiating,

$$ v_{ij} = e^{w_{ij}} e^{\lambda_i} e^{\mu_j} e^{-\eta_{ij}}. \quad (38) $$

**Bounding the multipliers.** Fix an agent $i \in N$. We wish to bound the magnitude of the multipliers, using Lemma B.1. Write

$$ q = \frac{\min(B_i, \text{cap}_{\min})}{2m} $$

and consider the solution $b^\circ$ with $b_{ij}^\circ = q$ for all $j \in M_i$ and $b_{i'j}^\circ = 0$ for all other $i' \ne i$ or $j \notin M_i$). This solution is feasible since the total spending of $i$ is at most $B_i/2$ and each project receives spending of at most cap$_{min}/(2m)$, thus respecting the cap constraint.

Next, we check that various constraints have significant slack in the solution $b^\circ$. The budget constraint of $i$ has slack at least $B_i/2 \ge q$. The capacity constraint of each project $j \in M_i$ has slack at least cap$_{min}/2 \ge q$. The non-negativity constraint associated with $b_{ij}$ has slack $q$. Thus, each of these types of constraints has slack at least $q$.

Note that $f(b^\circ) \le 0$ (trivially). Also, we can give an upper bound on the objective value of any solution $\hat{b}$ to the program:

$$ -f(\hat{b}) = \sum_{i \in N, j \in M_i} \hat{b}_{ij} \log v_{ij} + \sum_{j \in M} x_j(\hat{b}) \left( - \sum_{i \in N_j} \frac{\hat{b}_{ij}}{x_j(\hat{b})} \log \frac{\hat{b}_{ij}}{x_j(\hat{b})} \right) \le B \log v_{\max} + B \log n, $$

where we used the fact that the Shannon entropy of a distribution over $n$ elements is at most $\log n$. Hence $-f^* \le B \log(v_{\max} \cdot n)$. Thus, from Lemma B.1 and using $\epsilon \le 1$, we deduce that

$$ \lambda_i, (\mu_j)_{j \in M_i}, (\eta_{ij})_{j \in M_i} \le \frac{B \log(v_{\max} \cdot n) + 1}{\frac{1}{2m} \min(B_i, \text{cap}_{\min})} =: F. \quad (39) $$
**Utility maximization.** Continue to fix the agent $i \in N$, and like in the lemma statement assume that $\sum_{j \in M_i} b_{ij} = B_i$. We wish to show that the allocation $x = x(b)$ approximately maximizes the utility of $i$ with respect to the prices $p_{ij} = b_{ij}/x_j(b)$. Note that with these prices, $x$ is exactly affordable by our assumption, $\langle p_i, x \rangle = \sum_{j \in M_i} b_{ij}/x_j(b) \cdot x_j(b) = B_i$. Let $y$ be any other allocation satisfying the cap constraints, i.e., $0 \le y_j \le \text{cap}_j$, and which is affordable for agent $i$, i.e., $\langle p_i, y \rangle \le B_i$. Since we assumed that $\text{cap}_j \le B$ for all $j \in M$, and thus $\sum_{j \in M} y_j \le \sum_{j \in M} \text{cap}_j \le m \cdot B$.

To establish that $x$ is approximately utility-maximizing, we need to show that $u_i(y) - u_i(x)$ is small. Rewriting,

$$ 
\begin{aligned}
u_i(y) - u_i(x) &= \sum_{j \in M_i} v_{ij}(y_j - x_j) \\
&\stackrel{(38)}{=} \sum_{j \in M_i} e^{w_{ij}} e^{\lambda_i} e^{\mu_j} e^{-\eta_{ij}} (y_j - x_j) \\
&= e^{\lambda_i} \sum_{j \in M_i} e^{w_{ij}} e^{\mu_j} e^{-\eta_{ij}} (y_j - x_j)
\end{aligned}
$$

For each $j \in M_i$, let us write $e^{w_{ij}} = p_{ij} + \delta_{ij}$ for some error value $\delta_{ij}$, where from (37) we know $|\delta_{ij}| \le \sqrt{2\epsilon}/t$. Then

$$ 
\begin{aligned}
u_i(y) - u_i(x) &= e^{\lambda_i} \sum_{j \in M_i} (p_{ij} + \delta_{ij}) e^{\mu_j} e^{-\eta_{ij}} (y_j - x_j) \\
&= e^{\lambda_i} \underbrace{\sum_{j \in M_i} p_{ij} e^{\mu_j} e^{-\eta_{ij}} (y_j - x_j)}_{\text{Main Term}} + e^{\lambda_i} \underbrace{\sum_{j \in M_i} \delta_{ij} e^{\mu_j} e^{-\eta_{ij}} (y_j - x_j)}_{E_1: \text{Error from subgradient approx.}}
\end{aligned}
$$

Let's bound the error term $E_1$:

$$ 
\begin{aligned}
|E_1| &\le e^{\lambda_i} \sum_{j \in M_i} |\delta_{ij}| e^{\mu_j} e^{-\eta_{ij}} |y_j - x_j| \\
&\le e^F \left(\sqrt{2\epsilon/t}\right) e^F \cdot 1 \cdot \sum_{j \in M_i} |y_j - x_j| && (\text{using } \eta_{ij} \ge 0 \text{ so } e^{-\eta_{ij}} \le 1) \\
&\le e^{2F} \sqrt{2\epsilon/t} (\sum_j y_j + \sum_j x_j) \\
&\le e^{2F} \sqrt{2\epsilon/t} (mB + B) && (\sum_{j \in M} y_j \le m \cdot B) \\
&= (m+1)Be^{2F} \sqrt{2\epsilon/t}.
\end{aligned}
$$

Now, let's analyze the Main Term. We can rewrite it as:

$$ 
\text{Main Term} = e^{\lambda_i} \sum_{j \in M_i} p_{ij}(y_j - x_j) + e^{\lambda_i} \underbrace{\sum_{j \in M_i} p_{ij}(e^{\mu_j} e^{-\eta_{ij}} - 1)(y_j - x_j)}_{E_2: \text{Error from slackness}}.
$$

The first part is non-positive because $y$ is affordable for $i$ and $x$ exhausts the budget of $i$:

$$ e^{\lambda_i} \sum_{j \in M_i} p_{ij}(y_j - x_j) = e^{\lambda_i} (\langle p_i, y \rangle - \langle p_i, x \rangle) \le e^{\lambda_i} (B_i - B_i) = 0. $$

So, we only need to bound the slackness error, $E_2$. Let's split the sum based on the sign of $(y_j - x_j)$.
**Case 1:** $y_j > x_j$. The term $(y_j - x_j)$ is positive. We need an upper bound for $(e^{\mu_j}e^{-\eta_{ij}} - 1)$. Since $\eta_{ij} \ge 0$, we have $e^{-\eta_{ij}} \le 1$, so $e^{\mu_j}e^{-\eta_{ij}} - 1 \le e^{\mu_j} - 1$. Now,

$$ 
\begin{aligned}
p_{ij}(e^{\mu_j} - 1)(y_j - x_j) &\le p_{ij}(e^{\mu_j} - 1)(\text{cap}_j - x_j) && (\text{since } y_j \le \text{cap}_j) \\
&\le p_{ij}e^{\mu_j}\mu_j(\text{cap}_j - x_j) && (\text{using } e^z - 1 \le ze^z \text{ for } z \ge 0)
\end{aligned}
$$

From $\varepsilon$-complementary slackness, we have $\mu_j(\text{cap}_j - x_j) \le \varepsilon\mu_j$ with $\sum_j \varepsilon\mu_j \le \varepsilon$. The contribution from this case to $E_2$ is at most:

$$ e^{\lambda_i} \sum_{j: y_j > x_j} p_{ij} e^{\mu_j} \varepsilon_{\mu_j} \le e^F \sum_{j: y_j > x_j} (B/t) e^F \varepsilon_{\mu_j} \le (B/t) e^{2F} \sum_j \varepsilon_{\mu_j} \le (B/t) e^{2F} \varepsilon. $$

**Case 2:** $y_j < x_j$. The term $(y_j - x_j)$ is negative. We need a lower bound for $(e^{\mu_j}e^{-\eta_{ij}} - 1)$ to get an upper bound on the product. Using $e^{-z} \ge 1 - z$ for $z \ge 0$:

$$ e^{\mu_j} e^{-\eta_{ij}} - 1 \ge e^{\mu_j}(1 - \eta_{ij}) - 1 = (e^{\mu_j} - 1) - \eta_{ij}e^{\mu_j} \ge -\eta_{ij}e^{\mu_j}. $$

The term $p_{ij}(e^{\mu_j}e^{-\eta_{ij}} - 1)(y_j - x_j)$ is therefore bounded above by $p_{ij}(-\eta_{ij}e^{\mu_j})(y_j - x_j)$. From $\varepsilon$-complementary slackness, $\eta_{ij}b_{ij} \le \varepsilon\eta_{ij}$ with $\sum_{ij} \varepsilon\eta_{ij} \le \varepsilon$. This means $\eta_{ij}p_{ij}x_j \le \varepsilon\eta_{ij}$, so $\eta_{ij}p_{ij} \le \varepsilon\eta_{ij}/x_j \le \varepsilon\eta_{ij}/t$. Hence

$$ 
\begin{aligned}
p_{ij}(-\eta_{ij}e^{\mu_j})(y_j - x_j) &= (- (y_j - x_j)) \cdot (p_{ij}\eta_{ij}) \cdot e^{\mu_j} \\
&\le x_j \cdot (\varepsilon\eta_{ij}/t) \cdot e^F \le (B/t) e^F \varepsilon\eta_{ij}.
\end{aligned}
$$

The contribution from this case to $E_2$ is at most $e^{\lambda_i} \sum_{j: y_j < x_j} (B/t) e^F \varepsilon_{\eta_{ij}} \le (B/t) e^{2F} \varepsilon$.

Combining both cases, we get $|E_2| \le (2B/t)e^{2F}\varepsilon$.

Finally, putting everything together:

$$ 
\begin{aligned}
u_i(y) - u_i(x) \le 0 + |E_1| + |E_2| &\le (m+1)Be^{2F}\sqrt{2\varepsilon/t} + (2B/t)e^{2F}\varepsilon \\
&\le (m+1)Be^{2F}(\sqrt{2\varepsilon/t} + 2\varepsilon/t). && (\text{since } 2 \le m+1)
\end{aligned}
$$

This shows that $u_i(x) \ge u_i(y) - \varepsilon'$ where $\varepsilon' = (m+1)Be^{2F}(\sqrt{2\varepsilon/t} + 2\varepsilon/t)$, as required. $\square$

We now use Lemma B.4 to show that an approximate solution to our convex program produces an approximate Lindahl equilibrium, in the following sense discussed in Section 5.3.

**DEFINITION 6 (ε-LINDAH EQUILIBRIUM).** Let $\varepsilon \ge 0$. A pair $(x, p)$ of a vector $x = (x_j)_{j \in M}$ such that $0 \le x_j \le \text{cap}_j$ for all $j \in M$ and a set of personalized prices $p$ forms an $\varepsilon$-Lindahl equilibrium if

* $x$ is approximately budget-feasible: $\sum_{j \in M} x_j \le B + \varepsilon$ (i.e., $x$ may overshoot the total budget),

* $x$ is affordable: we have $\langle p_i, x \rangle \le B_i$ for every $i \in N$,

* $x$ is approximately utility-maximizing: for every $i \in N$ and every $y \in \mathbb{R}_{\ge 0}^m$ such that $0 \le y_j \le \text{cap}_j$ for all $j \in M$ and such that $\langle p_i, y \rangle \le B_i$, we have $u_i(x) \ge u_i(y) - \varepsilon$,

* $x$ is approximately profit-maximizing: for every $j \in M$ we have $\sum_{i \in N} p_{ij} \le 1$, and whenever $x_j > 0$ then $\sum_{i \in N} p_{ij} \ge 1 - \varepsilon/x_j$.

Since Lemma B.4 makes an extra assumption that $x_j \ge t$ for all $j \in M$, our argument perturbs the input instance by adding additional voters with $\varepsilon$ weight who ensure that in any feasible solution to the program, we have $x_j \ge \varepsilon/m$ for all $j \in M$. We then invoke Lemma B.4 with $t = \varepsilon/m$, and show that the resulting solution for the perturbed instance forms an approximate Lindahl equilibrium with respect to the original instance.

**THEOREM 9 (APPROXIMATE SOLUTIONS GIVE $\varepsilon$-LINDAH EQUILIBRIUM).** Let $0 < \varepsilon \le \min\{1, \text{cap}_{\min}\}$ where $\text{cap}_{\min} = \min_{j \in M} \text{cap}_j$. Assume that $v_{ij} > 1$ whenever $v_{ij} > 0$, that $B \ge 1$, and that $\text{cap}_j \le B$
for all $j \in M$. There is an algorithm computing an $\epsilon$-Lindahl equilibrium for the capped public goods setting running in polynomial time (with a logarithmic dependence on $1/\epsilon$).

PROOF. Given an instance $I$ of the capped public goods problem and a value of $\epsilon > 0$, our algorithm will construct a perturbed instance $I'$ on agent set $N' = N \cup \{i_1^+, \dots, i_m^+\}$, obtained by adding an extra agent $i_j^+$ for each project $j \in M$, with budget $B_{i_j^+} = \epsilon/m$ and with a “single-minded” valuation, meaning that $M_{i_j^+} = \{j\}$ (say $v_{i_j^+} = 2$ and $v_{i_j^+} = 0$ for all $k \neq j$). Thus, the overall budget available in $I'$ is $B' = B + m \cdot \frac{\epsilon}{m} = B + \epsilon$.

Now let $B_{\min} = \min_{i \in N} B_i$ (where the minimum is taken only over the original agents) and set

$$ \epsilon_{\text{solver}} = \frac{\epsilon^3}{(2\gamma)^2 \cdot 2m} \quad \text{for } \gamma := (m+1)Be^{2F} \text{ and } F := \frac{B \log(v_{\max} \cdot n) + 1}{\frac{1}{2m} \min(B_{\min}, \text{cap}_{\min})} $$

The algorithm will compute an $\epsilon_{\text{solver}}$-optimal solution $b$ to Program 16 as applied to the perturbed instance $I'$. We can do this using the ellipsoid method [see, e.g., Vishnoi, 2021, Theorem 13.1] whose runtime has a dependence on $\log \frac{1}{\epsilon_{\text{solver}}}$ which is polynomial (as $\epsilon_{\text{solver}}$ contains single-exponential terms).

The algorithm then checks if there is a voter $i \in N'$ who doesn't spend all of their budget (i.e., $\sum_{j \in M_i} b_{ij} < B_i$) but approves a project that doesn't exhaust its cap (i.e., $x_j(b) < \text{cap}_j$ for some $j \in M_i$). In these cases, the algorithm increases $b_{ij}$ appropriately. This increase preserves feasibility and improves the objective function value since the partial derivative of the objective function of the program is $\partial g(b)/\partial b_{ij} = -\log v_{ij} + \log \frac{b_{ij}}{x_j(b)}$ (see Lemma 7) which is negative when $j \in M_i$ because $v_{ij} > 1$ by our normalization and $0 \le b_{ij}/x_j(b) \le 1$ by definition of $x_j(b)$. Thus, increasing $b_{ij}$ decreases the objective function which is to be minimized. Thus, this increase preserves being an $\epsilon$-optimal solution. This process is repeated until no such voter $i$ exists.

Now, for every $j \in M$, we either have $x_j(b) = \text{cap}_j \ge \epsilon$, or else (by the postprocessing we just did) the entire budget of the extra voter $i_j^+$ must be going towards project $j$ and hence $x_j(b) \ge b_{i_j^+} = B_{i_j^+} = \epsilon/m$. In either case $x_j(b) \ge \epsilon/m$. This will later allow us to invoke Lemma B.4 with $t = \epsilon/m$.

Consider the personalized prices defined as $p_{ij} = b_{ij}/x_j$ for all $i \in N$ and $j \in M_i$. We will show that $(x, (p_{ij})_{i \in N, j \in M})$ is an $\epsilon$-approximate Lindahl equilibrium (for the original instance $I$).

* For approximate budget-feasibility, note that $\sum_{j \in M} x_j \le B' = B + \epsilon$.

* For affordability, note that $\langle p_i, x \rangle = \sum_{j \in M} \frac{b_{ij}}{x_j} x_j = \sum_{j \in M_i} \frac{b_{ij}}{x_j} x_j = \sum_{j \in M_i} b_{ij} \le B_i$ for all $i \in N$, since $b$ is a feasible solution to Program 16.

* For approximate utility maximization, consider some agent $i \in N$. By our post-processing of the solution, if we have $\sum_{j \in M_i} b_{ij} < B_i$, then all projects that agent $i$ likes have been funded up to their cap, so $i$ receives the best-possible outcome and thus utility maximization is satisfied for $i$. Otherwise, $\sum_{j \in M_i} b_{ij} = B_i$ and we can invoke Lemma B.4 with $\epsilon_{\text{solver}}$ and $t = \epsilon/m$, which shows that $x$ is utility-maximizing for $i$ up to an error of $\epsilon_{\text{util}}$ as specified in the statement of Lemma B.4, which is in terms of a parameter $F_i$ (involving a $1/B_i$ term) that we can upper bound by $F$ (which instead involves a $1/B_{\min}$ term). In the following computation, we will use that $2\gamma = 2(m+1)Be^{2F} \ge 1$ which follows since $2F > 0$ (which itself follows from $v_{\max} > 1$ due to the normalization of valuations) and $B \ge 1$ by assumption of the theorem. We get

$$ \epsilon_{\text{util}} = (m+1)Be^{2F_i} \left( \sqrt{2\epsilon_{\text{solver}}/(\epsilon/m)} + 2\epsilon_{\text{solver}}/(\epsilon/m) \right) \quad \text{(from Lemma B.4)} $$

$$ \le (m+1)Be^{2F_i} \left( \sqrt{2\epsilon_{\text{solver}}/(\epsilon/m)} + 2\epsilon_{\text{solver}}/(\epsilon/m) \right) \quad \text{(as } F_i \le F \text{)} $$
$$ \leq \gamma \left( \sqrt{2\varepsilon_{\text{solver}}/(\varepsilon/m)} + 2\varepsilon_{\text{solver}}/(\varepsilon/m) \right) \qquad (\text{def. of } \gamma) $$

$$ = \gamma \left( \sqrt{2\varepsilon^3/((2\gamma)^2 2m \cdot \varepsilon/m)} + 2\varepsilon^3/((2\gamma)^2 2m \cdot \varepsilon/m) \right) \qquad (\text{def. of } \varepsilon_{\text{solver}}) $$

$$ = \gamma \left( \sqrt{\varepsilon^2/(2\gamma)^2} + \varepsilon^2/(2\gamma)^2 \right) \qquad (\text{cancelling}) $$

$$ = \gamma \left( \varepsilon/(2\gamma) + \varepsilon^2/(2\gamma)^2 \right) \qquad (\text{take square root}) $$

$$ \leq \gamma \cdot \left( \varepsilon/(2\gamma) + \varepsilon/(2\gamma) \right) \qquad (\varepsilon \leq 1 \text{ and } 2\gamma \geq 1) $$

$$ = \varepsilon, $$

hence showing that $x$ is $\varepsilon$-utility maximizing for $i$.

* For approximate profit maximization, note that for every $j \in M$ we have $\sum_{i \in N} p_{ij} = \sum_{i \in N} b_{ij}/x_j \leq \sum_{i \in N'} b_{ij}/x_j = 1$ by definition of $x_j = x_j(b)$. Also note that by construction, we have $x_j > 0$ for every $j$, and we have $\sum_{i \in N} p_{ij} = \sum_{i \in N} b_{ij}/x_j = \sum_{i \in N'} b_{ij}/x_j - \sum_{k \in M} b_{k,j}/x_j = 1 - b_{k,j}^+/x_j \geq 1 - B_{k,j}^+/x_j = 1 - \frac{\varepsilon}{mx_j} \geq 1 - \frac{\varepsilon}{x_j}$.

Thus, the algorithm has successfully computed an $\varepsilon$-approximate Lindahl equilibrium. $\square$