# proportionality_in_approvalbased_participatory_budgeting__f5920c40.pdf

Proportionality in Approval-Based Participatory Budgeting

Markus Brill1,2, Stefan Forster3, Martin Lackner3, Jan Maly4, Jannik Peters1

1TU Berlin, Berlin, Germany 2University of Warwick, Coventry, UK 3TU Wien, Vienna, Austria 4ILLC, University of Amsterdam, Amsterdam, Netherlands markus.brill@warwick.ac.uk, stefan.forster@tuwien.ac.at, lackner@dbai.tuwien.ac.at, j.f.maly@uva.nl, jannik.peters@tu-berlin.de

The ability to measure the satisfaction of (groups of) voters is a crucial prerequisite for formulating proportionality axioms in approval-based participatory budgeting elections. Two common but very different ways to measure the satisfaction of a voter consider (i) the number of approved projects and (ii) the total cost of approved projects, respectively. In general, it is difficult to decide which measure of satisfaction best reflects the voters true utilities. In this paper, we study proportionality axioms with respect to large classes of approval-based satisfaction functions. We establish logical implications among our axioms and related notions from the literature, and we ask whether outcomes can be achieved that are proportional with respect to more than one satisfaction function. We show that this is impossible for the two commonly used satisfaction functions when considering proportionality notions based on extended justified representation, but achievable for a notion based on proportional justified representation. For the latter result, we introduce a strengthening of priceability and show that it is satisfied by several polynomial-time computable rules, including the Method of Equal Shares and Phragm en s sequential rule.

1 Introduction How can cities ensure that the results of their participatory budgeting process proportionally represents the preferences of the citizens? This is the key question in a recently emerging line of research on proportional participatory budgeting (Aziz, Lee, and Talmon 2018; Peters, Pierczy nski, and Skowron 2021; Los, Christoff, and Grossi 2022). Participatory budgeting (PB) is the collective process of identifying a set of projects to be realized with a given budget cap; often, the final decision is reached by voting (e.g., Laruelle 2021). The goal of proportional PB is to identify voting rules that guarantee proportional representation without the need to declare a priori which groups deserve representation. Instead, each group of sufficient size with sufficiently similar interests is taken into account. Such a group could be a district, cyclists, parents, or any other collection of people with similar preferences. This is contrast to, e.g., assigning each district a proportional part of the budget, which excludes other (cross-district) groups from consideration.

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

To be able to speak about proportional representation in the context of PB, one first needs to decide on how to measure the representation of a given voter by a selection of projects. If votes are cast in the form of approval ballots, as is the case in most PB processes in practice, two standard ways to measure the satisfaction of a voter have emerged. The first assumes that the satisfaction a voter derives from an outcome is the total cost of the approved projects in this outcome (Aziz, Lee, and Talmon 2018; Aziz and Lee 2021; Talmon and Faliszewski 2019). In other words, voters care about how much money is spent on projects they like. The second assumes the satisfaction of a voter to be simply the number of approved projects in the outcome (Peters, Pierczy nski, and Skowron 2021; Los, Christoff, and Grossi 2022; Fairstein et al. 2022; Talmon and Faliszewski 2019). We refer to these two measures as cost-based satisfaction and cardinality-based satisfaction, respectively. Both measures, though naturally appealing, have their downsides: Under the cost-based satisfaction measure, inefficient (i.e., more expensive) projects are seen as preferable to equivalent but cheaper ones. Under the cardinality-based satisfaction measure, large projects (e.g., a new park) and small projects (e.g., a new bike rack) are treated as equivalent.

The ambiguity of measuring satisfaction leads to three main problems: First, different papers present incomparable notions of fairness based on different measures of satisfaction. For example, both Aziz, Lee, and Talmon (2018) and Los, Christoff, and Grossi (2022) generalized a well-known proportionality axiom known as proportional justified representation (PJR), but they did so based on different satisfaction measures. Second, the two measures described above are certainly not the only reasonable functions for measuring satisfaction; and results in the literature cannot easily be transferred to new satisfaction functions. For example, satisfaction could be estimated by experts evaluating projects; if efficiency is taken into account, such a measure may differ significantly from the cost-based one. Third, most papers so far have focused on a single satisfaction function only. Therefore, it is not known whether we can guarantee proportionality properties with respect to different satisfaction measures simultaneously. This would be extremely useful in practice: If a mechanism designer is not sure which satisfaction function most accurately describes the voters preferences in a given PB process, she could potentially choose a

The Thirty-Seventh AAAI Conference on Artificial Intelligence (AAAI-23)

voting rule that provides proportionality guarantees with respect to all satisfaction functions that seem plausible to her.

Our contribution. To tackle these problems, we propose a general framework for studying proportionality in approvalbased participatory budgeting: We employ the notion of (approval-based) satisfaction functions (Talmon and Faliszewski 2019), i.e., functions that, for every possible outcome, assign to each voter a satisfaction value based on the voter s approval ballot. We then use this notion of satisfaction functions to unify the different proportionality notions studied by Aziz, Lee, and Talmon (2018), Peters, Pierczy nski, and Skowron (2021), and Los, Christoff, and Grossi (2022) into one framework and analyze their relations. Furthermore, we identify a large class of satisfaction functions that are of particular interest: Weakly decreasing normalized satisfaction (short: DNS) functions are satisfaction functions for which more expensive projects offer at least as much satisfaction as cheaper projects, but the satisfaction does not grow faster than the cost. Intuitively, the cardinal measure is one extreme of this class (the satisfaction does not change with the cost) while the cost-based measure is the other extreme (the satisfaction grows exactly like the cost). For each satisfaction function in this class, we show that an instantiation of the Method of Equal Shares (MES) (Peters and Skowron 2020; Peters, Pierczy nski, and Skowron 2021) satisfies extended justified representation up to any project (EJR-x).1 However, while MES for a specific satisfaction function satisfies EJR-x, we can show that even the weaker notion of EJR-1 is incompatible for the cost-based and cardinality-based satisfaction functions. In other words, it is not possible to find a voting rule that guarantees EJR1 for the cost-based and the cardinality-based satisfaction measure simultaneously. To deal with this incompatibility, we turn to the notion of proportional justified representation (PJR) and show that a specific class of rules, including sequential Phragm en and one variant of MES, satisfies PJR up to any project (PJR-x) for all DNS satisfaction functions at once. In other words, when using one of these rules, we generate an outcome that can be seen as proportional no matter which satisfaction function is used, as long as the function is a DNS satisfaction function.

Related work. The study of proportional PB crucially builds on the literature on approval-based committee voting (Lackner and Skowron 2022). The proportionality notions most relevant to our paper are extended justified representation (EJR) (Aziz et al. 2017), proportional justified representation (PJR) (S anchez-Fern andez et al. 2017), and priceability (Peters and Skowron 2020). Proportionality in PB was first considered by Aziz, Lee, and Talmon (2018), who generalized PJR as well as the maximin support method (S anchez-Fern andez et al. 2021). This setting was subsequently generalized to voters with ordinal preferences (Aziz and Lee 2021). The concept of

1This strengthens a result by Peters, Pierczy nski, and Skowron (2021), showing that MES satisfies EJR up to one project (EJR-1) for additive utility functions.

satisfaction functions was introduced by Talmon and Faliszewski (2019), who presented a framework for designing (non-proportional) approval-based PB rules. Besides the cost-based and the cardinality-based satisfaction function, they also studied a satisfaction measure based on the Chamberlin Courant method (Chamberlin and Courant 1983). Peters, Pierczy nski, and Skowron (2021) studied PB with arbitrary additive utilities and showed that a generalized variant of the Method of Equal Shares (MES) (Peters and Skowron 2020) satisfies EJR up to one project. The approval-based satisfaction functions studied in our paper constitute special cases of additive utility functions, and the additional structure provided by this restriction allows us to show a significantly stronger result. Los, Christoff, and Grossi (2022) study the logical relationship of proportionality axioms in PB with either additive utilities or the cardinality-based satisfaction function. They generalize notions such as PJR, laminar proportionality, and priceability to the two aforementioned settings and study how MES, sequential Phragm en, and other rules behave with regard to these axioms. In particular, they show that sequential Phragm en satisfies PJR for the cardinality-based satisfaction function. We strengthen the latter result along multiple dimensions, by identifying a class of rules satisfying PJR-x for a whole class of satisfaction functions simultaneously. (PJR-x is equivalent to PJR for the cardinality-based satisfaction function.) Besides proportionality, other recent topics in PB include the handling of donations (Chen, Lackner, and Maly 2022), the study of districts (Hershkowitz et al. 2021) and projects groups (Jain et al. 2021), the maximin objective (Sreedurga, Bhardwaj, and Narahari 2022), welfare/representation tradeoffs (Fairstein et al. 2022), and uncertainty in the cost of projects (Baumeister, Boes, and Laußmann 2022).

2 Preliminaries

For t N, we let [t] denote the set [t] = {1, . . . , t}. Let N = [n] be a set of n voters and P = {p1, . . . , pm} a set of m projects. Each voter i N is associated with an approval ballot Ai P and an approval profile A = (A1, . . . , An) lists the approval ballots of all voters. Further, c: P R+ is a cost function mapping each project p P to its cost c(p). Finally, b R+ is the budget limit. Together, (A, P, c, b) form an approval-based budgeting (ABB) instance. For a subset W P of projects, we define c(W) = P p W c(p). We call W an outcome if c(W) b, i.e., if the projects in W together cost no more than the budget limit. Further, we call an outcome W exhaustive if there is no outcome W W. An ABB rule R now assigns every ABB instance E = (A, P, c, b) to a non-empty set R(E) of outcomes. If every outcome in R(E) is exhaustive for every ABB instance E, we call the rule R exhaustive. For a project p P we let Np := {i N : p Ai} denote the set of approvers of p. We often write Nj for Npj. An ABB instance with c(p) = 1 for all p P is called a unit-cost instance and corresponds to an approval-based committee voting instance with b seats.

Next, we define our key concept.

Definition 2.1. Given an ABB instance (A, P, c, b), an (approval-based) satisfaction function is a function µ: 2P R 0 that satisfies the following conditions: µ(W) µ(W ) whenever W W and µ(W) = 0 if and only if W = .

The satisfaction µi(W) that a voter i derives from an outcome W P with respect to the satisfaction function µ is defined as the satisfaction generated by the projects in W that are approved by i, i.e.,

µi(W) = µ(Ai W).

For notational convenience, we write µ(p) instead of µ({p}) for an individual project p P. Some of our results holds for restricted classes of satisfaction functions. In particular, we are interested in the following properties.

Definition 2.2. Given an ABB instance (A, P, c, b), a satisfaction function µ is

additive if µ(W) = P pi W µ(pi) for all W P. strictly increasing if µ(W) < µ(W ) for all W, W P with W W . cost-neutral if µ(W) = µ(W ) for all W, W P such that there is a bijection f : W W for which c(p) = c(f(p)) holds for all p P.

Clearly, every additive satisfaction function is also strictly increasing. The two most prominent satisfaction functions are the following.

Definition 2.3. Given an ABB instance (A, P, c, b) and a set W P, the cost-based satisfaction function µc is defined as µc(W) = c(W) = P p W c(p) and the cardinality-based satisfaction function µ# is defined as µ#(W) = |W|.

Clearly, µc and µ# are cost-neutral and additive. An example for a cost-neutral satisfaction function that is not strictly increasing (and, hence, not additive) is the CC satisfaction function (Talmon and Faliszewski 2019), which is inspired by the well-known Chamberlin Courant rule (Chamberlin and Courant 1983):

µCC(W) = 0 if W = 1 otherwise.

An example for an additive satisfaction function that is not cost-neutral is share (Lackner, Maly, and Rey 2021):

µshare(W) = X

We illustrate the two most prominent satisfaction functions, µc and µ#, with a simple example.

Example 2.1. Consider an ABB instance with one voter, five projects, and budget b = 5; the voter approves all projects and the cost of each project is 1 except the first project, which has cost c(p1) = 5. Under µc the best outcome is {p1}, which gives the voter a satisfaction of 5. Under µ#, the best outcome is {p2, . . . , p5}, with a satisfaction of 4.

Next, we define a natural subclass of additive and costneutral satisfaction functions that contains both µc and µ#. An additive satisfaction function belongs to this class if (i) more expensive projects provide at least as much satisfaction as cheaper ones, and (ii) more expensive projects do not provide a higher satisfaction per cost than cheaper projects.

Definition 2.4. Consider an ABB instance (A, P, c, b). An additive satisfaction function µ has weakly decreasing normalized satisfaction (DNS) if for all projects p, p P with c(p) c(p ) the following two inequalities hold:

µ(p) µ(p ) and µ(p)

In this case, we call µ a DNS function.

Clearly, both µc and µ# are DNS functions. Indeed, they can be seen as two extremes among DNS functions since µ#(p) = µ#(p ) holds for all p, p , whereas for µc we have µc(p)

c(p) = µc(p )

c(p ) . Other natural examples of DNS func-

tions include µ c(W) := P p W p

c(p) and µlog(c) := P p W log(1 + c(p)).

Finally, let us define an ABB rule that we use throughout the paper: the Method of Equal Shares (MES). In fact, we do not only define one rule, but rather a family of variants of MES, parameterized by a satisfaction function. We follow the definition of MES by Peters, Pierczy nski, and Skowron (2021) in the setting of additive PB.

Definition 2.5 (MES[µ]). Given an ABB instance (A, P, c, b) and a satisfaction function µ, MES[µ] constructs an outcome W, initially empty, iteratively as follows. It begins by assigning a budget of bi = b n to each voter i N. A project pj / W is called ρ-affordable if X

i Nj min(bi, ρµ(pj)) = c(pj).

In each round, the project pj which is ρ-affordable for the minimum ρ is selected and for every i Nj, the budget bi is updated to bi min(bi, ρµ(pj)). This process is iterated until no further ρ-affordable projects are left (for any ρ).

Intuitively, the parameter ρ tells us how many units of budget a voter has to pay for one unit of satisfaction.

3 Extended Justified Representation We begin our study of proportionality with the strong notion of extended justified representation (EJR). This concept was first introduced in the multiwinner setting by Aziz et al. (2017). On a very high level, it states that every group that is sufficiently cohesive deserves a certain amount of representation in the final outcome. Therefore, we first need to define what it means for a group of voters in a PB instance to be cohesive. For this, we follow Peters, Pierczy nski, and Skowron (2021) and Los, Christoff, and Grossi (2022).2

2Aziz, Lee, and Talmon (2018) define cohesiveness slightly differently, which leads to slightly different looking definitions of the axioms. The resulting definitions are, however, equivalent.

Definition 3.1. Given an ABB instance (A, P, c, b) and a set T P of projects, a subset N N of voters is T-cohesive if and only if T T i N Ai and c(T) |N |

n b. Using this definition, we can now define EJR, which essentially states that in every T-cohesive group there is at least one voter that derives at least as much satisfaction from the outcome as from T. Definition 3.2. Given an ABB instance (A, P, c, b) and a satisfaction function µ, an outcome W P satisfies extended justified representation with respect to µ (µ-EJR) if and only if for any T-cohesive N N, there is some i N such that µi(W) µi(T). In the following we say that an ABB rule R satisfies a property (in this case µ-EJR) if and only if, for every ABB instance (A, P, c, b), each outcome in R(A, P, c, b) satisfies this property. Definition 3.2 defines a whole class of axioms, one for each satisfaction function µ. This in contrast to the unit-cost setting, where only one version of the EJR axiom exists. This can be explained by the fact that µ-EJR and µ - EJR are equivalent in the unit-cost setting for many satisfaction functions µ and µ . Proposition 3.1. Consider a unit-cost ABB instance and two additive and cost-neutral satisfaction functions µ and µ . Then, an outcome satisfies µ-EJR if and only if it satisfies µ -EJR. Moreover, under these assumptions, µ-EJR is equivalent to EJR as originally defined originally by Aziz et al. (2017). By contrast, this is not the case, e.g., for µCC-EJR. Next, we show that µ-EJR is always satisfiable. Our proof adapts a similar proof for general additive utility functions (Peters, Pierczy nski, and Skowron 2021) and employs the so-called Greedy Cohesive Rule.3

Theorem 3.2. µ-EJR is always satisfiable for any satisfaction function µ. The Greedy Cohesive Rule that is used to prove Theorem 3.2 has exponential running time. This is however unavoidable, as we can show that no algorithm can find an allocation satisfying µ-EJR in polynomial time (unless P = NP), for a large class of approval-based satisfaction functions. We call this class strictly cost-responsive. Definition 3.3. We say that a satisfaction function µ is strictly cost-responsive if for all W, W P with c(W) < c(W ), we have µ(W) < µ(W ). This class includes µc but also functions with diminishing (but not vanishing) marginal satisfaction like µ c. Theorem 3.3. Let µ be a satisfaction function that is strictly cost-responsive for instances with a single voter. Then, there is no polynomial-time algorithm that, given an ABB instance (A, P, c, b) as input, always computes an outcome satisfying µ-EJR, unless P = NP. Note that µ# does not satisfy strict cost-responsiveness. Indeed, outcomes satisfying µ#-EJR can be computed efficiently, e.g., by employing MES[µ#] (Peters, Pierczy nski,

3Our result is less general in that it only considers the approval case and more general in that it does not assume additivity.

and Skowron 2021; Los, Christoff, and Grossi 2022). Further, we note that our reduction does not preclude efficient algorithms in the case that costs are bounded. Hence, it is open whether a pseudopolynomial-time algorithm exists. Theorem 3.3 motivates us to consider weakenings of EJR. First, we define EJR up to one project (Peters, Pierczy nski, and Skowron 2021).

Definition 3.4. Given an ABB instance (A, P, c, b) and a satisfaction function µ, an outcome W P satisfies EJR up to one project with respect to µ (µ-EJR-1) if and only if, for every T-cohesive group N , either T W or there exists a voter i N and a project p P \ W such that µi(W {p}) > µi(T).

Peters, Pierczy nski, and Skowron (2021) have shown that we can satisfy µ-EJR-1 for every additive satisfaction function µ using MES[µ].4 Since the approval-based setting studied in this paper is a special case of the setting studied by Peters, Pierczy nski, and Skowron (2021), we can improve upon their result. Similar to the fair division literature, where the notion of envy-freeness up to one good (EF-1) can be strengthened to envy-freeness up to any good (EF-x) (Caragiannis et al. 2019), we strengthen µ-EJR-1 to µ-EJR-x: Instead of requiring that there exists one project whose addition lets voter i s satisfaction exceed µ(T), we require that this holds for every unchosen project from T.

Definition 3.5. Given an ABB instance (A, P, c, b) and a satisfaction function µ, an outcome W P satisfies EJR up to any project with respect to µ (µ-EJR-x) if and only if, for every T-cohesive group N , there is a voter i N such that µi(W {p}) > µi(T) for every project p T \ W.

By definition, µ-EJR-x implies µ-EJR-1 and, intuitively, we would assume that µ-EJR-x is implied by µ-EJR. This is indeed the case, at least for strictly increasing satisfaction functions. Moreover, µ-EJR, µ-EJR-1 and µ-EJR-x are equivalent in the unit-cost setting as long as µ is strictly increasing and cost-neutral.

Proposition 3.4. Let µ be a strictly increasing satisfaction function. Then,

(i) µ-EJR implies µ-EJR-x, and (ii) for unit-cost instances if µ is cost-neutral, both µ-EJR-1 and µ-EJR-x are equivalent to µ-EJR.

The following example illustrates the difference between µ-EJR-x and µ-EJR-1.

Example 3.1. Consider one voter and five projects p1, p2, p3, p4 and p5, all approved by this voter. The costs and the additive satisfaction function are defined as follows.

p1 p2 p3 p4 p5 c( ) 2.5 2.5 2.5 3 4.5 µ( ) 0.1 0.1 0.1 3.1 4

4In the approval-based setting considered in this paper, this is even true if we strengthen µ-EJR-1 by requiring that the project p comes from T, i.e., by replacing p P \ W with p T \ W in Definition 3.4 (see the full version of this paper (Brill et al. 2023) for details).

Let b = 7. The single voter is {p1, p5}-cohesive with µ({p1, p5}) = 4.1. For this instance, there are three exhaustive outcomes (if one treats p1, p2, and p3 the same). The first one, {p1, p5}, satisfies µ-EJR (and thus also µ-EJR-x and µ-EJR-1). The second one, {p2, p3}, violates µ-EJR-x since µ({p2, p3} {p1}) = 0.3 < µ({p1, p5}); it, however, satisfies µ-EJR-1 since µ({p2, p3} {p5}) = 4.2 > µ({p1, p5}). Similarly, {p1, p4} also satisfies µ-EJR-1 but not µ-EJR-x.

Having observed that µ-EJR-x is strictly stronger than µEJR-1, a natural question is whether MES[µ] also satisfies µ-EJR-x. This is not the case in general. In Example 3.1, MES[µ] would first select p4 and then one of {p1, p2, p3}, and would thus violate µ-EJR-x. However, if we restrict attention to DNS functions µ, we can show that MES[µ] always satisfies µ-EJR-x.

Theorem 3.5. Let µ be a DNS function. Then MES[µ] satisfies µ-EJR-x.

This result shows that MES[µ] is proportional in a strong sense. However, it also has a big downside: Theorem 3.5 only provides a proportionality guarantee for MES[µ] for the specific satisfaction function µ by which the rule is parameterized. This means that we have to know which satisfaction function best models the voters when deciding which voting rule to use. It turns out that this is unavoidable, because for two different satisfaction functions, the sets of outcomes providing EJR-x can be non-intersecting. In fact, this even holds for EJR-1.

Proposition 3.6. There is an ABB instance for which no outcome satisfies µc-EJR-1 and µ#-EJR-1 simultaneously.

Proof. Consider the following example with two voters and projects p1, . . . , p12 with c(p1) = c(p2) = 5 and the other projects costing 1. Voter 1 approves {p1, . . . , p7} and voter 2 approves {p1, p2, p8, . . . , p12}. We set the budget to be 10. For µ#, we observe that each voter on their own is cohesive over the set of 5 projects they approve individually (i.e., voter 1 is {p3, . . . , p7}-cohesive and voter 2 is {p8, . . . , p12}-cohesive). If either p1 or p2 is included in the outcome, at least one voter has a satisfaction of at most 3 under µ#; such an outcome can not satisfy µ#-EJR1. Thus, W = {p3, . . . , p12} is the only outcome satisfying µ#-EJR-1. On the other hand, since both voters together are {p1, p2}-cohesive, the outcome W does not satisfy µc-EJR-1. Thus, no outcome satisfies both µc-EJR-1 and µ#-EJR-1 in this instance.

Proposition 3.6 shows that if we want to achieve strong proportionality guarantees, we need to know the satisfaction function. Since this might be unrealistic in practice, in the next chapter we focus on a weaker notion of proportionality.

4 Proportional Justified Representation In this section, we consider proportionality axioms based on proportional justified representation (PJR). As our main result in this section, we show that there exist rules which simultaneously satisfy PJR-x for all DNS functions. This establishes a counterpoint to our result for EJR at the end of the previous section (Proposition 3.6).

4.1 Variants of PJR PJR is a weakening of EJR. Instead of requiring that, for every cohesive group, there exists a single voter in the group who is sufficiently satisfied, PJR considers the satisfaction generated by the set of all projects that are approved by some voter in the group. Definition 4.1. Given an ABB instance (A, P, c, b), an outcome W P satisfies PJR with respect to a satisfaction function µ (µ-PJR) if and only if for any T-cohesive group N it holds that µ((W S i N Ai)) µ(T). For µ = µc, µ-PJR was considered by Aziz, Lee, and Talmon (2018), who called it BPJR-L. For µ = µ#, µ-PJR was considered by Los, Christoff, and Grossi (2022). It is straightforward to see that µ-EJR implies µ-PJR. Hence, from Theorem 3.2 it follows directly that µ-PJR is also always satisfiable. Corollary 4.1. µ-PJR is always satisfiable for any satisfaction function µ. Since µ-EJR and µ-PJR coincide if there is only one voter, the hardness proof for µ-EJR (Theorem 3.3) directly applies to µ-PJR. Corollary 4.2. Let µ be a satisfaction function that is strictly cost-responsive for instances with a single voter. Then, there is no polynomial-time algorithm that, given an ABB instance (A, P, c, b) as input, always computes an outcome satisfying µ-PJR, unless P = NP. The hardness result above (for µ = µc) motivated Aziz, Lee, and Talmon (2018) to define a relaxation of µ-PJR (for µ = µc) they call Local-BPJR . We discuss this relaxation in the full version of this paper (Brill et al. 2023), where we show that it does not imply PJR under the unit-cost assumption. Aziz, Lee, and Talmon (2018) show that their property is satisfied by a polynomial-time computable generalization of the maximin support method (S anchez-Fern andez et al. 2021). Instead of Local-BPJR, we consider a stronger property that is similar to µ-EJR-x. Definition 4.2. Given an ABB instance (A, P, c, b), an outcome W satisfies PJR up to any project w.r.t. µ (µ-PJR-x) if and only if for any T-cohesive group N and any p T \W it holds that µ((W S i N Ai) {p}) > µ(T). Let us consider the relationships between µ-PJR, µ-PJR-x and the EJR-based fairness notions that we introduced. By definition, µ-PJR-x is implied by µ-EJR-x for all satisfaction functions. One would additionally assume that µ-PJR-x is implied by µ-PJR. Like in the analogous statement for EJR (Proposition 3.4), we show this for strictly increasing satisfaction functions. Proposition 4.3. Let µ be a strictly increasing satisfaction function. Then, (i) µ-PJR implies µ-PJR-x, and (ii) for unit-cost instances if µ is cost-neutral, µ-PJR-x is equivalent to µ-PJR. As a consequence of the second part of Proposition 4.3, µc-PJR-x (unlike Local-BPJR) is equivalent to PJR in the unit-cost setting. For more details, see the full version of

this paper, (Brill et al. 2023) where we also discuss PJR up to one project (µ-PJR-1). Next, we consider the relationship between µ-PJR-x and µ-EJR-1. Of course, EJR is generally a stronger axiom that PJR. However, up to one project is a greater weakening than up to any project and, indeed, we find that µ-EJR-1 does not imply µ-PJR-x in general. We keep the following example fairly general to show that µ-EJR-1 does not imply µ-PJR-x for a large class of satisfaction functions.

Example 4.1. Consider a strictly increasing satisfaction function µ and an ABB instance (A, P, c, b) with |P| 3, and one voter 1 who approves all projects in P. Moreover, assume that there is a project p1 P for which

c(P \ {p1}) c(p1) and µ(P \ {p1}) = µ(p1).

Finally, let b = c(p1). For example, for µ {µc, µshare}, we can use any example for which c(P \ {p1}) = c(p1). Let p2 P with p2 = p1 and P = P \ {p1, p2}. Since |P| 3 we have that P = . We claim that P satisfies µ-EJR-1 but not µ-PJR-x. Let us first consider µ-EJR-1: We observe that {1} is {p1}-cohesive and {p1} is an affordable outcome from which 1 derives maximal satisfaction. Moreover, as µ is a satisfaction function and because P = , we know that µ(W) > 0. Since µ is strictly increasing, this implies µ(p1) < µ(P {p1}). Hence, P satisfies µ-EJR-1. On the other hand, since 1 derives the same satisfaction from the outcomes {p1} and P \{p1}, we know that P \{p1} is also an outcome from which the voter derives maximal satisfaction. By definition, P \ {p1} is a proper superset of P . Moreover, by assumption P {p1} is within the budget limit. This means that P violates µ-PJR-x.

4.2 Achieving PJR-x for All DNS Functions

Next we turn to our main result on PJR. We give a family of voting rules, all of which simultaneously satisfy µ-PJR-x for all DNS functions µ. To define these voting rules, we recall the definition of priceability, which has been introduced in multiwinner voting by Peters and Skowron (2020) and extended to the PB setting by Peters, Pierczy nski, and Skowron (2021) and Los, Christoff, and Grossi (2022).

Definition 4.3 (Priceability). An outcome W satisfies priceability with respect to an ABB instance (A, P, c, b) if and only if there is a budget B > 0 and a collection d = (di)i N of payment functions di : P [0, B

n ] such that5

C1 If di(pj) > 0 then pj Ai for all pj P and i N

C2 If di(pj) > 0 then pj W for all pj P and i N

C3 P pj P di(pj) B

n for all i N

C4 P i N di(pj) = c(pj) for all pj W

C5 P i Nj B i c(pj) for all pj / W, where B i is the unspent budget of voter i, i.e., B i = B

n P pk P di(pk).

The pair {B, d} is called a price system for W.

5The numbering of constraints follows Peters et al. (2021).

For unit-cost instances, every exhaustive, priceable outcome satisfies PJR (Peters and Skowron 2020). For µc, we show something similar in the approval-based PB setting. Theorem 4.4. Let W be an outcome such that there is a price system {B, d} with B > b. Then W fulfills µc-PJR-x. However, this implication does not hold for other satisfaction functions, as the following example illustrates. Example 4.2. Consider µ# and an instance with two voters, five projects p1, . . . , p5, and budget b = 4. The voters have the approval sets A1 = {p1, p2, p3} and A2 = {p1, p4, p5}. The project p1 costs 4 while the rest of the projects cost 1 each. Then the outcome {p1} is priceable with a budget of B = 4.5 > 4 (with both voters paying 2 for p1), but does not satisfy µ#-PJR-x. Towards a more broadly applicable variant of Theorem 4.4, we introduce a new constraint for price systems: C6 P i Nj di(pk) c(pj) for all pj / W and all pk W.

Intuitively, a violation of this axiom would mean that the approvers of pj could take their money they spent on pk and buy pj instead for a strictly smaller cost. If an outcome is priceable with a price system satisfying C6, we say that it is C6-priceable. For instance, in Example 4.2, the outcome consisting only of p1 is not C6-priceable since at least one voter must spend at least 2 on p1 which is more than the price of one of {p2, . . . , p5}. Using this definition, we can now show our main result, namely that C6-priceability with B > b is sufficient for satisfying µ-PJR-x for all DNS functions µ. Theorem 4.5. Let W P be a C6-priceable outcome with price system {B, d} such that B > b. Then, W satisfies µPJR-x for all DNS functions µ.

Proof. For the sake of a contradiction, assume that W does not satisfy µ-PJR-x. Then there is a T-cohesive group of voters N and some p T \ W such that

i N Ai) {p}) µ(T). (1)

For ease of notation, let W := W S i N Ai be the set of projects in W that are approved by at least one voter in N . Furthermore, we let Np denote the set of approvers of p. The proof proceeds in two parts. First, we show that if the voters in N would additionally buy p, then they would spend more than c(T). To prove this, we mainly use the priceability of W. Second, we show that there is an unchosen project in T which would give the voters in N a better satisfaction-to-cost ratio. For this part, C6 will be crucial, as it guarantees that cheaper projects are bought first; since µ is a DNS function, this leads to a higher satisfaction per cost. Together, these two parts contradict (1). For the first part, we want to show the following claim:

p W di(p ) > c(T). (2)

Since B > b, we obtain from C5 that

p P di(p ) = |N |B

i N di(p ).

Rewriting this inequality gives us

i N di(p ) |N |B

Having shown (2), we now advance to the second part of the proof. Here we want to compare the satisfaction per unit of money between W {p} and T. Since both the satisfaction function µ and the cost function c are additive, we can ignore the projects that appear both in W {p} and T when doing so. Let TW = T W . Then, we first observe that (1) implies by the additivity of µ that

µ(W \ TW ) µ(T \ (TW {p})). (3)

We apply the same idea to (2). Since for all p W it holds that P i N di(p ) c(p ) we get that X

p W \TW di(p ) > c(T \ (TW {p})). (4)

We now show that T \ (TW {p}) = . Assume for contradiction that T \(TW {p}) = , then µ(T \(TW {p})) = 0. By (3) this implies µ(W \TW ) = 0 and hence W \TW = Then, however, both sides of (4) evaluate to 0; a contradiction. Thus, we know that c(T \ (TW {p})) > 0. By putting (3) and (4) together, we get that

µ(W \ TW ) P p W \TW P i N di(p ) < µ(T \ (TW {p}))

c(T \ (TW {p})) .

Since µ and c are additive, we can rewrite this inequality as X

µ(p ) P i N di(p ) < X

t T \(TW {p})

Now we use the fact that min( a

d) to obtain the following:

min p W \TW

µ(p ) P i N di(p )

µ(p ) P i N di(p )

t T \(TW {p})

c(t) max t T \(TW {p})

Let pmin = arg minp W \TW n µ(p ) P

i N di(p ) o and tmax =

arg maxt T \TW n µ(t)

c(t) o . Then it follows that

c(pmin) µ(pmin) P i N di(pmin) < µ(tmax)

c(tmax) . (5)

In other words, pmin has a lower normalized satisfaction than tmax. Since µ is a DNS function, we can conclude that c(tmax) c(pmin). By the first condition of DNS functions, this implies µ(pmin) µ(tmax). However, then for the second inequality of (5) to hold, we must have P i N di(pmin) > c(tmax), a contradiction to C6.

First, we observe that from the MES family of rules MES[µ#] satisfies the conditions of the theorem.

Corollary 4.6. MES[µ#] satisfies µ-PJR-x for all DNS functions µ. Two further rules for which we can always find such a price system are the PB versions of sequential Phragm en (Phragm en 1894; Brill et al. 2017) and the maximin support method (S anchez-Fern andez et al. 2021). For the definitions of these two rules, we refer to the full version of this paper (Brill et al. 2023). Corollary 4.7. Sequential Phragm en and the maximin support method provide µ-PJR-x for all DNS functions µ. Finally, we can show that DNS is, in a sense, a necessary restriction. Namely, we can show that for any function mapping costs to satisfaction in a way that violates DNS, we can find an instance such that MES[µ#] does not satisfy PJR-x for that instance. We give an informal statement of the theorem here and a full statement and proof in the full version of this paper (Brill et al. 2023). Proposition 4.8. Let µ be an additive satisfaction function that is not a DNS function. Then there exists an ABB instance (A, P, c, b) with satisfaction function µ such that MES[µ# ] violates µ-PJR-x.

5 Conclusion We have studied proportionality axioms for participatory budgeting elections based on approval ballots. Our results can be summarized along two main threads: 1. If strong (i.e., EJR-like) proportionality guarantees are desired, then it is necessary to know the satisfaction function, as different satisfaction functions may lead to incompatible requirements (Proposition 3.6). If the satisfaction function is known and belongs to the class of DNS functions, however, we can guarantee EJR up to any project using a polynomial-time computable variant of MES tailored to this function (Theorem 3.5). 2. If the proportionality requirement is weakened to a PJRlike notion, there is no need to know the satisfaction function precisely: We identify a large class of satisfaction functions so that PJR up to any project is achievable for all those functions simultaneously (Theorem 4.5). We identify a class of voting rules that achieve this, including Phragm en s sequential rule, the maximin support method, and a variant of MES. (Among those three rules, the MES variant is the only rule that additionally satisfies EJR w.r.t. the cardinality-based satisfaction function.) It is open whether we can even achieve EJR-x (or even PJR-x) in polynomial time for additive non-DNS functions. Here, it seems crucial to further identify rules besides MES providing proportionality guarantees for PB. Furthermore, it would be interesting to push the boundaries of Theorem 4.5; for example, can we soften the assumption that we use the same satisfaction function for all voters? It is also an open question whether proportional outcomes can be computed in polynomial time for satisfaction functions that are not additive (e.g., for submodular or subadditive satisfaction functions). Looking beyond the approvalbased setting, it would be interesting to extend our framework to general (additive or non-additive) utility functions.

Acknowledgements We thank Dominik Peters and Piotr Skowron for helpful comments. This work was supported by the Austrian Science Fund (FWF) under the research grants P31890 and J4581 and by the Deutsche Forschungsgemeinschaft (DFG) under the grant BR 4744/2-1 and the Graduiertenkolleg Facets of Complexity (GRK 2434).

References Aziz, H.; Brill, M.; Conitzer, V.; Elkind, E.; Freeman, R.; and Walsh, T. 2017. Justified representation in approvalbased committee voting. Social Choice and Welfare, 2(48): 461 485. Aziz, H.; and Lee, B. E. 2021. Proportionally Representative Participatory Budgeting with Ordinal Preferences. In Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI), 5110 5118. Aziz, H.; Lee, B. E.; and Talmon, N. 2018. Proportionally representative participatory budgeting: Axioms and algorithms. In Proceedings of the 17th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 23 31. Baumeister, D.; Boes, L.; and Laußmann, C. 2022. Time-Constrained Participatory Budgeting Under Uncertain Project Costs. In Proceedings of the 31st International Joint Conference on Artificial Intelligence (IJCAI), 74 80. Brill, M.; Forster, S.; Lackner, M.; Maly, J.; and Peters, J. 2023. Proportionality in Approval-Based Participatory Budgeting. ar Xiv preprint ar Xiv:2302.03672. 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. AAAI Press. Caragiannis, I.; Kurokawa, D.; Moulin, H.; Procaccia, A. D.; Shah, N.; and Wang, J. 2019. The unreasonable fairness of maximum Nash welfare. ACM Transactions on Economics and Computation (TEAC), 7(3): 1 32. Chamberlin, B.; and Courant, P. 1983. Representative Deliberations and Representative Decisions: Proportional Representation and the Borda Rule. American Political Science Review, 77(3): 718 733. Chen, J.; Lackner, M.; and Maly, J. 2022. Participatory Budgeting with Donations and Diversity Constraints. In Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI), 9323 9330. Fairstein, R.; Vilenchik, D.; Meir, R.; and Gal, K. 2022. Welfare vs. Representation in Participatory Budgeting. In 21st International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 409 417. Hershkowitz, D. E.; Kahng, A.; Peters, D.; and Procaccia, A. D. 2021. District-fair participatory budgeting. In Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI), 5464 5471. AAAI Press. Jain, P.; Sornat, K.; Talmon, N.; and Zehavi, M. 2021. Participatory Budgeting with Project Groups. In Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI), 276 282.

Lackner, M.; Maly, J.; and Rey, S. 2021. Fairness in Long Term Participatory Budgeting. In Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI), 299 305. Lackner, M.; and Skowron, P. 2022. Multi-Winner Voting with Approval Preferences. Springer. Laruelle, A. 2021. Voting to select projects in participatory budgeting. European Journal of Operational Research, 288(2): 598 604. Los, M.; Christoff, Z.; and Grossi, D. 2022. Proportional Budget Allocations: A Systematization. In Proceedings of the 31st International Joint Conference on Artificial Intelligence (IJCAI), 398 404. Peters, D.; Pierczy nski, G.; Shah, N.; and Skowron, P. 2021. Market-Based Explanations of Collective Decisions. In Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI), 5656 5663. AAAI Press. Peters, D.; Pierczy nski, G.; and Skowron, P. 2021. Proportional participatory budgeting with additive utilities. In Proceedings of the 35th Conference on Neural Information Processing Systems (Neur IPS), 12726 12737. 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. Phragm en, L. E. 1894. Sur une m ethode nouvelle pour r ealiser, dans les elections, la repr esentation proportionnelle des partis. Ofversigt af Kongliga Vetenskaps-Akademiens F orhandlingar, 51(3): 133 137. S anchez-Fern andez, L.; Elkind, E.; Lackner, M.; Fern andez, N.; Arias-Fisteus, J.; Basanta-Val, P.; and Skowron, P. 2017. Proportional Justified Representation. In Proceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI), 670 676. S anchez-Fern andez, L.; Fern andez, N.; Fisteus, J. A.; and Brill, M. 2021. The Maximin Support Method: An Extension of the D Hondt Method to Approval-Based Multiwinner Elections. In Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI), 5690 5697. AAAI Press. Sreedurga, G.; Bhardwaj, M. R.; and Narahari, Y. 2022. Maxmin Participatory Budgeting. In Proceedings of the 31st International Joint Conference on Artificial Intelligence (IJCAI), 489 495. Talmon, N.; and Faliszewski, P. 2019. A framework for approval-based budgeting methods. In Proceedings of the 33rd AAAI Conference on Artificial Intelligence (AAAI), 2181 2188. AAAI Press.