# districtfair_participatory_budgeting__e6d2a7f8.pdf

District-Fair Participatory Budgeting

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

1 Carnegie Mellon University 2 Harvard University dhershko@cs.cmu.edu, akahng@cs.cmu.edu, dpeters@seas.harvard.edu, arielpro@seas.harvard.edu

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.

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 e100 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,

Copyright c 2021, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

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.1 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.2 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

1More specifically, projects are selected in descending order of vote count until the budget runs out. 2In 2016, this split in Paris was e64.3 million for district elections and e30 million for city-wide elections (Cabannes 2017).

The Thirty-Fifth AAAI Conference on Artificial Intelligence (AAAI-21)

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.3 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 multiplicativeweights-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 ε (ex ante). Since the fairness guarantee only holds in expectation, some districts may be underserved once the lottery is realized. However, our in-expectation guarantee translates to a high probability guarantee if we run this lottery every year.

3Our notion of district fairness can be thought of as a form of individual rationality where every district is seen as an individual.

In particular, as long as the utility that each district deserves stays comparable across years, then a Chernoff and union bound together show that with high probability the sum of each district s received utilities over the years is at least the sum of the utility it deserves, up to a small error term. 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 ( 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 en s rule and Thiele s Proportional Approval Voting (Janson 2016; S anchez-Fern andez 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 approxi-

mations 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 Sadfi2005; Fujimoto and Yamada 2006).

Formal Problem, Notation and Definitions Formally, the setting we consider is as follows. We are given a budget b Z 1. There are m possible projects P = {x1, . . . , xm} with associated nonnegative costs c : P Z 0. We refer to a subset W P as an outcome. The cost of an outcome W is c(W) := P xj W c(xj). We say that a subset W is budget-feasible if c(W) b. There are k districts d1, . . . , dk. The social welfare (or utility) that project xj provides to district di is swi(xj) Z 0. We assume that utilities are additive; i.e., the utility that an outcome W P provides to district di is swi(W) := P xj W swi(xj). Furthermore, the total social welfare of W P is sw(W) := P i [k] swi(W). Throughout this work we assume that sw(xj) and c(xj) are both poly(k, m) for each j. (A function f is poly(x, y) if there exists a k 0 such that f = O((xy)k).) We can relax this assumption using well-known bucketing techniques at the cost of an arbitrarily small ε 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 at least the utility it could achieve if it spent its budget on its most preferred projects: Each district di deserves some budget bi 0 where P

i bi = b. District di deserves utility fi := swi(Wi), where Wi := arg max W :c(W ) bi swi(W) is di s favorite outcome costing at most bi.

Definition 1 (District-Fair Outcome). We say that an outcome W is district-fair (DF) if swi(W) fi for all i.

Computing fi is an instance of the knapsack problem; by our assumption that utilities and costs are polynomially bounded, this instance is solvable in polynomial time (Chekuri and Khanna 2005). Thus, we assume fi is known. Note that the outcome S

i Wi 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 sw(W). We call our problem district-fair welfare maximization. Throughout this paper, we let W := arg max W sw(W) be some optimal solution, where the argmax is taken over budget-feasible and district-fair solutions. Similarly, we let OPT := 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 ?? .

Definition 2 (ε-District-Fair Lottery). Given ε > 0, we say that a probability distribution W over outcomes of cost at most b is an ε-district-fair (ε-DF) lottery if EW W[swi(W)] fi ε for every district di.

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 di,

swi(W) + max xj (P\W ) swi(xj) fi.

DF1 is inspired by the well-studied notion of EF1 (envyfreeness 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 ?? .

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 sw(W) 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 = {e1, . . . , e3n} and a collection {S1, . . . , Sm} of 3-element subsets of U. It is a yes -instance if there exists a selection Sj1, . . . , Sjn such that Sj1 Sjn = 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 D . Let D = {d1, . . . , d3n}, where each di in D corresponds to element ei. Additionally, let D = {d3n+1, . . . d3n+M}, where each di D is a dummy district. We have m + 2n + M projects, X X . Let X = {x1, . . . , xm}, where xj X corresponds to set Sj, and let X = {xm+1, . . . , xm+2n+M}, where each xj M is a dummy project. Utilities are as follows: every dummy district approves every dummy project, so swi(xj) = 1 for each i 3n+1 and xj X . Also, each non-dummy district approves of non-dummy sets to reflect the structure of the X3C instance: that is, for each i 3n we have swi(xj) = 1 if xj X and ei Sj. All other utilities are 0: that is, swi(xj) = 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 bi = 1 for every district di. Clearly, fi = 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 Sj1, . . . , Sjn to the X3C instance, then W = {xj1, . . . , xjn} X 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 budgetfeasible 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 W since otherwise the total welfare of W is less than (2n + M)M. Hence |X W| n. By district-fairness, for each i = 1, . . . , 3n, there must be some xj W such that ei Sj. These two facts together imply that {Sj : xj 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 the full version, this special case admits a polynomialtime 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 the full version shows that the integrality gap of that formulation is unboundedly large, so this approach will not work.

Optimal District-Fair Lottery In this section, we allow randomness and consider lotteries over outcomes. Our main result for the lottery setting is an ε-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 ε > 0 refer to the ε in the ε-DF definition.

Theorem 2. There is an algorithm which, in poly m, k, 1

time, returns an ε-DF lottery W such that for all outcomes W in the support of W, we have sw(W) 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 d. We can, then, compute as our solution a utility-optimal outcome W which is fair for d but not necessarily fair for each di 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 di, we might naturally increase the proportional share of di in the convex combination and recompute W in the hopes that the new outcome we compute will be fair for di. 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(sw(1), . . . , sw(k), j, b) which is the answer to the question, Does there exists an outcome of cost at most b using projects x1, x2, . . . , xj wherein district di achieves social welfare at least sw(i)? If the answer to this question is yes, then either the desired utilities are possible with the stated budget without using xj or there is an outcome which uses at most b c(xj) budget that doesn t use xj in which every district gets at least its specified utility minus how much it values xj. Thus, R(sw(1), . . . , sw(k), j, b) is true if and only if either R(sw(1), . . . , sw(k), j 1, b) is true or R(sw(1) sw1(xj), . . . , sw(k) swk(xj), j 1, b c(xj)) 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 sw(W) = 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 sw(i) fi for all i and which maximizes P i 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(sw(1), . . . , sw(k), j, 1), for each j and possible value for each sw(i) in polynomial time. Since maxi,j swi(xj) is polynomially bounded in m, we need only check polynomiallymany in m values for each 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.4 We let w(t) i 0 be the weight of district i in iteration t and let w(t) := P i w(t) i be the total weight in iteration t. Initially, our weights are uniform: w(1) i = 1 for all i.

For any iteration t and district di we let p(t) i := w(t) i w(t) be the proportion of the weight that district i has in iteration t. These p(t) i will induce our convex combination over districts; in particular we let d(t) be a district which values project xj to extent sw(t)(xj) := P i p(t) i swi(xj) and which deserves f (t) := P i p(t) i fi utility. Also, let swmax be the maximum welfare of an outcome. With the above notation in hand, we can give our instantiation of multiplicative weights where T := 4 ln k

ε2 sw2 max is the number of iterations of our algorithm.

1. For all iterations t [T]: (a) Let Wt be an outcome that maximizes sw(Wt) subject to sw(t)(Wt) f (t) and c(Wt) b. We can compute Wt using Lemma 3.

(b) Let m(t) i := swi(Wt) fi be our mistakes , indicating how far off a district was from getting what it deserved.

(c) Update weights: w(t+1) i w(t) i exp( εm(t) i ). 2. Return lottery W, the uniform distribution over {Wt}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 p(t), m(t) := P i p(t) i m(t) i is the usual inner product. Lemma 4 (Arora, Hazan, and Kale 2012). For all i we have 1 T

t T p(t), m(t) ε + 1

t T m(t) i .

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(Wt) 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 d(t). In particular,

sw(t)(W ) = X

i pi swi(W ) X

i pifi = f (t)

Thus, W is a budget-feasible solution for the problem of finding a max-utility outcome which is fair for d(t). Thus,

4We 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.

sw(Wt) can only be larger than sw(W ), meaning that sw(Wt) OPT. We now argue that the above lottery is ε-DF in expectation. Fix a district di. By Lemma 4 we know that

t T p(t), m(t) ε + 1

t T m(t) i . (1)

Now notice that by definition of m(t) i and since our lottery is uniform over all Wt we know that the right-hand-side of Equation (1) is

t T m(t) i = ε + 1

t (swi(Wt) fi)

= ε fi + E W W[swi(W)]

Thus, to show that fi ε EW W[swi(W)], it suffices to show that the left-hand side of Equation (1) is at least 0. That is, we must show 0 1

T P t T p(t), m(t) . However, this amounts to simply showing that Wt is fair for d(t); in particular, we have that the left-hand-side is

t T p(t), m(t) = 1

i p(t) i (swi(Wt) fi)

t T sw(t)(Wt) f (t).

It holds that sw(t)(Wt) f (t) 0 since we always choose a solution which is fair for d(t), and so we conclude that the left-hand-side of Equation (1) is at least 0.

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 OPT if the algorithm can spend double the available budget: we can compute an outcome W1 with c(W1) b that is welfare-maximizing without attempting to satisfy district-fairness, and we can compute some outcome W2 with c(W2) b that is district-fair (see ?? ); then W1 W2 satisfies district fairness and we clearly have c(W1 W2) 2b and sw(W1 W2) 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 ε > 0, there is a 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) (1.647 + ε) b, and sw(W) (1 ε) 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 I and a multiplier β < 1, we define an instance I (β), which is identical to I but in which each district di contributes only β bi and thus deserves utility f i := swi(W i), where W i is di s favorite outcome which costs at most β bi. Additionally, let OPT (β) represent the maximum achievable social welfare over all district-fair solutions in I using a budget of at most b := β b. Then, applying Theorem 5 to I (β) 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 ε > 0, there is a poly(m, k)- time algorithm which, given an instance I of district-fair welfare maximization, returns an outcome W such that W is DF1 for I ( 1 1.647), c(W) (1 + ε) b, and sw(W) (1 ε) OPT ( 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 1

e .37 fraction of the budget, with high probability (i.e., with probability 1 1 p(m,k) where p(m, k) is some polynomial in m and k). Details of our randomized algorithm are in the full version. 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 Rm where 0 pj 1. We overload notation and let the social welfare of p for district di be swi(p) := P j swi(xj) pj. Similarly the social welfare of p is P i swi(p). Lastly, we define the cost of p as P j c(xj) pj.

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 (residi(W)). The residual budget requirement of district di given (integral) outcome W is the minimum cost of a fractional outcome p such that swi(W) + swi(p) fi and pj = 0 for all xj 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 (coveri(W)). The coverage of an outcome W for district di is the difference between the amount of budget they deserve, bi, and their residual budget requirement: coveri(W) := bi residi(W). Lastly, we define the coverage of an outcome. Definition 7 (cover(W)). The overall coverage of an outcome W is the sum over all districts di of the coverage W affords di: coveri(W) := P i coveri(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 β fraction of all fairness constraints, we can use at most an extra β 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 cover(W) = b r, one can compute in polynomial time a set W W such that W is DF1 and c(W ) 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(xj). Suppose that W is an outcome that fails DF1, and let di be a district such that swi(W) + swi(xj) < fi for all xj W. Let p be the fractional outcome witnessing residi(W); thus swi(W) + swi(p) fi. We may assume without loss of generality that all but at most one project is integral in pj (because there is always some optimal p with this property by additivity of swi). Since W fails DF1 for di, there is some xj W such that p(xj) = 1. Then residi(W {xj}) = residi(W) c(xj) (witnessed by the fractional outcome obtained from p by removing xj from it). Thus, from definitions, coveri(W {xj}) = coveri(W) + c(xj), and hence cover(W {xj}) cover(W) + c(xj). Now suppose we are given an outcome W with cover(W) = b r, which fails DF1. We can identify a project xj as above, add it to W, and increase the coverage by at least c(xj). We repeat this until the outcome is DF1. This process must stop, since at each step the coverage increases by c(xj) 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 ) c(W) + r.

With this lemma in hand, we now turn to the problem of finding high-coverage outcomes with good welfare. Let

B 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.

max W P cover(W)

s.t. sw(W) B, c(W) b.

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 Ω, a set function f : Ω R 0 is nondecreasing and submodular if for every A, B Ω such that A B we have f(A) f(B) and f(A {x}) f(A) f(B {x}) f(B) for all x Ω\ B.

The theorem we apply is as follows.

Theorem 8 (Mizrachi et al. 2018, Theorem 5). For each constant ε > 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 = |Ω| is the size of the support of the set function, satisfies the covering constraint up to a factor of 1 ε and the packing constraint up to a factor of 1 + ε, 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 fairnessconstrained utility. Then, we apply Lemma 7 to augment our solution using an additional 1 0.353+ε 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 cover(W) is a nondecreasing submodular function. In particular, note that the coverage functions coveri(W) for each district are clearly nondecreasing and submodular. It follows that their sum, cover(W) is also nondecreasing and submodular, yielding the following lemma.

Lemma 9. The function 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 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 cover(W) 0.353b; such a value must exist since we are guaranteed this condition when B = OPT (since for this value, the optimum of problem (DF1P) is b). Among all solutions we found that satisfy

cover(W) 0.353b, take the one that maximizes sw(W). This solution provides social welfare at least (1 ε) OPT. We have obtained an outcome W with

cover(W) 0.353b = b 0.647b,

and sw(W) (1 ε) OPT and c(W) (1+ε)b. Now apply Lemma 7 to W to obtain a DF1 outcome W W with

c(W ) c(W) + 0.647b (1 + 0.647 + ε)b.

This outcome W satisfies the requirements of Theorem 5.

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 holds even for approval votes. Several open questions remain. Most obvious is the question of whether we can achieve welfare maximization and DF1 in polynomial time while overspending 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 and do not overspend any budget. In the full version, we present an algorithm which satisfies district fairness, does not overspend budget, 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.

Acknowledgments

D Ellis Hershkowitz is supported in part by NSF grants CCF1527110, CCF-1618280, CCF-1814603, CCF-1910588, NSF CAREER award CCF-1750808 and a Sloan Research Fellowship.

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, 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, H.; Elkind, E.; Huang, S.; Lackner, M.; S anchez Fern andez, 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, H.; and Shah, N. 2020. Participatory Budgeting: Models and Approaches. In Rudas, T.; and P eli, G., eds., Pathways Between Social Science and Computational Social Science: Theories, Methods, and Interpretations. Springer.

Brill, M.; Freeman, R.; Janson, S.; and Lackner, M. 2017. Phragm en s Voting Methods and Justified Representation. In Proceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI), 406 413.

Brown, J. R. 1979. The knapsack sharing problem. Operations Research 27(2): 341 355.

Budish, E. 2011. The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes. Journal of Political Economy 119(6): 1061 1103.

Cabannes, Y. 2004. Participatory budgeting: a significant contribution to participatory democracy. Environment and Urbanization 16(1): 27 46.

Cabannes, Y. 2014. Contribution of Participatory Budgeting to provision and management of basic services. London: IIED .

Cabannes, Y. 2017. Participatory budgeting in Paris: Act, reflect, grow. Another city is possible with participatory budgeting 179 203.

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, 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, 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, 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 ar Xiv:1805.03164.

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, 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, M. R.; and Johnson, D. S. 1979. Computers and intractability, volume 174. Freeman San Francisco. 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.; M Halla, H.; and Sadfi, S. 2005. An exact algorithm for the knapsack sharing problem. Computers & Operations Research 32(5): 1311 1324. Janson, S. 2016. Phragm en s and Thiele s election methods. Technical report. Ar Xiv:1611.08826 [math.HO].

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, E.; Schwartz, R.; Spoerhase, J.; and Uniyal, S. 2018. A tight approximation for submodular maximization with mixed packing and covering constraints. ar Xiv:1804.10947. 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, 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 anchez-Fern andez, L.; Elkind, E.; Lackner, M.; Fern andez, 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, 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.

Yamada, T.; and Futakawa, M. 1997. Heuristic and reduction algorithms for the knapsack sharing problem. Computers & operations research 24(10): 961 967. 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.