# District-Fair Participatory Budgeting

D. Ellis Hershkowitz,1 Anson Kahng,1 Dominik Peters,2 Ariel D. Procaccia2

###### Abstract

Participatory budgeting is a method used by city governments to select public
projects to fund based on residents’ votes. Many cities use participatory
budgeting at a district level. Typically, a budget is divided among districts
proportionally to their population, and each district holds an election over
local projects and then uses its budget to fund the projects most preferred by
its voters. However, district-level participatory budgeting can yield poor
social welfare because it does not necessarily fund projects supported across
multiple districts. On the other hand, decision making that only takes global
social welfare into account can be unfair to districts: A social-welfare-
maximizing solution might not fund any of the projects preferred by a
district, despite the fact that its constituents pay taxes to the city. Thus,
we study how to fairly maximize social welfare in a participatory budgeting
setting with a single city-wide election. We propose a notion of fairness that
guarantees each district at least as much welfare as it would have received in
a district-level election. We show that, although optimizing social welfare
subject to this notion of fairness is NP-hard, we can efficiently construct a
lottery over welfare-optimal outcomes that is fair in expectation. Moreover,
we show that, when we are allowed to slightly relax fairness, we can
efficiently compute a fair solution that is welfare-maximizing, but which may
overspend the budget.

##  1 Introduction

Participatory budgeting is a democratic approach to the allocation of public
funds. In the participatory budgeting paradigm, city governments fund public
projects based on constituents’ votes. In contrast to budget committees, which
operate behind closed doors, participatory budgeting promises to directly take
the voices of the community into account. Since 2014, Paris has allocated more
than €100 million per year using constituents’ votes. Many other cities around
the globe — including Porto Alegre, New York City, Boston, Chicago, San
Francisco, Lisbon, Madrid, Seoul, Chengdu, and Toronto — employ participatory
budgeting (Cabannes 2004, 2014; Aziz and Shah 2020).

Typically, participatory budgeting is used at a district-level. Each district
of the city is allotted a budget proportional to its size. Constituents living
in a given district vote on projects such as park, road or school improvements
local to the district, using some version of approval voting. Then, the
district’s budget is spent according to these votes. For instance, in Paris a
participatory budget is split between 20 districts (a.k.a. arrondissements),
constituents vote and then each district runs a greedy algorithm to maximize
the total social welfare — i.e., the total number of votes — of the funded
projects.111More specifically, projects are selected in descending order of
vote count until the budget runs out.

Having separate elections for each district leads to several problems.
Foremost, projects that are not local to a single district cannot be
accommodated. For this reason, Paris must run an additional election for city-
wide projects. However, this splits the available budget for participatory
budgeting between district-level and city-wide elections in an ad hoc manner,
which is not informed by votes.222In 2016, this split in Paris was €64.3
million for district elections and €30 million for city-wide elections
(Cabannes 2017). Further, people may have interests in multiple districts,
such as those who live and work in different districts. For this reason, Paris
has to allow residents to choose the district in which they vote. Lastly, a
project that only benefits voters at the edge of a district may receive a
number of votes that is not proportional to the number of potential
beneficiaries.

A simple solution to these problems is a single city-wide election. However,
such a voting scheme may result in unfair outcomes. For instance, if votes are
aggregated to maximize social welfare (i.e., as is presently done in Paris on
the district level) then it is possible that some districts might have none of
their preferred projects funded despite deserving a large proportion of the
budget. Such outcomes are likely when some districts are much more populous
than others, in which case projects local to small districts cannot gather
sufficiently many votes. Ideally, we would like a system that balances the
tradeoff between social welfare and fairness without an arbitrary, pre-
determined split between district-specific and city-wide funding. This
motivates our central research question:

> _How can we maximize social welfare in a way that is fair to all districts?_

Intuitively, a solution that is fair to all districts should somehow represent
each districts’ constituents. One way to formalize this intuition is to
stipulate that no district should be able to obtain higher utility by
purchasing projects with its proportional share of the budget. In particular,
each district should receive at least as much utility as it would have
received had it held a district-level election with its proportional share of
the budget. We call this guarantee _district fairness_.333Our notion of
district fairness can be thought of as a form of _individual rationality_
where every district is seen as an “individual.” A district-fair allocation of
funds always exists, since an outcome obtained by holding separate district
elections is district fair. We aim to find district-fair outcomes that
maximize social welfare. Such an outcome will be a Pareto-improvement on the
status quo of district-level participatory budgeting, in the sense that each
district’s welfare has increased.

### Our Results.

In our model we think of (utilitarian) social welfare as induced by a given
value assigned by each district to each project; our goal is to maximize the
sum of these values over districts and selected projects. Note that this model
captures the setting of approval votes, where each voter decides on a
collection of projects to vote for; the social welfare of a district for a
project would then be interpreted as the project’s overall number of approvals
from voters in that district. This observation is important because some
variant of approval voting is used in most real-world participatory budgeting
elections, including in Paris.

We also assume that each district is endowed with an arbitrary fraction of the
total budget. Clearly this captures, as a special case, the common setting
where the endowment of each district is proportional to its size. Moreover,
the reasoning behind the existence of district-fair outcomes immediately
applies to the more general setting.

We first show that it is NP-complete to compute an allocation that is welfare-
maximizing subject to district fairness. This result holds even for the case
of approval votes and proportional budgets, and therefore the generality of
our model only strengthens our positive (algorithmic) results without
weakening the main negative (hardness) result. We also show that the natural
linear program (LP) formulation of the problem has an unbounded integrality
gap. Since participatory budgeting elections can be large — hundreds of
projects are proposed and hundreds of thousands of votes are cast in Paris —
computational complexity can become a problem in practice. Thus, we seek
polynomial-time solutions with reasonable approximation guarantees.

There are several ways one might relax our problem or trade-off between
parameters in our problem. In this work, we design polynomial-time algorithms
that work when we relax or approximate some of the following: (1) the achieved
social welfare; (2) the spent budget; (3) the fairness of the solution; and
(4) the absence of randomization.

We first relax (4) by considering distributions over outcomes, a.k.a.
“lotteries”. We show that using a multiplicative-weights-type algorithm, one
can efficiently find a lottery that guarantees budget feasibility (ex post),
optimum social welfare (ex post), and district-fairness in expectation up to
an $\varepsilon$ (ex ante). Since the fairness guarantee only holds in
expectation, some districts may be underserved once the lottery is realized.
However, since participatory budgeting typically happens repeatedly (e.g.,
annually), such districts could be compensated in the next election, for
example by increasing their share of the budget in the next year.

We next consider what sort of deterministic guarantees are achievable. To this
end, we show how to use techniques from submodular optimization to find an
outcome that is district fair “up to one project” and which achieves optimum
social welfare with the caveat that the outcome may need to spend $64.7\%$
more money than was originally budgeted. We also give a randomized algorithm
with the same guarantees but which overshoots the budget by only a $1/e$
$(\approx 37\%)$ fraction with high probability. Additionally, as a corollary
of these results, we give both deterministic and randomized algorithms that
achieve weaker utility and fairness guarantees but do not overspend the
available budget.

### Related Work.

The social choice literature on participatory budgeting has both studied the
voting rules used in practice, and designed original voting schemes. Goel et
al. (2019) study knapsack voting, used for example in Madrid (Cabannes 2014),
where voters cannot approve more projects than fit into the budget constraint.
Talmon and Faliszewski (2019) axiomatically study a variety of approval-based
rules that maximize social welfare, both greedy and optimal ones.

The unit cost case (where all projects have the same cost) is best-studied, as
_multi-winner_ or _committee_ elections (Faliszewski et al. 2017). For
example, this setting models the election of a parliament. A main focus of
that literature is the computational complexity of the winner determination of
various voting rules. More relevant for our purposes are fairness axioms used
in this setting. The most prominent such axioms are variants of _justified
representation_ (Aziz et al. 2017). These axioms are formulated for approval
votes, and require that arbitrary subgroups of the electorate need to be
represented in the outcome if they are _cohesive_ , in the sense that there
are a sufficient number of projects that are approved by every member of the
subgroup. Several voting rules are known to satisfy these conditions,
including Phragmén’s rule and Thiele’s Proportional Approval Voting (Janson
2016; Sánchez-Fernández et al. 2017; Brill et al. 2017; Aziz et al. 2018). By
contrast, district-fairness gives guarantees to a specific selection of
subgroups (i.e., disjoint districts) but does not require these groups to be
cohesive.

A very strong fairness axiom that is sometimes discussed in the context of
committee elections and participatory budgeting is the _core_ (Fain, Goel, and
Munagala 2016; Aziz et al. 2017; Fain, Munagala, and Shah 2018). It insists
that every subgroup (or _coalition_) must be represented (in the sense that it
should not be possible for the subgroup to propose an alternative use of their
proportional share of the budget that each group member prefers to the chosen
outcome), without a cohesiveness requirement. For approval-based elections, it
is a major open question whether there always exists a core outcome. For
general additive utilities, there are instance where no core outcome exists
(Fain, Munagala, and Shah 2018), but several researchers have proved the
existence of approximations to the core (Jiang, Munagala, and Wang 2020; Fain,
Munagala, and Shah 2018; Cheng et al. 2019; Peters and Skowron 2020). A
district-fair outcome is, in a sense, in the core: no subgroup which coincides
with a district can block the outcome. Thus, our work shows that for general
utilities, a core-like outcome exists if we only allow a specific collection
of (disjoint) coalitions to block.

The problem of _knapsack sharing_ (Brown 1979) has a similar motivation to our
problem. The knapsack sharing problem supposes that the _projects_ are
separated into districts (instead of, in our case, the voters), and each
project comes with a cost and a value. The aim is to find a budget-feasible
set of projects that maximize the minimum total value of the projects in a
district. Note that in this formulation all districts are treated equally
(there is no weighting by district population) and that there is no notion of
the value of a project to a specific district. The literature contains a
variety of algorithms for solving this NP-hard problem (e.g., Yamada and
Futakawa 1997; Yamada, Futakawa, and Kataoka 1998; Hifi, M’Halla, and Sadfi
2005; Fujimoto and Yamada 2006).

##  2 Formal Problem, Notation and Definitions

Formally, the setting we consider is as follows. We are given a budget
$b\in\mathbb{Z}_{\geqslant 1}$. There are $m$ possible projects
$\mathcal{P}=\\{x_{1},\ldots,x_{m}\\}$ with associated nonnegative costs
$c:\mathcal{P}\to\mathbb{Z}_{\geqslant 0}$. We refer to a subset
$W\subseteq\mathcal{P}$ as an _outcome_. The cost of an outcome $W$ is
$c(W)\coloneqq\sum_{x_{j}\in W}c(x_{j})$. We say that a subset $W$ is _budget-
feasible_ if $c(W)\leqslant b$.

There are $k$ districts $d_{1},\ldots,d_{k}$. The _social welfare_ (or
_utility_) that project $x_{j}$ provides to district $d_{i}$ is
$\textup{sw}_{i}(x_{j})\in\mathbb{Z}_{\geqslant 0}$. We assume that utilities
are additive; i.e., the utility that an outcome $W\subseteq\mathcal{P}$
provides to district $d_{i}$ is $\textup{sw}_{i}(W):=\sum_{x_{j}\in
W}\textup{sw}_{i}(x_{j})$. Furthermore, the total social welfare of
$W\subseteq\mathcal{P}$ is
$\textup{sw}(W)\coloneqq\sum_{i\in[k]}\textup{sw}_{i}(W)$.

Throughout this work we assume that $\textup{sw}(x_{j})$ and $c(x_{j})$ are
both $\text{poly}(k,m)$ for each $j$. (A function $f$ is $\text{poly}(x,y)$ if
there exists a $k\geqslant 0$ such that $f=O((xy)^{k})$.) We can relax this
assumption using well-known bucketing techniques at the cost of an arbitrarily
small $\varepsilon$ in the guarantees of our algorithms. See the fully
polynomial time approximation scheme for the knapsack problem (Chekuri and
Khanna 2005) for an example of this technique.

To model the participatory budgeting setting, we assume that each district
deserves some portion of the budget and, in turn, deserves at least the
utility it could achieve if it spent its budget on its most preferred
projects. Specifically, each district $d_{i}$ deserves some budget
$b_{i}\geqslant 0$ where $\sum_{i}b_{i}=b$. District $d_{i}$ deserves utility
$f_{i}:=\textup{sw}_{i}(W_{i})$, where
$W_{i}:=\operatorname*{arg\,max}_{W:c(W)\leqslant b_{i}}\textup{sw}_{i}(W)$ is
$d_{i}$’s favorite outcome costing at most $b_{i}$.

######  Definition 1 (District-Fair Outcome).

We say that an outcome $W$ is district-fair (DF) if
$\textup{sw}_{i}(W)\geqslant f_{i}$ for all $i$.

Computing $f_{i}$ is precisely an instance of the knapsack problem; by our
assumption that utilities and costs are polynomially bounded, this knapsack
instance is solvable in polynomial time (Chekuri and Khanna 2005). Thus, we
will assume $f_{i}$ is known.

Note that the outcome $\bigcup_{i}W_{i}$ is both budget-feasible and district-
fair, so an outcome with both properties always exists. Our goal is to find a
budget-feasible and district-fair outcome $W$ which maximizes social welfare
$\textup{sw}(W)$. We call our problem _district-fair welfare maximization_.
Throughout this paper, we let
$W^{*}:=\operatorname*{arg\,max}_{W}\textup{sw}(W)$ be some optimal solution,
where the argmax is taken over budget-feasible and district-fair solutions.
Similarly, we let $\operatorname*{\textup{OPT}}:=\textup{sw}(W^{*})$.

We consider two relaxations of district fairness. The first relaxation extends
the concept to _lotteries_ over outcomes. We require that each district only
needs to be approximately satisfied in expectation. We give an efficient
algorithm to compute optimal district-fair lotteries in Section 4.

######  Definition 2 ($\varepsilon$-District-Fair Lottery).

Given $\varepsilon>0$, we say that a probability distribution $\mathcal{W}$
over outcomes of cost at most $b$ is an $\varepsilon$-district-fair
($\varepsilon$-DF) lottery if
$E_{W\sim\mathcal{W}}[\textup{sw}_{i}(W)]\geqslant f_{i}-\varepsilon$ for
every district $d_{i}$.

The second relaxation is _district-fairness up to one good_ (DF1).
Intuitively, an allocation is DF1 if each district would be satisfied if one
additional project was funded.

######  Definition 3 (DF1).

An outcome $W$ is _DF1_ if for every $d_{i}$,

$\textup{sw}_{i}(W)+\max_{x_{j}\in(\mathcal{P}\setminus
W)}\textup{sw}_{i}(x_{j})\geqslant f_{i}.$

DF1 is inspired by the well-studied notion of EF1 (envy-freeness up to one
good) from the private goods setting (Budish 2011). This relaxation is mild,
and unlike relaxations that require district-fairness to hold on average over
districts, it is a _uniform_ relaxation which provides guarantees for all
districts. We study DF1 outcomes in Section 5.

##  3 NP-Hardness

Our first result shows that the problem of optimizing social welfare subject
to district-fairness is NP-hard even in the restricted setting of approval
votes (i.e., voters provide binary yes/no opinions over projects) and budgets
proportional to district sizes. In fact, our problem remains NP-hard in this
restricted setting even when each district contains only one voter and
projects have unit costs.

We reduce from exact 3-cover (X3C), which is known to be NP-hard (Garey and
Johnson 1979). The idea of our reduction is as follows. Given an instance of
X3C, we define a district for each of the elements in the universe, and then
add a large amount of dummy districts. We then define a project for each set
in our problem instance which gives one utility to the districts corresponding
to the elements which it covers. We also define a large set of dummy projects
that are approved by all dummy districts. We then ask whether there exists a
district-fair outcome that attains high social welfare. An optimal solution
for our district-fair welfare maximization problem, then, will first try to
solve the X3C instance as efficiently as possible so that it can spend as much
of its budget as possible on high-utility dummy projects. We formalize this
idea in the following proof.

######  Theorem 1.

It is NP-complete to decide, given an instance of district-fair welfare
maximization and an integer $M$, whether there exists a budget-feasible and
district-fair outcome $W$ such that $\textup{sw}(W)\geqslant M$. NP-hardness
holds even in the restricted setting of approval votes and budgets
proportional to district sizes, and when each district contains one voter and
all projects have unit cost.

###### Proof.

The stated problem is trivially in NP. For NP-hardness we reduce from X3C. In
an instance of X3C, we are given a universe $U=\\{e_{1},\dots,e_{3n}\\}$ and a
collection $\\{S_{1},\dots,S_{m}\\}$ of 3-element subsets of $U$. It is a
“yes”-instance if there exists a selection $S_{j_{1}},\dots,S_{j_{n}}$ such
that $S_{j_{1}}\cup\dots\cup S_{j_{n}}=U$.

Given an instance of X3C, we construct an instance of our problem as follows.
Let $M=3mn+1$. We have $3n+M$ districts, $D\cup D^{\prime}$. Let
$D=\\{d_{1},\dots,d_{3n}\\}$, where each $d_{i}$ in $D$ corresponds to element
$e_{i}$. Additionally, let $D^{\prime}=\\{d_{3n+1},\ldots d_{3n+M}\\}$, where
each $d_{i}\in D^{\prime}$ is a dummy district. We have $m+2n+M$ projects,
$X\cup X^{\prime}$. Let $X=\\{x_{1},\dots,x_{m}\\}$, where $x_{j}\in X$
corresponds to set $S_{j}$, and let
$X^{\prime}=\\{x_{m+1},\dots,x_{m+2n+M}\\}$, where each $x_{j}\in M^{\prime}$
is a dummy project. Utilities are as follows: every dummy district approves
every dummy project, so $\textup{sw}_{i}(x_{j})=1$ for each $i\geqslant 3n+1$
and $x_{j}\in X^{\prime}$. Also, each non-dummy district approves of non-dummy
sets to reflect the structure of the X3C instance: that is, for each
$i\leqslant 3n$ we have $\textup{sw}_{i}(x_{j})=1$ if $x_{j}\in X$ and
$e_{i}\in S_{j}$. All other utilities are 0: that is,
$\textup{sw}_{i}(x_{j})=0$ for all other $i$ and $j$. Each project has cost 1,
and our budget is $b=3n+M$. We assume all districts contain 1 voter, so
$b_{i}=1$ for every district $d_{i}$. Clearly, $f_{i}=1$ for each $i$. We ask
whether there exists a district fair committee with social welfare at least
$3n+(2n+M)M$.

If there exists a solution $S_{j_{1}},\dots,S_{j_{n}}$ to the X3C instance,
then $W=\\{x_{j_{1}},\dots,x_{j_{n}}\\}\cup X^{\prime}$ is an outcome with
cost $n+(2n+M)=3n+M=b$. Clearly, $W$ is district-fair, and its social welfare
is $3n+(2n+M)M$, so this is a “yes”-instance for the district-fair welfare-
maximization problem.

Conversely suppose that there exists a district-fair budget-feasible outcome
$W$ with social welfare at least $3n+(2n+M)M$. Note that all projects in $X$
together give overall welfare at most $3mn<M$. Thus, we must have
$X^{\prime}\subseteq W$ since otherwise the total welfare of $W$ is less than
$(2n+M)M$. Hence $|X\cap W|\leqslant n$. By district-fairness, for each
$i=1,\dots,3n$, there must be some $x_{j}\in W$ such that $e_{i}\in S_{j}$.
These two facts together imply that $\\{S_{j}:x_{j}\in W\\}$ is a solution to
the X3C instance. ∎

This NP-hardness result holds even if each district consists of a single voter
and all projects have unit cost. As we show in Appendix A in the supplementary
material, this special case admits a polynomial-time
$\frac{1}{2}$-approximation. Our algorithm is based on a greedy algorithm and
a combinatorial argument which “matches away” high utility goods of the
optimal solution. One might hope to achieve an approximation result for the
general case. A natural approach would be to round the optimal solution to the
LP relaxation of the natural ILP formulation of our problem. However, a simple
example in Appendix B in the supplementary material shows that the integrality
gap of that formulation is unboundedly large, so this approach will not work.

##  4 Optimal District-Fair Lottery

In this section, we allow randomness and consider lotteries over outcomes. Our
main result for the lottery setting is an $\varepsilon$-DF lottery which
always achieves the optimal social welfare subject to district fairness. The
welfare guarantee is ex post, so that every outcome in the lottery’s support
achieves optimal welfare. For the remainder of this section we let
$\varepsilon>0$ refer to the $\varepsilon$ in the $\varepsilon$-DF definition.

######  Theorem 2.

There is an algorithm which, in
$\text{poly}\left(m,k,\frac{1}{\varepsilon}\right)$ time, returns an
$\varepsilon$-DF lottery $\mathcal{W}$ such that for all outcomes $W$ in the
support of $\mathcal{W}$, we have
$\textup{sw}(W)\geqslant\operatorname*{\textup{OPT}}$.

The intuition for our algorithm is as follows. We begin by showing that our
problem is polynomial-time solvable if the number of districts $k$ is
constant. Such an algorithm is useful because we can artificially make the
number of districts constant by convexly combining all districts into a single
district $\tilde{d}$. We can, then, compute as our solution a utility-optimal
outcome $W$ which is fair for $\tilde{d}$ but not necessarily fair for each
$d_{i}$ individually. However, we can bias our solution to try and satisfy
fairness for certain districts by increasing the weights of these districts in
our convex combination. Thus, if $W$ is not fair for $d_{i}$, we might
naturally increase the proportional share of $d_{i}$ in the convex combination
and recompute $W$ in the hopes that the new outcome we compute will be fair
for $d_{i}$. We obtain our lottery by repeatedly increasing the weight of
districts that do not have their fairness constraint satisfied, and then take
a uniform distribution over the resulting outcomes.

Turning to the proof, we begin by describing how to solve our problem in
polynomial time when $k$ is a constant. Our algorithm will solve the natural
dynamic program (DP). Specifically, consider the true/false value
$R(\textup{sw}^{(1)},\ldots,\textup{sw}^{(k)},j,b)$ which is the answer to the
question, “Does there exists an outcome of cost at most $b$ using projects
$x_{1},x_{2},\ldots,x_{j}$ wherein district $d_{i}$ achieves social welfare at
least $\textup{sw}^{(i)}$?” If the answer to this question is yes, then either
the desired utilities are possible with the stated budget without using
$x_{j}$ or there is an outcome which uses at most $b-c(x_{j})$ budget that
doesn’t use $x_{j}$ in which every district gets at least its specified
utility minus how much it values $x_{j}$. Thus,
$R(\textup{sw}^{(1)},\ldots,\textup{sw}^{(k)},j,b)$ is true if and only if
either $R(\textup{sw}^{(1)},\ldots,\textup{sw}^{(k)},j-1,b)$ is true or
$R(\textup{sw}^{(1)}-\textup{sw}_{1}(x_{j}),\ldots,\textup{sw}^{(k)}-\textup{sw}_{k}(x_{j}),j-1,b-c(x_{j}))$
is true, giving us a definition by recurrence.

By our assumption that all costs and utilities are polynomially bounded, we
can easily solve the dynamic program (DP) for the above recurrence, giving the
following result.

######  Lemma 3.

There is an algorithm that finds a budget-feasible district-fair outcome $W$
with $\textup{sw}(W)=\operatorname*{\textup{OPT}}$ in $m^{O(k)}$ time.

###### Proof.

Our algorithm simply fills in the DP table and returns the outcome
corresponding to the entry in our DP table which is true, satisfies
$\textup{sw}^{(i)}\geqslant f_{i}$ for all $i$ and which maximizes
$\sum_{i}\textup{sw}^{(i)}$. The recurrence is correct by the above reasoning.

To see why we can fill in the DP table in the stated time, note that we can
trivially solve our base case,
$R(\textup{sw}^{(1)},\ldots,\textup{sw}^{(k)},j,1)$, for each $j$ and possible
value for each $\textup{sw}^{(i)}$ in polynomial time. Since
$\max_{i,j}\textup{sw}_{i}(x_{j})$ is polynomially bounded in $m$, we need
only check polynomially-many in $m$ values for each $\textup{sw}^{(i)}$.
Lastly, since $j$ and $b$ are bounded by a polynomial in $m$, we conclude that
our DP table has $m^{O(k)}$ entries, giving the desired runtime. ∎

We now describe our multiplicative-weights-type algorithm to produce our
lottery using the above algorithm.444We will only need to invoke the above
algorithm for the case $k=1$. This amounts to solving the knapsack problem
with a single covering constraint, which to our knowledge is not one of the
standard variants of the knapsack problem. We let $w_{i}^{(t)}\geqslant 0$ be
the “weight” of district $i$ in iteration $t$ and let
$w^{(t)}:=\sum_{i}w_{i}^{(t)}$ be the total weight in iteration $t$.
Initially, our weights are uniform: $w_{i}^{(1)}=1$ for all $i$.

For any iteration $t$ and district $d_{i}$ we let
$p_{i}^{(t)}:=\frac{w_{i}^{(t)}}{w^{(t)}}$ be the proportion of the weight
that district $i$ has in iteration $t$. These $p_{i}^{(t)}$ will induce our
convex combination over districts; in particular we let $\tilde{d}^{(t)}$ be a
district which values project $x_{j}$ to extent
$\tilde{\textup{sw}}^{(t)}(x_{j}):=\sum_{i}p_{i}^{(t)}\cdot\textup{sw}_{i}(x_{j})$
and which deserves $\tilde{f}^{(t)}:=\sum_{i}p_{i}^{(t)}\cdot f_{i}$ utility.
Also, let $\textup{sw}_{\max}$ be the maximum welfare of an outcome.

With the above notation in hand, we can give our instantiation of
multiplicative weights where $T:=\frac{4\ln
k}{\varepsilon^{2}}\cdot\textup{sw}_{\max}^{2}$ is the number of iterations of
our algorithm.

  1. 1.

For all iterations $t\in[T]$:

    1. (a)

Let $W_{t}$ be an outcome that maximizes $\textup{sw}(W_{t})$ subject to
$\tilde{\textup{sw}}^{(t)}(W_{t})\geqslant\tilde{f}^{(t)}$ and
$c(W_{t})\leqslant b$. We can compute $W_{t}$ using Lemma 3.

    2. (b)

Let $m_{i}^{(t)}:=\textup{sw}_{i}(W_{t})-f_{i}$ be our “mistakes”, indicating
how far off a district was from getting what it deserved.

    3. (c)

Update weights: $w_{i}^{(t+1)}\leftarrow w_{i}^{(t)}\cdot\exp(-\varepsilon
m_{i}^{(t)})$.

  2. 2.

Return lottery $\mathcal{W}$, the uniform distribution over $\\{W_{t}\\}_{t}$.

We now restate the usual multiplicative weights guarantee in terms of our
algorithm. This lemma guarantees that, on average, the multiplicative weights
strategy is competitive with the best “expert.” In the following $\langle
p^{(t)},m^{(t)}\rangle:=\sum_{i}p^{(t)}_{i}\cdot m_{i}^{(t)}$ is the usual
inner product.

######  Lemma 4 (Arora, Hazan, and Kale 2012).

For all $i$ we have

$\displaystyle\frac{1}{T}\sum_{t\leqslant T}\langle
p^{(t)},m^{(t)}\rangle\leqslant\varepsilon+\frac{1}{T}\sum_{t\leqslant
T}m_{i}^{(t)}.$

We can use this lemma to show the desired guarantees.

###### Proof of Theorem 2.

We use the algorithm described above.

Our algorithm is polynomial time since it runs for polynomially-many
iterations and in each iteration we compute a solution for a problem on only
one district which is solvable in polynomial time by Lemma 3. Also, note that
by Lemma 3 we know that $c(W_{t})\leqslant b$ for all $t$, so all outcomes in
the lottery are budget-feasible.

We now argue that the above lottery is utility-optimal. Fix an iteration $t$.
Notice that since $W^{*}$ is fair for all districts then it is fair for
$\tilde{d}^{(t)}$. In particular,

$\displaystyle\tilde{\textup{sw}}^{(t)}(W^{*})=\sum_{i}p_{i}\cdot\textup{sw}_{i}(W^{*})\geqslant\sum_{i}p_{i}f_{i}=\tilde{f}^{(t)}$

Thus, $W^{*}$ is a budget-feasible solution for the problem of finding a max-
utility outcome which is fair for $\tilde{d}^{(t)}$. Thus,
$\textup{sw}(W_{t})$ can only be larger than $\textup{sw}(W^{*})$, meaning
that $\textup{sw}(W_{t})\geqslant\operatorname*{\textup{OPT}}$.

We now argue that the above lottery is $\varepsilon$-DF in expectation. Fix a
district $d_{i}$. By Lemma 4 we know that

$\displaystyle\frac{1}{T}\sum_{t\leqslant T}\langle
p^{(t)},m^{(t)}\rangle\leqslant\varepsilon+\frac{1}{T}\sum_{t\leqslant
T}m_{i}^{(t)}.$ (1)

Now notice that by definition of $m_{i}^{(t)}$ and since our lottery is
uniform over all $W_{t}$ we know that the right-hand-side of Equation 1 is

$\displaystyle\varepsilon+\frac{1}{T}\sum_{t\leqslant T}m_{i}^{(t)}$
$\displaystyle=\varepsilon+\frac{1}{T}\sum_{t}(\textup{sw}_{i}(W_{t})-f_{i})$
$\displaystyle=\varepsilon-f_{i}+\frac{1}{T}\sum_{t}\textup{sw}_{i}(W_{t})$
$\displaystyle=\varepsilon-
f_{i}+\mathop{{}\mathbb{E}}_{W\sim\mathcal{W}}[\textup{sw}_{i}(W)]$

Thus, to show that
$f_{i}-\varepsilon\leqslant\mathop{{}\mathbb{E}}_{W\sim\mathcal{W}}[\textup{sw}_{i}(W)]$,
it suffices to show that the left-hand side of Equation 1 is at least $0$.
That is, we must show $0\leqslant\frac{1}{T}\sum_{t\leqslant T}\langle
p^{(t)},m^{(t)}\rangle$. However, this amounts to simply showing that $W_{t}$
is fair for $\tilde{d}^{(t)}$; in particular, we have that the left-hand-side
is

$\displaystyle\frac{1}{T}\sum_{t\leqslant T}\langle p^{(t)},m^{(t)}\rangle$
$\displaystyle=\frac{1}{T}\sum_{t\leqslant
T}\sum_{i}p^{(t)}_{i}\cdot(\textup{sw}_{i}(W_{t})-f_{i})$
$\displaystyle=\frac{1}{T}\sum_{t\leqslant
T}\tilde{\textup{sw}}^{(t)}(W_{t})-{\tilde{f}^{(t)}}.$

It holds that $\tilde{sw}^{(t)}(W_{t})-\tilde{f}^{(t)}\geqslant 0$ since we
always choose a solution which is fair for $\tilde{d}^{(t)}$, and so we
conclude that the left-hand-side of Equation 1 is at least $0$. ∎

##  5 Optimal DF1 Outcome with Extra Budget

We now study how well we can do if we allow ourselves to overspend the
available budget. Certainly it is possible to achieve district fairness and
optimal fairness-constrained utility $\operatorname*{\textup{OPT}}$ if the
algorithm can spend _double_ the available budget: we can compute an outcome
$W_{1}$ with $c(W_{1})\leqslant b$ that is welfare-maximizing without
attempting to satisfy district-fairness, and we can compute some outcome
$W_{2}$ with $c(W_{2})\leqslant b$ that is district-fair (see Section 2); then
$W_{1}\cup W_{2}$ satisfies district fairness and we clearly have $c(W_{1}\cup
W_{2})\leqslant 2b$ and $\textup{sw}(W_{1}\cup
W_{2})\geqslant\operatorname*{\textup{OPT}}$. In this section, we show that we
can find a solution that requires less than twice the budget, if we slightly
relax the district fairness requirement to DF1. Our main result for the DF1
setting shows that, under DF1 fairness, there is a deterministic algorithm
which achieves DF1 and optimal social welfare if one overspends a $0.647$
fraction of the budget.

######  Theorem 5.

For any constant $\varepsilon>0$, there is a $\text{poly}(m,k)$-time algorithm
which, given an instance of district-fair welfare maximization, returns an
outcome $W$ such that $W$ is DF1,
$c(w)\leqslant\left(1.647+\varepsilon\right)b$, and
$\textup{sw}(W)\geqslant(1-\varepsilon)\operatorname*{\textup{OPT}}$.

Overspending by 64.7% is a worst-case result, and the algorithm may often
overspend less. If the context does not permit any overspending, one can run
the same algorithm with a reduced budget; then the output will be feasible for
the true budget, yet will satisfy weaker fairness and social welfare
guarantees. More precisely, given an instance $\mathcal{I}$ and a multiplier
$\beta<1$, we define an instance $\mathcal{I}^{\prime}(\beta)$, which is
identical to $\mathcal{I}$ but in which each district $d_{i}$ contributes only
$\beta\cdot b_{i}$ and thus deserves utility
$f_{i}^{\prime}\coloneqq\textup{sw}_{i}(W_{i}^{\prime})$, where
$W_{i}^{\prime}$ is $d_{i}$’s favorite outcome which costs at most $\beta\cdot
b_{i}$. Additionally, let $\operatorname*{\textup{OPT}}^{\prime}(\beta)$
represent the maximum achievable social welfare over all district-fair
solutions in $\mathcal{I}^{\prime}$ using a budget of at most
$b^{\prime}\coloneqq\beta\cdot b$. Then, applying Theorem 5 to
$\mathcal{I}^{\prime}(\beta)$ results in an outcome which is DF1 and utility-
optimal on this reduced instance and does not overspend the original budget
$b$.

######  Corollary 6.

For any constant $\varepsilon>0$, there is a $\text{poly}(m,k)$-time algorithm
which, given an instance $\mathcal{I}$ of district-fair welfare maximization,
returns an outcome $W$ such that $W$ is DF1 for
$\mathcal{I}^{\prime}(\frac{1}{1.647})$,
$c(W)\leqslant\left(1+\varepsilon\right)b$, and
$\textup{sw}(W)\geqslant(1-\varepsilon)\operatorname*{\textup{OPT}}^{\prime}(\frac{1}{1.647})$.

Our result uses a submodular optimization as a subroutine. If one allows
randomization in this subroutine, algorithms with better approximation ratios
are known. Thus, we can prove a similar theorem (and corollary) with a
_randomized_ algorithm which achieves DF1 and optimal social welfare while
overspending its budget by only a $\frac{1}{e}\approx.37$ fraction of the
budget, with high probability (i.e., with probability $1-\frac{1}{p(m,k)}$
where $p(m,k)$ is some polynomial in $m$ and $k$). We defer details of our
randomized algorithm to Appendix C in the supplementary material.

In the remainder of this section, we will prove Theorem 5. Our main tool is a
notion of the “coverage” of a partial outcome. An outcome has high coverage if
we do not need to spend much more money to make it district-fair. On a high
level, our proof consists of two main steps. First, we show how to complete an
outcome with good coverage into a DF1 outcome. Second, we will show how to
frame the problem of finding a solution with good coverage and social welfare
as a submodular maximization problem subject to linear constraints, allowing
us to use a result by Mizrachi et al. (2018).

We begin by formalizing the coverage of a solution. Roughly, if we imagine
that initially every district requires its portion of the budget for fairness,
then fractional coverage captures how much less districts must spend to
satisfy their own fairness constraints. Thus, if we imagine that our algorithm
first spends its budget to satisfy fairness as efficiently as possible, and
then spends the remainder of its budget on the highest utility projects, then
the coverage of a collection of projects is roughly how much budget this
collection “frees up” for the algorithm to spend on the highest utility
projects. More formally, we define coverage by way of the notions of
fractional outcomes and residual budget requirements.

######  Definition 4 (fractional outcomes).

A fractional outcome is a vector $p\in\mathbb{R}^{m}$ where $0\leqslant
p_{j}\leqslant 1$. We overload notation and let the social welfare of $p$ for
district $d_{i}$ be $\textup{sw}_{i}(p):=\sum_{j}\textup{sw}_{i}(x_{j})\cdot
p_{j}$. Similarly the social welfare of $p$ is $\sum_{i}\textup{sw}_{i}(p)$.
Lastly, we define the cost of $p$ as $\sum_{j}c(x_{j})\cdot p_{j}$.

We now define the residual budget requirement of a district, given an outcome,
which can be understood as the minimum amount of additional money that must be
spent to satisfy the district, if fractional outcomes are allowed.

######  Definition 5 ($\text{resid}_{i}(W)$).

The residual budget requirement of district $d_{i}$ given (integral) outcome
$W$ is the minimum cost of a fractional outcome $p$ such that
$\textup{sw}_{i}(W)+\textup{sw}_{i}(p)\geqslant f_{i}$ and $p_{j}=0$ for all
$x_{j}\in W$.

We can now define the coverage of an outcome for a particular district $i$ in
terms of the total amount of budget they deserve and their residual budget
requirement.

######  Definition 6 ($\textup{cover}_{i}(W)$).

The coverage of an outcome $W$ for district $d_{i}$ is the difference between
the amount of budget they deserve, $b_{i}$, and their residual budget
requirement: $\textup{cover}_{i}(W):=b_{i}-\text{resid}_{i}(W)$.

Lastly, we define the coverage of an outcome.

######  Definition 7 ($\textup{cover}(W)$).

The overall coverage of an outcome $W$ is the sum over all districts $d_{i}$
of the coverage $W$ affords $d_{i}$:
$\textup{cover}_{i}(W):=\sum_{i}\textup{cover}_{i}(W)$.

Next, we establish a useful property of DF1 solutions. In particular, given a
set of projects that achieves relatively good fairness on _average_ , we can
then buy a small subset of projects that results in fairness up to one good
for all districts. In particular, given a collection of projects that covers a
$1-\beta$ fraction of all fairness constraints, we can use at most an extra
$\beta$ fraction of our budget in order to complete this to a DF1 solution.
Moreover, this completion is quite intuitive: purchase all projects whose
total coverage exceed their cost, until there are no such projects remaining.

Formally, we state the following _DF1 completion_ lemma.

######  Lemma 7 (DF1 Completion).

Given an outcome $W$ with $\textup{cover}(W)=b-r$, one can compute in
polynomial time a set $W^{\prime}\supseteq W$ such that $W^{\prime}$ is DF1
and $c(W^{\prime})\leqslant c(W)+r$.

###### Proof.

We first prove that for every non-DF1 outcome $W$, there exists a project that
we can add to $W$ which increases its coverage by at least $c(x_{j})$. Suppose
that $W$ is an outcome that fails DF1, and let $d_{i}$ be a district such that
$\textup{sw}_{i}(W)+\textup{sw}_{i}(x_{j})<f_{i}$ for all $x_{j}\not\in W$.
Let $p$ be the fractional outcome witnessing $\text{resid}_{i}(W)$; thus
$\textup{sw}_{i}(W)+\textup{sw}_{i}(p)\geqslant f_{i}$. We may assume without
loss of generality that all but at most one project is integral in $p_{j}$
(because there is always some optimal $p$ with this property by additivity of
$\textup{sw}_{i}$). Since $W$ fails DF1 for $d_{i}$, there is some
$x_{j}\not\in W$ such that $p(x_{j})=1$. Then
$\text{resid}_{i}(W\cup\\{x_{j}\\})=\text{resid}_{i}(W)-c(x_{j})$ (witnessed
by the fractional outcome obtained from $p$ by removing $x_{j}$ from it).
Thus, from definitions,
$\textup{cover}_{i}(W\cup\\{x_{j}\\})=\textup{cover}_{i}(W)+c(x_{j})$, and
hence $\textup{cover}(W\cup\\{x_{j}\\})\geqslant\textup{cover}(W)+c(x_{j})$.

Now suppose we are given an outcome $W$ with $\textup{cover}(W)=b-r$, which
fails DF1. We can identify a project $x_{j}$ as above, add it to $W$, and
increase the coverage by at least $c(x_{j})$. We repeat this until the outcome
is DF1. This process must stop, since at each step the coverage increases by
$c(x_{j})$ but by definition the coverage can never exceed $b$. For the same
reason, the cost of the projects we have added to $W$ cannot exceed $r$, and
thus $c(W^{\prime})\leqslant c(W)+r$. ∎

With this lemma in hand, we now turn to the problem of finding high-coverage
outcomes with good welfare. Let $B\geqslant 0$ be a lower bound on the social
welfare we desire. We rephrase our problem as an optimization problem in which
we maximize the coverage of an outcome subject to a linear knapsack constraint
and a linear covering constraint. The knapsack constraint enforces budget
feasibility, and the covering constraint encodes the requirement that the
total utility of the outcome is at least $B$.

$\begin{split}\max_{W\subseteq\mathcal{P}}&\,\,\textup{cover}(W)\\\ \text{s.t.
}&\textup{sw}(W)\geqslant B,\\\ &\>\>\>c(W)\leqslant b.\end{split}$ (DF1P)

The main tool we apply is a theorem on the maximization of nondecreasing
submodular functions of Mizrachi et al. (2018). Recall that a set function is
nondecreasing if its value never decreases as elements are added to its input,
and submodular if it exhibits diminishing returns.

######  Definition 8.

Given a finite set $\Omega$, a set function $f:\Omega\to\mathbb{R}_{\geqslant
0}$ is _nondecreasing_ and _submodular_ if for every $A,B\subseteq\Omega$ such
that $A\subseteq B$ we have $f(A)\leqslant f(B)$ and
$f(A\cup\\{x\\})-f(A)\geqslant f(B\cup\\{x\\})-f(B)$ for all
$x\in\Omega\setminus B$.

The theorem we apply is as follows.

######  Theorem 8 (Mizrachi et al. 2018, Theorem 5).

For each constant $\varepsilon>0$, there exists a deterministic algorithm for
maximizing a nondecreasing submodular function subject to one packing
constraint and one covering constraint that runs in time $O(n^{O(1)})$, where
$n=|\Omega|$ is the size of the support of the set function, satisfies the
covering constraint up to a factor of $1-\varepsilon$ and the packing
constraint up to a factor of $1+\varepsilon$, and achieves an approximation
ratio of $0.353$.

We apply this theorem to find a solution that satisfies a $0.353$ fraction of
coverage and achieves optimal fairness-constrained utility. Then, we apply
Lemma 7 to augment our solution using an additional $1-0.353+\varepsilon$
fraction of our budget in order to obtain a final solution which satisfies
full DF1. However, in order to apply Theorem 8, we must first establish that
$\textup{cover}(W)$ is a nondecreasing submodular function. In particular,
note that the coverage functions $\textup{cover}_{i}(W)$ for each district are
clearly nondecreasing and submodular. It follows that their sum,
$\textup{cover}(W)$ is also nondecreasing and submodular, yielding the
following lemma.

######  Lemma 9.

The function $\textup{cover}(W)$ is nondecreasing and submodular.

We are now ready to prove Theorem 5, which applies the DF1 completion lemma to
an approximately optimal solution for the problem DF1P.

###### Proof of Theorem 5.

Recall that we have assumed that the maximum utility of an outcome is
polynomially bounded in $m$ and $k$ and that the maximum utility is integral.
Thus, the value of $\operatorname*{\textup{OPT}}$ falls in a polynomial range.
For each value $B$ in this range, solve the problem DF1P using the algorithm
from Theorem 8. Now consider all values of $B$ for which the algorithm
returned a solution with $\textup{cover}(W)\geqslant 0.353b$; such a value
must exist since we are guaranteed this condition when
$B=\operatorname*{\textup{OPT}}$ (since for this value, the optimum of problem
(DF1P) is $b$). Among all solutions we found that satisfy
$\textup{cover}(W)\geqslant 0.353b$, take the one that maximizes
$\textup{sw}(W)$. This solution provides social welfare at least
$(1-\varepsilon)\operatorname*{\textup{OPT}}$.

We have obtained an outcome $W$ with

$\textup{cover}(W)\geqslant 0.353b=b-0.647b,$

and $\textup{sw}(W)\geqslant(1-\varepsilon)\operatorname*{\textup{OPT}}$ and
$c(W)\leqslant(1+\varepsilon)b$. Now apply Lemma 7 to $W$ to obtain a DF1
outcome $W^{\prime}\supseteq W$ with

$c(W^{\prime})\leqslant c(W)+0.647b\leqslant(1+0.647+\varepsilon)b.$

This outcome $W^{\prime}$ satisfies the requirements of Theorem 5. ∎

##  6 Discussion

Our results extend to the special case of unit costs, also known as committee
selection. In committee selection, we elect a committee to represent voters in
a larger governmental body such as a parliament. Often, to ensure local
representation, the electorate is split into voting districts, which elect
their representatives separately. The districts may be apportioned different
numbers of representatives, for example based on district size. While this
scheme guarantees each district representation, it may well be possible to
increase the welfare of the voters in a district, for example by electing a
diverse array of candidates with expertise in various areas who can gather
votes from across the electorate. Thus, it is natural for all districts to
elect the committee together if we impose district-fairness constraints. This
way, we can maximize social welfare of the final committee while guaranteeing
each district fair representation. This gives a more holistic view of
committee selection in exactly the same way we addressed participatory
budgeting, only instead of pooling the budget between districts, we now pool
seats on a committee.

Our model implicitly treats districts as atoms, and so district fairness is a
kind of _individual rationality_ property. In turn, individual rationality is
a type of strategyproofness: it incentivizes districts not to leave the
central election and instead hold a separate one. Is it possible to design a
voting scheme that is fully strategyproof for districts, so that districts do
not have incentives to misreport the utilities of their residents?
Unfortunately not: Peters (2018) proves an impossibility theorem about
committee elections which implies that there does not exist a voting rule that
is efficient, district-fair, and also strategyproof. This result holds even
for approval votes.

Several open questions remain. Most obvious is the question of whether can we
achieve welfare maximization and DF1 in polynomial time while guaranteeing to
overspend the budget by less than $1/e$. More broadly, it would be interesting
to study our problem with more general utility functions such as submodular or
even general monotone valuation functions. Additionally, it would be exciting
to study approximation algorithms which promise full district fairness. In
Appendix B in the supplementary material, we present an algorithm which
satisfies district fairness and provides a $1/2$-approximation to optimal
district-fair social welfare in the special case of unanimous districts; it
would be interesting to extend this result to the general case.

## References

  * Arora, Hazan, and Kale (2012) Arora, S.; Hazan, E.; and Kale, S. 2012.  The multiplicative weights update method: a meta-algorithm and applications.  _Theory of Computing_ 8(1): 121–164.
  * Aziz et al. (2017) Aziz, H.; Brill, M.; Conitzer, V.; Elkind, E.; Freeman, R.; and Walsh, T. 2017.  Justified Representation in Approval-Based Committee Voting.  _Social Choice and Welfare_ 48(2): 461–485.
  * Aziz et al. (2018) Aziz, H.; Elkind, E.; Huang, S.; Lackner, M.; Sánchez-Fernández, L.; and Skowron, P. 2018.  On the Complexity of Extended and Proportional Justified Representation.  In _Proceedings of the 32nd AAAI Conference on Artificial Intelligence (AAAI)_ , 902–909.
  * Aziz and Shah (2020) Aziz, H.; and Shah, N. 2020.  Participatory Budgeting: Models and Approaches.  In Rudas, T.; and Péli, G., eds., _Pathways Between Social Science and Computational Social Science: Theories, Methods, and Interpretations_. Springer.
  * Brill et al. (2017) Brill, M.; Freeman, R.; Janson, S.; and Lackner, M. 2017.  Phragmén’s Voting Methods and Justified Representation.  In _Proceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI)_ , 406–413.
  * Brown (1979) Brown, J. R. 1979.  The knapsack sharing problem.  _Operations Research_ 27(2): 341–355.
  * Budish (2011) Budish, E. 2011.  The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes.  _Journal of Political Economy_ 119(6): 1061–1103.
  * Cabannes (2004) Cabannes, Y. 2004.  Participatory budgeting: a significant contribution to participatory democracy.  _Environment and Urbanization_ 16(1): 27–46.
  * Cabannes (2014) Cabannes, Y. 2014.  Contribution of Participatory Budgeting to provision and management of basic services.  _London: IIED_ .
  * Cabannes (2017) Cabannes, Y. 2017.  Participatory budgeting in Paris: Act, reflect, grow.  _Another city is possible with participatory budgeting_ 179–203.
  * Chekuri and Khanna (2005) Chekuri, C.; and Khanna, S. 2005.  A polynomial time approximation scheme for the multiple knapsack problem.  _SIAM Journal on Computing_ 35(3): 713–728.
  * Cheng et al. (2019) Cheng, Y.; Jiang, Z.; Munagala, K.; and Wang, K. 2019.  Group fairness in committee selection.  In _Proceedings of the 20th ACM Conference on Economics and Computation (ACM EC)_ , 263–279.
  * Fain, Goel, and Munagala (2016) Fain, B.; Goel, A.; and Munagala, K. 2016.  The core of the participatory budgeting problem.  In _Proceedings of the 12th International Conference on Web and Internet Economics (WINE)_ , 384–399.
  * Fain, Munagala, and Shah (2018) Fain, B.; Munagala, K.; and Shah, N. 2018.  Fair Allocation of Indivisible Public Goods.  In _Proceedings of the 19th ACM Conference on Economics and Computation (ACM EC)_ , 575–592.  Extended version arXiv:1805.03164.
  * Faliszewski et al. (2017) Faliszewski, P.; Skowron, P.; Slinko, A.; and Talmon, N. 2017.  Multiwinner Voting: A New Challenge for Social Choice Theory.  In Endriss, U., ed., _Trends in Computational Social Choice_ , chapter 2.
  * Fujimoto and Yamada (2006) Fujimoto, M.; and Yamada, T. 2006.  An exact algorithm for the knapsack sharing problem with common items.  _European Journal of Operational Research_ 171(2): 693–707.
  * Garey and Johnson (1979) Garey, M. R.; and Johnson, D. S. 1979.  _Computers and intractability_ , volume 174.  Freeman San Francisco.
  * Goel et al. (2019) Goel, A.; Krishnaswamy, A. K.; Sakshuwong, S.; and Aitamurto, T. 2019.  Knapsack voting for participatory budgeting.  _ACM Transactions on Economics and Computation (TEAC)_ 7(2): 1–27.
  * Hifi, M’Halla, and Sadfi (2005) Hifi, M.; M’Halla, H.; and Sadfi, S. 2005.  An exact algorithm for the knapsack sharing problem.  _Computers & Operations Research_ 32(5): 1311–1324.
  * Hoeffding (1963) Hoeffding, W. 1963.  Probability inequalities for sums of bounded random variables.  _Journal of the American Statistical Association_ 58(301): 13–30.
  * Janson (2016) Janson, S. 2016.  Phragmén’s and Thiele’s election methods.  Technical report.  ArXiv:1611.08826 [math.HO].
  * Jiang, Munagala, and Wang (2020) Jiang, Z.; Munagala, K.; and Wang, K. 2020.  Approximately stable committee selection.  In _Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC)_ , 463–472.
  * Mizrachi et al. (2018) Mizrachi, E.; Schwartz, R.; Spoerhase, J.; and Uniyal, S. 2018.  A tight approximation for submodular maximization with mixed packing and covering constraints.  arXiv:1804.10947.
  * Peters (2018) Peters, D. 2018.  Proportionality and Strategyproofness in Multiwinner Elections.  In _Proceedings of the 17th International Conference on Autonomous Agents and Multiagent Systems (AAMAS)_ , volume 1549–1557.
  * Peters and Skowron (2020) Peters, D.; and Skowron, P. 2020.  Proportionality and the limits of welfarism.  In _Proceedings of the 21st ACM Conference on Economics and Computation (ACM EC)_ , 793–794.
  * Sánchez-Fernández et al. (2017) Sánchez-Fernández, L.; Elkind, E.; Lackner, M.; Fernández, N.; Fisteus, J. A.; Basanta Val, P.; and Skowron, P. 2017.  Proportional justified representation.  In _Proceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI)_ , 670–676.
  * Talmon and Faliszewski (2019) Talmon, N.; and Faliszewski, P. 2019.  A framework for approval-based budgeting methods.  In _Proceedings of the 33rd Conference on Artificial Intelligence (AAAI)_ , volume 33, 2181–2188.
  * Williamson and Shmoys (2011) Williamson, D. P.; and Shmoys, D. B. 2011.  _The design of approximation algorithms_.  Cambridge University Press.
  * Yamada and Futakawa (1997) Yamada, T.; and Futakawa, M. 1997.  Heuristic and reduction algorithms for the knapsack sharing problem.  _Computers & operations research_ 24(10): 961–967.
  * Yamada, Futakawa, and Kataoka (1998) Yamada, T.; Futakawa, M.; and Kataoka, S. 1998.  Some exact algorithms for the knapsack sharing problem.  _European Journal of Operational Research_ 106(1): 177–183.

##  Appendix A $\frac{1}{2}$-Approximation for Unanimous Districts with Unit
Costs

In this section we study approximation algorithms for the simplest version of
our problem which we know to be NP-hard: when each districts consist of a
single voter and every project has unit cost. In fact, we will study a
strictly more general setting than each district consisting of a single voter;
namely, we study the setting where each district is “unanimous.” Formally, we
study instances of district-fair welfare maximization where $c(x_{j})=1$ for
all $j$ and $\textup{sw}_{i}(x_{j})\in\\{0,|d_{i}|\\}$ for all $i$ where
$|d_{i}|$ is the number of voters in $d_{i}$. For this setting we will give a
$\frac{1}{2}$-approximation.

Our algorithm will make use of the following notion of conditional coverage
which builds on Definition 6.

######  Definition 9.

The coverage of a project $x_{j}$ given an outcome $W$ is
$\textup{cover}(x_{j}|W)\coloneqq\sum_{i}\textup{cover}_{i}(W\cup\\{x_{j}\\})-\textup{cover}_{i}(W)$.

Notice that by our assumption of unit cost and unanimous districts we have
that $\textup{cover}(x_{j}|W)\in\mathbb{Z}_{\geqslant 0}$.

We now present our greedy algorithm that satisfies district fairness and
achieves a $1/2$-approximation to the optimal district-fair utility for the
setting of unanimous districts and unit costs. Formally, the algorithm, which
we call the _Unanimous Greedy Algorithm (UGA)_ proceeds as follows.

  1. 1.

Given an instance $\mathcal{I}$, initialize $W_{0}\leftarrow\emptyset$.

  2. 2.

For $j\in[b]$:

    1. (a)

Let $c_{j}:=\max_{x_{j}}\textup{cover}(x_{j}|W_{j-1})$ be the max possible
coverage and let $X_{j}:=\\{x_{j}:\textup{cover}(x_{j}|W_{j-1})=c_{j}\\}$ be
all projects which achieve this coverage.

    2. (b)

Let $x_{j}\coloneqq\operatorname*{arg\,max}_{x_{j}\in
X_{j}}\textup{sw}(x_{j})$ be the max covering project with maximum utility.

    3. (c)

Update $W_{j}\leftarrow W_{j-1}\cup\\{x_{j}\\}$.

  3. 3.

Return $W_{b}$.

######  Theorem 10.

Given an instance $\mathcal{I}$ consisting of unanimous approval districts,
UGA returns a solution which satisfies district fairness and achieves a
$1/2$-approximation to the optimal district-fair utility.

###### Proof.

Let $W$ represent the result of UGA, and let $W^{*}$ represent the optimal
district-fair outcome. Furthermore, let $N_{2},N_{1}$ and $N_{0}$ be all
projects purchased by UGA that had conditional coverage at least 2, exactly 1
and exactly 0 when purchased by UGA respectively. Clearly $W$ is district-fair
and budget-feasible and so we need only argue that it achieves at least
$\textup{sw}(W^{*})/2$ utility.

Now, consider the following subproblem, which we will call
$\mathcal{I}^{\prime}$, which intuitively is our original instance
$\mathcal{I}$ but where all of $N_{2}$ is forced to be in a solution and no
projects from $N_{0}$ are available. More formally, $\mathcal{I}^{\prime}$ is
$\mathcal{I}$ but where our budget is changed to
$b^{\prime}:=b-|N_{2}|-|N_{0}|$, $f_{i}$ is changed to
$f_{i}^{\prime}:=\max(f_{i}-\textup{sw}_{i}(N_{2}),0)$ for all $i$ and the set
of purchasable projects is $\mathcal{P}^{\prime}:=\mathcal{P}\setminus N_{2}$.
$\textup{sw}_{i}(x_{j})$ is the same for all $i,j$ in $\mathcal{I}^{\prime}$
as in $\mathcal{I}$. Notice that the coverage of any project in
$\mathcal{I}^{\prime}$ is at most $1$ but the total coverage required for
fairness is $b^{\prime}$, meaning that every budget-feasible and district-fair
solution for $\mathcal{I}^{\prime}$ has size exactly $b^{\prime}$. Also notice
that $N_{1}$ is not only feasible for $\mathcal{I}^{\prime}$ but also attains
the optimal utility among all district-fair and budget-feasible solutions.

We claim that there exists a subset $N_{1}^{*}\subseteq W^{*}\setminus N_{2}$
which is district-fair and budget-feasible for $\mathcal{I}^{\prime}$. To see
this, note that we can iteratively build $N_{1}^{*}$ by initializing it to
$\emptyset$ and then repeatedly adding to it any $x_{j}\in W^{*}\setminus
N_{1}^{*}\setminus N_{2}$ such that $\textup{cover}(x_{j}|N_{1}^{*})$ in
$\mathcal{I}^{\prime}$ is at least $1$. After $b^{\prime}$ such additions we
are guaranteed to have a district-fair and budget-feasible solution for
$\mathcal{I}^{\prime}$ and such an $x_{j}$ always exists since $W^{*}\setminus
N_{2}$ is district-fair for $\mathcal{I}^{\prime}$. As noted above, any
district-fair and budget-feasible solution for $\mathcal{I}^{\prime}$ has size
$b^{\prime}$ and so $|N_{1}^{*}|=b^{\prime}$.

Thus, since $N_{1}$ is optimal for $\mathcal{I}^{\prime}$, we know that
$N_{1}$ achieves at least as high utility as $N_{1}^{*}$, i.e.,
$|N_{1}|=|N_{1}^{*}|=b^{\prime}$, and

$\displaystyle\textup{sw}(N_{1}^{*})\leqslant sw(N_{1}).$ (2)

It remains to understand the utility of $W^{*}\setminus N_{1}^{*}$. However,
note that at least half of the projects other than $N_{1}$ must be in the
$N_{0}$ phase. That is, $|N_{0}|\geqslant|N_{2}|/2$. Intuitively, this means
that UGA “frees up” at least $\frac{b-b^{\prime}}{2}$ money to spend on high-
utility projects. Let $\mathcal{P}_{0}:=\mathcal{P}\setminus\\{N_{2}\cup
N_{1}\\}$ be all projects not in $N_{2}$ or $N_{1}$. We have that
$\textup{sw}(N_{0})$ is the utility of the top $\frac{b-b^{\prime}}{2}$
projects in $\mathcal{P}_{0}$. On the other hand, consider projects in
$W^{*}\setminus N_{1}^{*}$. We can divide these into projects which are in
$N_{2}$ and $N_{1}$ and those which are not. In particular, let
$W^{*}_{1,2}:=W^{*}\setminus N_{1}^{*}\cap(N_{1}\cup N_{2})$ and let
$W^{*}_{0}:=W^{*}\setminus N_{1}^{*}\cap\mathcal{P}_{0}$ so that
$W^{*}_{1,2}\cup W^{*}_{0}=W^{*}\setminus N_{1}^{*}$. Now notice that
trivially

$\displaystyle\textup{sw}(W^{*}_{1,2})\leqslant\textup{sw}(N_{1})+\textup{sw}(N_{2}).$
(3)

On the other hand, $|W^{*}_{0}|=b-b^{\prime}-|W^{*}_{1,2}|\leqslant
b-b^{\prime}$ and $W^{*}_{0}\subseteq\mathcal{P}_{0}$ and so
$\textup{sw}(W^{*}_{0})$ is at most the utility of the $b-b^{\prime}$ highest
utility projects in $\mathcal{P}_{0}$. Since our utilities are additive and
$\textup{sw}(N_{0})$ is the utility of the $\frac{b-b^{\prime}}{2}$ highest
utility projects in $\mathcal{P}_{0}$, it follows that

$\displaystyle\textup{sw}(W_{0}^{*})\leqslant 2\cdot\textup{sw}(N_{0}).$ (4)

Since $W^{*}=N_{1}^{*}\cup W_{0}^{*}\cup W_{1,2}^{*}$, we can combine the
above bounds to conclude our $\frac{1}{2}$-approximation. Namely, applying the
additivity of our utilities and combining Equations 2, 3 and 4 we have

$\displaystyle\textup{sw}(W^{*})$
$\displaystyle=\textup{sw}(N_{1}^{*})+\textup{sw}(W_{0}^{*})+\textup{sw}(W_{1,2}^{*})$
$\displaystyle\leqslant
2\cdot\textup{sw}(N_{0})+2\cdot\textup{sw}(N_{1})+\textup{sw}(N_{2})$
$\displaystyle\leqslant 2\cdot\textup{sw}(W)$

and so we conclude that $\textup{sw}(W)\geqslant\frac{\textup{sw}(W^{*})}{2}$.

∎

##  Appendix B Integrality Gap

Here, we investigate the integrality gap of the natural LP for our problem. As
a reminder, the integrality gap of an LP measures how much better a fractional
solution can do than an integral solution. An unbounded integrality gap shows
that any analysis of an approximation algorithm which charges the value of its
integral solution to the value of the optimal LP gives an unboundedely-bad
approximation ratio. For this reason integrality gaps are sometimes taken as
evidence of hardness of approximation. For more details on the topic of
integrality gaps see Williamson and Shmoys (2011).

We will show that our LP has an unbounded integrality gap which suggests that
approximation algorithms which return budget-feasible and district-fair
solutions with nearly-optimal social welfare may be difficult or impossible to
attain for the general case.

Formally our LP and its integrality gap are as follows. Our LP has a variable
$y_{j}$ for each project $x_{j}$ corresponding to the extent to which we
choose $x_{j}$.

$\begin{split}\max&\sum_{j}y_{j}\cdot\textup{sw}(x_{j})\\\ \text{s.t.
}&\sum_{j}y_{j}\cdot c(x_{j})\leqslant b\\\
&\sum_{j}y_{j}\cdot\textup{sw}_{i}(x_{j})\geqslant f_{i}\qquad\forall i\\\
&0\leqslant y_{j}\leqslant 1\qquad\forall j\end{split}$ (DFLP)

We let $\ref{LP:DFLP}(\mathcal{I})$ correspond to the polytope corresponding
to the above LP for an instance $\mathcal{I}$ of district-fair welfare
maximization.

The integrality gap of DFLP is defined as

$\displaystyle\min_{\mathcal{I}}\frac{\max_{y\in\ref{LP:DFLP}(\mathcal{I})\cap\mathbb{Z}^{m}}\sum_{j}y_{j}\cdot\textup{sw}(x_{j})}{\max_{y\in\ref{LP:DFLP}(\mathcal{I})}\sum_{j}y_{j}\cdot\textup{sw}(x_{j})}.$

The basic idea of our integrality gap construction is as follows. We will
construct an instance of social-welfare maximization where the preferences of
each district are “circular”. In particular, each district will like two
projects and every project will be liked by exactly two districts. As in our
NP-hardness proof, we will also have a collection of dummy projects which are
given very high utility by dummy districts which deserve no utility. An
optimal fractional solution will be able to choose each non-dummy project to
extent essentially $\frac{1}{2}$ to satisfy district-fairness and then spend
its remaining budget on high-utility dummy projects. On the other hand, the
optimal integral solution will have to spend its entire budget satisfying
fairness.

######  Theorem 11.

There does not exist a function $f$ such that the integrality gap of DFLP is
at most $\frac{1}{f(k,m)}$. Further, this integrality gap holds even when all
projects have unit cost.

###### Proof.

Fix $k\in\mathbb{Z}_{\geqslant 1}$ and a sufficiently small $\varepsilon>0$.
We define our instance of social-welfare maximization on $k$ districts where
$d_{1},d_{2},\ldots d_{k-1}$ will be non-dummy districts and the district
$d_{k}$ will be a dummy district. Similarly, we will have $2(k-1)$ projects
where $x_{1},x_{2},\ldots,x_{k-1}$ will be non-dummy projects and the
remaining projects $x_{k},\ldots,x_{2(k-1)}$ will be dummy projects.

For each non-dummy district $d_{i}$ we let $b_{i}=1$ and define its utility
for project $x_{j}$ as

$\displaystyle\textup{sw}_{i}(x_{j}):=\begin{cases}1+\varepsilon&\text{if
$j=i$}\\\ 1&\text{if $j=(i+1\text{ mod }k-1)+1$}\\\
0&\text{otherwise}\end{cases}$

For the dummy district $d_{k}$ we let $b_{k}=0$ and define its utility for
project $x_{j}$ as

$\displaystyle\textup{sw}_{k}(x_{j}):=\begin{cases}B&\text{if $x_{j}$ is a
dummy project}\\\ 0&\text{otherwise}\end{cases}$

for $B$ sufficiently large to be chosen later. Notice that
$\textup{sw}(x_{j})=B$ for each dummy project $x_{j}$. Lastly, we let our
budget $b=k-1$ and we let $c(x_{j})=1$ for all $x_{j}$.

Now notice that each non-dummy district $d_{i}$ has $f_{i}=1+\varepsilon$.
Consequently, any district-fair integral solution must include all non-dummy
projects, namely $x_{1},x_{2},\ldots,x_{k-1}$. However, since $b=k-1$, it
follows that the only district-fair integral solution is
$W_{int}:=\\{x_{1},x_{2},\ldots,x_{k-1}\\}$ where
$\textup{sw}(W_{int})=(2+\varepsilon)(k-1)$.

On the other hand, consider the following fractional solution $y$. For each
non-dummy project $x_{j}$ we let $y_{j}=\frac{1+\varepsilon}{2}$. For each
dummy project $x_{j}$ we let $y_{j}$ be $(1-\frac{1+\varepsilon}{2})$. Clearly
$\sum_{j}y_{j}\leqslant b$. Moreover, notice that for each district $d_{i}$ we
have
$\sum_{j}y_{j}\cdot\textup{sw}_{i}(x_{j})=\frac{1+\varepsilon}{2}(2+\varepsilon)\geqslant
1+\varepsilon=f_{i}$ and so our solution is indeed in the polytope of DFLP.
However, since $y_{j}=(1-\frac{1+\varepsilon}{2})$ for each dummy project we
have that $\sum_{j}y_{j}\cdot\textup{sw}(x_{j})\geqslant
B(k-1)(1-\frac{1+\varepsilon}{2})$.

Thus, for the above instance we have that the ratio of the optimal integral
solution to the optimal fractional solution is at most

$\displaystyle\frac{(2+\varepsilon)(k-1)}{B(k-1)\left(1-\frac{1+\varepsilon}{2}\right)}\leqslant\frac{10}{B}.$

Since $B$ can be chosen independently of $k$ and $m$, we have that the above
instance has integrality gap strictly less than $\frac{1}{f(k,m)}$ for any
function $f$ of $k$ and $m$. ∎

We note that the proof of the above result also rules out any integrality gap
which is which is larger than $o(\frac{1}{c})$ where $c$ is the total number
of voters across all districts.

##  Appendix C Randomized Optimal DF1 Outcome with Extra Budget

In this section we give our randomized analogues of Theorem 5 and Corollary 6.
We use the notation of Section 5 throughout this section. Whereas our
deterministic algorithms overspend budget by $64.7\%$, our randomized
algorithms will only overspend it by $\frac{1}{e}$ with high probability.
Formally, we show the following theorem.

######  Theorem 12.

There is a $\text{poly}(m,k)$-time algorithm which, given an instance of
district-fair welfare maximization, returns an outcome $W$ such that $W$ is
DF1, $c(W)\leqslant\left(1+\frac{1}{e}+\varepsilon\right)b\approx 1.37b$ with
high probability, and
$\textup{sw}(W)\geqslant(1-\varepsilon)\operatorname*{\textup{OPT}}$ for any
fixed constant $\varepsilon>0$.

As with Corollary 6 for Theorem 5, we immediately have a corollary which gives
an algorithm which does not overspend its budget.

######  Corollary 13.

There is a $\text{poly}(m,k)$-time algorithm which, given an instance of
district-fair welfare maximization, returns an outcome $W$ such that $W$ is
DF1 for $\mathcal{I}^{\prime}\left(\frac{1}{1+1/e}\right)$,
$c(W)\leqslant\left(1+\varepsilon\right)b$ with high probability, and
$\textup{sw}(W)\geqslant(1-\varepsilon)\operatorname*{\textup{OPT}}^{\prime}\left(\frac{1}{1+1/e}\right)$
for any fixed constant $\varepsilon>0$.

On a high level, this proof will closely follow that of Theorem 5. In
particular, it uses the same submodular optimization framing of the problem
(i.e., DF1P). However, there are some notable differences. In particular, we
leverage the following randomized result from Mizrachi et al. (2018) instead
of the previous deterministic result from Mizrachi et al. (2018).

######  Theorem 14 (Mizrachi et al. 2018, Theorem 1).

For each constant $\varepsilon>0$, there exists a randomized algorithm for
maximizing a nondecreasing submodular function subject to one packing
constraint and one covering constraint that runs in time $O(|\Omega|^{O(1)})$,
satisfies the packing constraint, satisfies the covering constraint up to a
factor of $1-\varepsilon$, and achieves an expected approximation ratio of
$1-\frac{1}{e}-\varepsilon$.

Additionally, we require Hoeffding’s inequality (Hoeffding 1963), which bounds
the probability that the sum of a sequence of independent random variables
deviates from its expectation; we restate it below.

######  Theorem 15 (Hoeffding’s Inequality).

Given a sequence of $n$ independent random variables $Y_{1},\dots,Y_{n}$,
where each $Y_{i}$ takes a value in the range $[\alpha_{i},\beta_{i}]$, we
have that

$\Pr\left(\mathop{{}\mathbb{E}}\left[\sum_{k=1}^{n}Y_{k}\right]-\sum_{k=1}^{n}Y_{k}\geqslant
t\right)\leqslant
e^{-\frac{2t^{2}}{\sum_{i=1}^{n}(\beta_{i}-\alpha_{i})^{2}}},$

where $t\geqslant 0$.

We now present the main lemma of the section, which states that there exists a
polynomial-time algorithm which, given a guess of the optimal district-fair
social welfare $B\leqslant\operatorname*{\textup{OPT}}$, returns an outcome
$W$ that is DF1 fair, overspends the budget by approximately $b/e$ with high
probability, and achieves at least $(1-\varepsilon)B$ social welfare.

######  Lemma 16.

Given an instance of DF1P, there is an algorithm that runs in polynomial time
which returns an outcome $W$ such that $W$ is DF1,
$c(W)\leqslant\left(1+\frac{1}{e}+\varepsilon\right)b$ with high probability,
and $\textup{sw}(W)\geqslant(1-\varepsilon)B$, where $\varepsilon>0$ is an
arbitrary constant and $B\leqslant\operatorname*{\textup{OPT}}$.

###### Proof.

Note that, by Lemma 7, it suffices to find an outcome $W^{\prime}$ such that
$c(W^{\prime})\leqslant b$,
$\textup{cover}(W^{\prime})\geqslant\left(1-\frac{1}{e}-\varepsilon\right)b$,
and $\textup{sw}(W^{\prime})\geqslant(1-\varepsilon)B$, as we can complete
this solution into a DF1 solution with $\left(\frac{1}{e}+\varepsilon\right)b$
more budget.

Let $\varepsilon_{0}\coloneqq\varepsilon/2$. By Lemma 9, we may apply Theorem
14 in order to find a solution $W$ such that
$\textup{cover}(W)\geqslant(1-\varepsilon_{0})(1-1/e)$ in expectation,
$\textup{sw}(W)\geqslant B$, and $c(W)\leqslant b$. We now show how to
transform this guarantee in expectation into one with high probability by
using Hoeffding’s inequality and an averaging argument.

In order to apply Hoeffding’s inequality to our setting, let $Y_{j}$ represent
the coverage of the $j^{th}$ run of our application of Theorem 14. We know
that each run is independent, and therefore the $Y_{j}$’s are also
independent. Let $n=\omega(\log k/\varepsilon_{0}^{2})$, and define a sequence
of $n$ independent random variables $Y_{1},\dots,Y_{n}$ representing the
coverage of $n$ runs of the mechanism. Furthermore, because coverage is
bounded between 0 and $b$, we have that $\beta_{i}=b$ and $\alpha_{i}=0$ for
all $i\in[n]$.

By Hoeffding, we have

$\displaystyle\Pr\left(\mathop{{}\mathbb{E}}\left[\sum_{j=1}^{n}Y_{j}\right]-\sum_{j=1}^{n}Y_{j}\geqslant\varepsilon_{0}\left(1-\frac{1}{e}\right)bn\right)$
$\displaystyle\qquad\leqslant\exp\left(-\frac{2(\varepsilon_{0}\left(1-\frac{1}{e}\right)bn)^{2}}{\sum_{i=1}^{n}(\beta_{i}-\alpha_{i})^{2}}\right)$
$\displaystyle\qquad=\exp\left(-2\varepsilon_{0}^{2}\left(1-\frac{1}{e}\right)^{2}n\right).$

Because we set $n=\omega(\log k/\varepsilon_{0}^{2})$, this probability goes
to 0 polynomially quickly. Therefore, we know that, with high probability,
$\mathop{{}\mathbb{E}}\left[\sum_{j=1}^{n}Y_{j}\right]-\sum_{j=1}^{n}Y_{j}\leqslant\varepsilon_{0}\left(1-\frac{1}{e}\right)bn$,
or $\sum_{j=1}^{n}Y_{j}\geqslant
bn(1-\varepsilon_{0})\left(1-\frac{1}{e}\right)-\varepsilon_{0}\left(1-\frac{1}{e}\right)bn$.
By an averaging argument, this means that, with high probability, there exists
a $Y_{i}$ such that
$Y_{i}\geqslant(1-\varepsilon_{0}-\varepsilon_{0})\left(1-\frac{1}{e}\right)b=(1-\varepsilon)\left(1-\frac{1}{e}\right)b$,
as desired. ∎

With this lemma in hand, we are ready to prove Theorem 12.

###### Proof of Theorem 12.

Recall that we have assumed that the maximum utility of an outcome is
polynomially bounded in $m$ and $k$ and that the maximum utility is integral.
Thus, the value of $\operatorname*{\textup{OPT}}$ falls in a polynomial range.
For each value $B$ in this range, run the procedure from Lemma 16. By a union
bound over these polynomially-many applications of Lemma 16, we have that all
applications of Lemma 16 with $B\leqslant\operatorname*{\textup{OPT}}$ succeed
with high probability, resulting in a collection of solutions; one for each
$B$. Now consider all values of $B$ for which the algorithm returned a
solution with $c(W)\leqslant(1+\frac{1}{e}+\varepsilon)b$; such a value must
exist since with high probability we are guaranteed this condition when
$B=\operatorname*{\textup{OPT}}$ and we know that, with high probability, all
applications of Lemma 16 succeed for all
$B\leqslant\operatorname*{\textup{OPT}}$. Among all solutions we found that
satisfy $c(W)\leqslant(1+\frac{1}{e}+\varepsilon)b$, take the one that
maximizes $\textup{sw}(W)$. This solution provides utility at least
$\operatorname*{\textup{OPT}}$.

∎