# proportional_budget_allocations_towards_a_systematization__9df3fedc.pdf

Proportional Budget Allocations: Towards a Systematization

Maaike Los1 , Zo e Christoff1 , Davide Grossi1,2

1University of Groningen 2University of Amsterdam {m.d.los, z.l.christoff, d.grossi}@rug.nl

We contribute to the programme of lifting proportionality axioms from the multi-winner voting setting to participatory budgeting. We define novel proportionality axioms for participatory budgeting and test them on known proportionality-driven rules such as Phragm en and Rule X. We investigate logical implications among old and new axioms and provide a systematic overview of proportionality criteria in participatory budgeting.

1 Introduction

First introduced in Porto Alegre, Brazil in 1988, Participatory budgeting (PB) is a democratic budgeting practice in which citizens are consulted, through some voting method, on how to best allocate a given budget to public projects. The practice is attracting increasing attention from both democracy practitioners worldwide and researchers, among others within computational social choice [Aziz and Shah, 2021]. The axiomatic study of PB has formulated a number of criteria for the desirable behaviour of participatory budgeting methods, or PB rules. Special attention has been dedicated to forms of fairness or proportionality . Intuitively, one may want a PB rule to output a division of the available budget over the projects that reflects divisions in the voters preferences. A variety of proportionality axioms has been proposed in recent literature, and this paper provides a first systematization of the axiomatic landscape of proportionality in PB and its special case of multi-winner voting (MWV, [Faliszewski et al., 2017]), or committee selection, that is, a PB setting where all projects (referred to as candidates) have identical cost.

State of the art. The current understanding of proportionality in PB is rooted in MWV [Skowron et al., 2017; Peters, 2018]. A key fairness axiom in MWV is justified representation (JR) [Aziz et al., 2017]. In short, JR requires that if a large enough group of voters agrees about a candidate, there is at least one candidate in the chosen committee that at least one of the group members approves. Proportionality requirements have been added with the axioms of extended justified representation (EJR) [Aziz et al., 2017] and proportional justified representation (PJR) [S anchez-Fern andez et al., 2017], following the intuition that if a larger group agrees

about more candidates, they should be represented by more candidates in the winning committee. Aziz et al. [2018] generalize these concepts from MWV to PB within an approval voting framework. A related fairness concept is the core [Fain et al., 2016]. A set of projects, or bundle, is a core bundle if there is no subset of agents who can afford a different bundle (with their own share of the total budget) where every agent in that subset gets more utility than in the chosen bundle. In [Peters and Skowron, 2020], two MWV rules considered to be proportional Proportional Approval Voting (PAV) and Phragm en s rule (or simply Phragm en) are analysed, and shown to guarantee different types of proportionality. PAV induces a fair distribution of welfare, so every group of agents gets a utility proportional to its size, while Phragm en can be seen as inducing a fair distribution of power: the influence of a group of agents is proportional to its size. The authors introduce two new proportionality axioms: priceability and laminar proportionality (LP), and a new rule, Rule X, that is similar to both PAV and Phragm en, but satisfies both new axioms and the aforementioned EJR. Finally, work has started exploring the logical relations between the proportionality axioms proposed in the literature. For instance, Peters et al. [2021] show that, in MWV, the core implies EJR, PJR, and JR. Moving to PB, research has focused on assessing the extent to which the above MWV axioms and rules can be meaningfully generalised to PB. Pierczy nski et al. [2021] generalise Rule X and EJR to PB, and show that, even in this context, Rule X satisfies EJR.1 The PB variant of Rule X is also shown to satisfy an approximation of the core and the axiom of priceability for PB. PAV is generalised to PB too, and shown to fail EJR without the unit-cost assumption.

Contribution. We make two contributions. First, we complete the study of proportionality for Phragm en and Rule X in the PB setting with respect to the axioms mentioned above (Table 3). To do so, we propose novel generalizations of PJR and LP (Definitions 7 and 11) from the MWV to the PB setting. Second, we provide an overview of the logical relations between proportionality axioms in MWV and PB, establishing several novel results (see Figure 1). The resulting picture contributes to a systematization of how proportionality is interpreted in PB. Only selected proofs are provided.

1Pierczy nski et al. [2021] call Rule X in the PB setting method of equal shares (MES). For simplicity we stick to the term Rule X.

Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence (IJCAI-22)

priceability

[Peters and Skowron, 2020]

on laminar instances

[Pierczy nski et al., 2021] Theorem 4

subject to u-afford

Corollary 1 on laminar instances

PJR-up-to-one

EJR-up-to-one

Figure 1: Relations among proportionality axioms in PB. Dashed lines indicate relations that only hold in MWV. Arrows are labelled either by our results or the paper where they have been proven. Some of the implications only hold under certain conditions or restrictions: laminar instances (Definition 10), and unanimity affordability (uafford, Definition 12). Transitive arrows are omitted. Absence of arrows denotes the existence of a counterexample.

2 Preliminaries 2.1 The Participatory Budgeting (PB) Problem We denote the set of projects (or candidates) by C = {c1, c2, ..., cm} and the set of voters by N = {v1, v2, ..., vn}. Each voter i comes with a function ui assigning a utility to all projects. In the fully general setting of utility-based PB, ui : C [0, 1]. In contrast, in the special case of approval-based PB, the utility function is restricted to two values: ui : C {0, 1}, determining voter i s approval set Ai = {c C : ui(c) = 1}. The utility of a set of projects T C for a set of voters S N is defined additively as: u S(T) = P i S P c T ui(c). A profile P is a vector of the utility functions of all voters: P = (u1, ..., un). If utilities are approval-based we denote with C(P) the set of all projects occurring in the approval sets in P. A function cost: C Q+ assigns a cost to every project. The cost of a set of projects T is given by cost(T) = P c T cost(c). The total budget is denoted by l. If l is not mentioned, it is equal to 1. Hence, an election instance (also called a PBinstance) E = (N, C, cost, P, l) consists of a set of voters N, a set of projects C, a cost function, a profile P, and a budget l. If all else is clear in context, we abbreviate this to E = (P, l). A voting rule R maps an election instance E to a winning bundle W. A PB-instance where for all i N ui : C {0, 1} is called approval-PB-instance. The special case of an approval-PB-instance in which all projects have the same cost is called a MWV-instance. In such MWV setting, we refer to a bundle as a committee.

2.2 Voting Rules We focus on three proportionality-inspired rules: (sequential) Phragm en, proportional approval voting (PAV) and Rule X. Below, we recall the generalizations of Phragm en, PAV, and Rule X to PB introduced by Pierczy nski et al. [2021]. Phragm en Every voter gets currency continuously at the rate of one unit of currency per unit of time. At the first moment t when there is a group of voters S who all approve a not-yet-selected project c, and who together have cost(c) units of currency, the rule adds c to the bundle and asks the

project cost utilities Winning bundles c1 0.4 1 0.7 0.1 0 c2 0.3 0.3 0.4 0 0.4 c3 0.7 0.1 0.2 0.4 0.4 c4 0.35 0 0.4 0.2 1 v1 v2 v3 v4 Phragm en PAV Rule X

Table 1: The profile used in Examples 1 and 2. Each column contains the utilities per project of a voter. The budget l = 1.

voters from S to pay the cost of c (i.e., the rule resets the balance of each voter from S), while the others keep their sofar earned money. The process stops when it would select a project which would overshoot the budget. PAV The winning bundle W of PAV is the bundle with cost(W) l that maximises the score PAV-score(W) = P i N 1 + 1

3 + + 1 |W Ai| .

Rule X The rule starts by giving each voter an equal fraction of the budget. In case of a budget of 1, each of the n voters gets 1

n unit of currency. We start with an empty bundle W = and sequentially add projects to W. To add a project c to W, the voters have to pay for c. Write pi(c) for the amount that voter i pays for c; we will need that P i N pi(c) = cost(c). Let pi(W) = P c W pi(c) 1

n be the total amount voter i has paid so far. For ρ 0, we say that a project c / W is ρaffordable if P i N min( 1

n pi(W), ui(c) ρ) = cost(c). The rule iteratively selects a project c / W that is ρ-affordable for a minimum ρ. Individual payments are given by pi(c) = min( 1

n pi(W), ui(c) ρ). If no project is ρ-affordable for any ρ, Rule X terminates and returns W. Remark 1. Note that Phragm en and PAV work with approval-based while Rule X with utility-based ballots. In what follows, when discussing the first two rules, we will therefore presuppose approval-PB-instances. Notice also that all three rules are non-resolute. Example 1. Consider the profile in Table 1. To get the approval profile needed for Phragm en and PAV, we binarize the utility function using a threshold of 0.3: voters approve a project when it yields utility of at least 0.3. Approved projects are shaded. Phragm en will first select c2 at time t = 0.1, which leaves voter v3 with 0.1 units of currency. Then at t = 0.275, v2 and v4 can together buy c4, which leaves v1 with 0.175 and v3 with 0.275. After adding c4, the rule ends since both remaining projects are not affordable and outputs W = {c2, c4}. For PAV, we compute the PAV-score of four sets: PAV-score({c1, c4}) = 3.5, PAV-score({c1, c2}) = 4, PAV-score({c2, c3}) = 4.5, and PAV-score({c2, c4}) = 4 (clearly, smaller sets have a lower score and larger sets are not affordable). Hence, PAV will select W = {c2, c3}. Rule X starts by giving every voter 1

4 unit of currency. First, c4 is ρaffordable for ρ = 0.35

1.6 0.219, then, for ρ = 0.4

1.8 0.222, c1 is ρ-affordable. After selecting c1, the sum of the remaining amounts of all voters is 0.25, so the other projects are not ρ-affordable for any ρ. Hence, Rule X returns W = {c1, c4}.

2.3 Known Proportionality Axioms We recall axioms for PB from Pierczy nski et al. [2021] that generalize known MWV axioms. We start with the axioms of

Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence (IJCAI-22)

core and extended justified representation (EJR). Definition 1 (Core). For a given PB-instance E = (N, C, cost, P, l), a bundle W is in the core if for every S N and T C with |S| cost(T )

l n there exists i S such that ui(W) ui(T). A voting rule R satisfies the core property if for each PB-instance E the winning bundle R(E) is in the core. To define EJR, we first introduce (α, T)-cohesiveness: Definition 2 ((α, T)-cohesiveness). A group of voters S is (α, T)-cohesive for α : C [0, 1] and T C, if |S| cost(T )

l n and if it holds that ui(c) α(c) for every voter i S and each project c T. Definition 3 (Extended justified representation). A rule R satisfies extended justified representation (EJR) if for each PB-instance E and each (α, T)-cohesive group of voters S, there is a voter i S such that ui(R(E)) P c T α(c). In Pierczy nski et al. [2021], a weakening of EJR is considered, to which we refer as EJR-up-to-one. Definition 4 (Extended justified representation up to one project). A rule R satisfies extended justified representation up to one project (EJR-up-to-one) if for each PB-instance E and each (α, T)-cohesive group of voters S, there is a voter i S such that ui(R(E)) P c T α(c) or for some a C it holds that ui(R(E) {a}) > P c T α(c). In MWV, Definitions 3 and 4 are equivalent: Proposition 1. Def. 3 and Def. 4 are equivalent in MWVinstances. We now turn to priceability, for which the notion of price system needs to be introduced first. Definition 5 (Price systems). A price system is a pair ps = (b, (pi)i N) where b 1 is the initial budget, and for each voter i N, there is a payment function pi : C R such that (1) a voter can only pay for projects she gets at least some utility from: if ui(c) = 0, then pi(c) = 0 for each i N and c C, and (2) each voter can spend the same budget of b

n units of currency: P c C pi(c) b

n for each i N. Definition 6 (Priceability). A rule R satisfies priceability (is priceable) if for each PB-instance E, there exists a price system ps = (b, (pi)i N) that supports R(E), that is: (1) for each c R(E), the sum of the payments for c equals its price, i.e., P i N pi(c) = cost(c); (2) no project outside of the winning bundle gets any payment, i.e., for all c / R(E), P

i N pi(c) = 0; (3) there exists no nonselected project whose supporters in total have a remaining unspent budget of more than its cost, i.e., for all c / R(E), P i N s.t. ui(c)>0 b n P c R(E) pi(c ) cost(c).

Remark 2. The above properties are defined for PB. Throughout the paper, when needing to refer to the MWV specialization of a PB axiom, we will assume the axiom is defined on MWV-instances. We say that a rule satisfies an axiom in MWV-instances if, for all MWV-instances, the rule s winning bundle satisfies the axiom. Observe also that, since Phragm en and PAV are defined on approval-PB-instances, when we assess whether they satisfy an axiom, we consider the axiom only with respect to approval-PB-instances.

3 Two Novel Axioms for PB 3.1 Proportional Justified Representation in PB S anchez-Fern andez et al. [2017] define proportional justified representation for MWV (we refer to it as MWV-PJR here). We generalize this axiom to PB based on the generalisation of EJR provided by Pierczy nski et al. [2021]. Two steps are involved: dropping the unit-cost assumption, and allowing arbitrary utilities instead of just approval ones.

Definition 7 (Proportional justified representation). A rule R satisfies proportional justified representation (PJR) if for each PB-instance E and (α, T)-cohesive group of voters S, X

c R(E) (max i S ui(c)) X

c T α(c). (1)

The intuition is that, in the winning bundle, for each cohesive group S (cohesive in that S agrees to a certain degree about the set of projects T) there should be enough projects to which at least one voter in S assigns enough utility.

Example 2. Consider the profile in Table 1, with the bundle W = {c2, c3} as selected by PAV. Now consider the group S = {v1, v2}. Probably both voters in S are happy that c2 is selected, but they would both get more utility from c1 than from the selected c2 or c3. Also, if each of them would get their share of the total budget ( 1

4), they could together afford the set T = {c1}. Intuitively then, W is not a fair bundle considering voters v1 and v2. Let us look at it more formally. S is (α, T)-cohesive for α(c1) = 0.7 (α(c2), α(c3) and α(c4) are arbitrary) since the voters in S can afford T with their share of the budget, and for both of them u(c1) α(c1). However, Equation 1 is not satisfied: P c W (maxi S ui(c)) = 0.4 + 0.2 = 0.6, while P c T α(c) = 0.7. This shows that in the given election instance, the bundle W does not satisfy PJR.

Our definition of PJR for PB is rather different from its MWV variant. It requires some work to show that the proposed definition reduces to the definition of MWV-PJR under unit-cost assumption and approval preferences. First of all, let us recall the definition of MWV-PJR:

Definition 8 (PJR for MWV [S anchez-Fern andez et al., 2017]). An approval based voting rule R satisfies PJR for MWV (MWV-PJR) if for every ballot profile P and committee size k, the rule outputs a committee W = R(P, k) s.t.: for every ℓ k and every ℓ-cohesive set of voters S N, it holds that |W ( i SAi) | ℓ, where a set S is ℓ-cohesive if |S| ℓ n

k and | i S Ai| ℓ.

We will need the following lemma:

Lemma 1. Let E = (N, C, cost, P, l) be an approval-PBinstance where for all projects c, cost(c) = 1

k. Then: (a) for given α : C [0, 1] and T C, any group of voters S N that is (α, T)-cohesive is also ℓ-cohesive for ℓ= |T | with T = {c T : α(c) > 0}; and (b) for every group S that is ℓ-cohesive there are T C with |T| = ℓand α : C [0, 1] with α(c) = 1 for all c C, such that S is (α, T)-cohesive.

Theorem 1. MWV-PJR and PJR are equivalent in MWVinstances.

Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence (IJCAI-22)

Proof Sketch. We show that on MWV-instances, Definitions 7 and 8 are equivalent. PJR MWV-PJR Assume that a rule R satisfies PJR, and take an arbitrary MWV-instance E. Because E satisfies the assumptions of unit-cost and approval based voting, the fact that R satisfies PJR boils down to the following: for all S, α : C [0, 1], and T C with |S| |T| n

k and for which ui(c) α(c) for all i S and for all c T, it is the case that |R(E) ( i SAi)| P c T α(c). Take arbitrary S N and ℓ k and suppose that S is ℓ-cohesive. According to Lemma 1(b), there are T C with |T| = ℓand α : C [0, 1] with α(c) = 1 for all c C, such that S is (α, T)-cohesive. Because R satisfies PJR, this implies that |R(E) ( i SAi)| P c T α(c). However, because of our choice of T and α, we know that P c T α(c) = |T| = ℓ, so |R(E) ( i SAi)| ℓ, which shows that R satisfies MWV-PJR. MWV-PJR PJR Assume that a rule R satisfies MWV-PJR. Take arbitrary MWVinstance E, and suppose that a group S is (α, T)-cohesive. Then according to Lemma 1(a), when we take T = {c T : α(c) > 0}, S is ℓ-cohesive for ℓ= |T |. Because R satisfies MWV-PJR, it follows that |R(E) ( i SAi)| ℓ= |T |. By definition of T , |T | P c T α(c) = P c T α(c), so |R(E) ( i SAi)| P c T α(c) as desired.

Remark 3. To our knowledge, besides Definition 7, the only generalization of MWV-PJR to PB is from Aziz et al. [2018]. They define an axiom called Strong-BPJR-L (where L stands for the budget limit, to which we refer here as ℓ) that requires the following: For a budget l, a bundle W satisfies Strong BPJR-L if for all ℓ [1, l] there does not exist a set of voters S N with |S| ℓn

l , such that cost( i SAi) ℓbut cost(( i SAi) W) < ℓ. It is possible to generalise this definition further to allow arbitrary utilities instead of approval votes. However, note that the requirement in this definition is not that for every ℓ-cohesive S the utility of the projects they all approve that are selected is at least ℓ, but rather the cost of this set of projects. Although this is indeed a generalisation of MWV-PJR, as is shown by Aziz et al. [2018], we consider that the aim of PJR is to ensure a certain level of utility for every group of voters, rather than a certain cost. Definition 7 is equivalent to Strong-BPJR-L when assuming that a project s cost is directly proportional to a voter s utility from it. Like for EJR (Definition 4), we can add an up-to-oneproject condition to PJR: Definition 9 (Proportional justified representation up to one project). A rule R satisfies proportional justified representation up to one project (PJR-up-to-one) if for each PBinstance E and each (α, T)-cohesive group of voters S, P c R(E)(maxi S ui(c)) P c T α(c) or for some a C it holds that P c R(E) {a}(maxi S ui(c)) > P c T α(c).

3.2 Laminar Proportionality in PB The basic idea of LP for MWV [Peters and Skowron, 2020] is that if we know about a strict separation between different parties, we can divide the chosen projects proportionally over the parties. We generalize this notion to PB in the approval voting setting by taking the budget l instead of the bundle size k, and by using the cost of each project instead of unit-cost.

c3, 3 c2, 3 c5, 4 c1, 2 c4, 2 c6, 1 v1 v2 v3

Table 2: Example of a laminar proportional bundle W (shaded) in a laminar election instance. Each column represents the approval set of a voter (written beneath it), and each box shows a project with its cost. E.g., voter v2 approves c6, c1, c2, and c3 and cost(c5) = 4.

Definition 10 (Laminar PB-instances). An approval-PBinstance (P, l) is laminar if either: (1) P is unanimous and cost(C(P)) l; (2) there is c C(P) such that c Ai for all Ai P, the profile P c (i.e., P once we remove c) is not unanimous and instance (P c, l cost(c)) is laminar (with P c = (A1\{c}, ..., An\{c})); or (3) There are two laminar PB-instances (P1, l1) and (P2, l2) with C(P1) C(P2) = and |P1| l2 = |P2| l1 such that P = P1+P2 and l = l1+l2.

Example 3. The instance P in Table 2 associated with the budget l = 10 is laminar. The instance P1 with v1 and v2 and projects c1, c2, and c3 with limit l1 = 6 satisfies the first item of Definition 10, as does the instance P2 with only voter v3 and projects c4 and c5, and limit l2 = 3. Those two instances can be added by Definition 10, item 3, since |P1| l2 = 2 3 = 1 6 = |P2| l1. Then c6 can be added by Definition 10, item 2, to get P with limit l = 6 + 3 + cost(c6) = 10.

Definition 11 (Laminar proportionality). A rule R satisfies laminar proportionality (LP) if for every laminar PB-instance E = (P, l), R(E) = W where W is a laminar proportional bundle, i.e.: (1) if P is unanimous, then W C(P) (if everyone agrees, then part of the projects they agree on is chosen); (2) if there is a unanimously approved project c s.t. (P c, l cost(c)) is laminar, then W = W {c} where W is laminar proportional for (P c, l cost(c)); or (3) If P is the sum of laminar PB-instances (P1, l1) and (P2, l2), then W = W1 W2 where W1 is laminar proportional for (P1, l1) and W2 is laminar proportional for (P2, l2).

It is trivial that in case of unit-cost and budget k, these definitions are equivalent to the corresponding MWV definitions.

Example 4. Elaborating on Example 3, bundle W = {c1, c2, c4, c6} (grey in Table 2) is laminar proportional in that instance with a budget of l = 10. In (P1, l1), {c1, c2} is laminar proportional, as is {c4} in (P2, l2). Hence, {c1, c2, c4} is laminar proportional in (P1 +P2, l1 +l2), and {c1, c2, c4, c6} is laminar proportional in (P, l).

4 Proportionality Properties of Rules

Table 3 summarizes the findings of this section. The literature already provides several results about PAV: it does not satisfy the core, priceability, or LP in MWV (and hence not in PB either). In MWV-instances PAV satisfies PJR, but it does not in PB:

Proposition 2. PAV does not satisfy PJR.

We turn now to our analysis of Phragm en and Rule X.

Proposition 3. Phragm en satisfies PJR.

Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence (IJCAI-22)

PAV Phragm en Rule X MWV PB MWV PB MWV PB core [Aziz et al., 2017] [Brill et al., 2017] [Peters and Skowron, 2020] [Pierczy nski et al., 2021] EJR [Aziz et al., 2017] [Pierczy nski et al., 2021] [Brill et al., 2017] [Peters and Skowron, 2020] up-to-1 [Pierczy nski et al., 2021] PJR [S anchez-Fern andez et al., 2017] (Prop. 2) [Brill et al., 2017] (Prop. 3) [Peters and Skowron, 2020] up-to-1 (Prop. 6) Price [Peters and Skowron, 2020] [Peters and Skowron, 2020] (Prop. 4) [Peters and Skowron, 2020] [Pierczy nski et al., 2021] LP [Peters and Skowron, 2020] [Peters and Skowron, 2020] (Prop. 5) [Peters and Skowron, 2020] (Prop. 5)

Table 3: Three rules and the properties they satisfy: indicates satisfaction, failure. Shaded entries indicate new results, references to the corresponding propositions or literature are included for each entry. Recall that PAV and Phragm en are assessed on approval-PB-instances.

Proof. Assume towards a contradiction that there exist a group of voters S N, a set of projects T C, and a function α : C [0, 1] such that S is (α, T)-cohesive, and for this S, α, and T, the winning bundle W of Phragm en does not contain enough projects that voters from S like enough: P c W (maxi S ui(c)) < P c T α(c). Note that in approval PB-instances this boils down to |W i SAi| < P c T α(c). Because of (α, T)-cohesiveness, for every voter i S and each project c T, ui(c) α(c), so either α(c) = 0 or c Ai, and therefore P c T α(c) |T i SAi|. We write T for T i SAi, and W for W i SAi. Hence, |W | < |T | |T|. Let t be the moment when the rule stops: a project c is reached that would overshoot the budget. Clearly, cost(W) + cost(c) > 1, but cost(W) 1. Let x be the amount of virtual money earned by all voters so far, so t n = x = cost(W) + cost(c) + y, (2) where y 0 is the money that non-supporters of c have earned in the meantime. Because |W | < |T |, there must be some project in T that is not in W. The voters in S together have earned x

n |S|, and because S is (α, T)-cohesive, |S| cost(T) n, so x n |S| cost(T) n x

n = cost(T) x. (3)

From (2) and the fact that cost(W) + cost(c) > 1, it follows that x > 1 + y (and x > 1). From (3), it follows that the voters in S have earned enough together at time t to buy all projects from T (and therefore from T ), but have not done so. Hence, either they have also paid for projects not in T , or, if they only spent their money on projects in T , c must be in T , i.e. they do have the virtual money to buy T but it would overshoot the budget. In the first case, for every project not in T that members of S pay for, |W | grows by one (since they can only pay for projects they approve). In order to keep |W | < |T |, the mean amount of money they have paid at time t for such a project must be greater than the mean cost of projects in T . Otherwise, the number of projects they would pay for (that they approve of and that are selected) would exceed the number of projects in T . However, for each project not in T that voters from S pay for, they should (as a group) pay less than the cost of any project from T not yet selected. Otherwise, they would have paid earlier for a cheaper project from T . This is a contradiction. Hence, the voters from S only spent their money on projects from T , and c T . Let us assume that c is the last project from T that is not yet selected.2 Because the rule stops exactly when c can be paid by its supporters, we know that at

2If there are more projects from T not yet selected, we get that x cost(T ) n |S|, so x 1 still holds.

that point in time, the voters in S have earned exactly cost(T ) units of money, so t |S| = cost(T ). Hence, the total amount of money earned at time t is x = t n = cost(T ) n |S|. Be-

cause S is (α, T)-cohesive, cost(T ) cost(T) |S|

n , so x = cost(T ) n |S| |S|

n n |S| = 1. However, we also had that x > 1 + y > 1. Contradiction.

Proposition 4. Phragm en satisfies priceability. Peters and Skowron [2020] show that Phragm en does not satisfy EJR in MWVand, therefore, PB-instances. Since the core implies EJR, Phragm en does not satisfy the core neither in MWVnor in PB-instances. Proposition 5. Phragm en and Rule X do not satisfy LP.

Proof sketch. LP requires any affordable unanimously approved project to be selected, but Phragm en and Rule X do not necessarily select those if their cost is high enough compared to the other projects.

Proposition 6. Rule X satisfies PJR-up-to-one.

Proof. Rule X satisfies EJR-up-to-one [Pierczy nski et al., 2021]. Theorem 4 will show that EJR-up-to-one implies PJRup-to-one. Hence Rule X also satisfies PJR-up-to-one.

5 Relations Between Axioms We study the logical relationships among the axioms we introduced and report on the results recapitulated in Figure 1.

5.1 Priceability, PJR, EJR, and the Core We start by showing that PJR, EJR, and the core do not imply priceability in MWV-instances, even in laminar ones. Theorem 2. In laminar MWV-instances there exist bundles that satisfy PJR, EJR, or are in the core, but are not priceable. Since laminar MWV-instances are a specific type of MWVinstances, which are a specific type of PB-instances, the same result holds for MWV and PB. In MWV-instances, every priceable bundle satisfies PJR, as is shown by [Peters and Skowron, 2020, Prop. 1]. This raises the question whether this relation is also present in the PB setting. We show now that this is not the case. Theorem 3. There are priceable bundles not satisfying PJR.

Proof sketch. PJR is based on the utility of the voters being higher than some threshold α(c), while priceability only discriminates between utilities of 0 and utilities above zero. It is therefore possible to construct a PB-instance with a bundle that is priceable but does not satisfy PJR.

Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence (IJCAI-22)

From this result, it follows that priceability neither implies EJR nor the core. Priceability would otherwise imply PJR, since the core implies EJR, and EJR implies PJR (Theorem 4). These results hold even for MWV. Theorem 4. EJR(-up-to-one) implies PJR(-up-to-one).

5.2 Laminar Proportionality and Priceability We first show that in MWV-instances, and therefore also in PB-instances, priceability does not imply LP. Theorem 5. In laminar MWV-instances there exist priceable bundles that are not laminar proportional. However it is worth reporting that for a class of price systems (called balanced systems) we are able to prove that the implication goes through. Furthermore, LP implies priceability on laminar election instances even in the PB setting. Theorem 6. LP implies priceability in laminar PB-instances.

Proof sketch. By induction on the structure of laminar PBinstances. We show that for every bundle W that is laminar proportional for a laminar PB-instance (P, l), there exists a price system ps = (b, (pi)i N) where b = cost(W). Consider three cases. The first is the basis of the induction. If P is unanimous with cost(C(P)) l and W is laminar proportional for (P, l) (with cost(W) l), then W C(P), so voters can divide their budget over W. With an initial b = cost(W), all and only the projects in W can be bought. In the second case, a unanimously approved project c W such that W = W\{c} is laminar proportional. By the inductive hypothesis, we know that there exists a price system ps with initial budget b = cost(W ). Because c is unanimously approved, all voters could pay for c. We know that in ps , there was no project not in W that was affordable to its supporters. If every voter got cost(c)

n more budget, to spend entirely on c, c would get funded and no voter would have more unspent budget than before. Also, the initial budget of every voter is now b

n + cost(c)

n = cost(W )+cost(c)

n = cost(W )

n = b n units of money, and the initial budget is b = cost(W) and all the individual payment functions stay the same. Because for every project c in W the sum of the individual payments was equal to cost(c), this is also the case for every project in W. In the third case, the profile consists of two laminar profiles: P = P1 + P2 and l = l1 + l2, where W1 and W2 are laminar proportional for respectively (P1, l1), (P2, l2). Take W = W1 W2, which is by definition laminar proportional for (P, l). By the inductive hypothesis, there exist price systems ps1 = (b1, {p1,i}i N) and ps2 = (b2, {p2,i}i N) with initial budgets b1 = cost(W1) and b2 = cost(W2), and that |P1| l2 = |P2| l1. We can now define a price system ps that supports W as follows: ps = (b, (pi)i N) with b = cost(W) = b1 + b2, and for all voters i N, pi(c) = p 1,i(c) + p 2,i(c), where p 1,i and p 2,i are extended versions of respectively p1,i and p2,i that yield zero for the projects that those are not defined for. It is easy to check that ps supports W according to the criteria from Def. 6.

5.3 Laminar Proportionality and the Core Theorem 7. In laminar MWV-instances, there exist bundles that satisfy PJR, EJR, or are in the core, but do not satisfy LP.

Theorem 8. There exist laminar proportional bundles that do not satisfy PJR, EJR, or are not in the core. Theorem 8 holds because of instances where there is one relatively expensive unanimously approved project, that is included in any laminar proportional bundle, but where there are many cheap projects that can be satisfactory enough for a group of voters. We show now that under certain restrictions, laminar proportional bundles are in the core (and hence also satisfy EJR and PJR). To do that we define a property of bundles which we call unanimity-affordability (u-affordability): Definition 12. A bundle T is u-affordable (shortly, u-afford) w.r.t. instance (P, l) whenever for any unanimously approved project c C(P) there exists t T s.t. cost(t) cost(c). Since cost(c) cost(c), the definition is also satisfied if c T. We will show that in laminar PB-instances, a laminar proportional bundle satisfies the core if it is subject to u-afford, that is, if u-afford holds for the bundle inductively on the structure of the instance. Theorem 9. In laminar PB-instances, laminar proportional bundles subject to u-afford satisfy the core.

Proof sketch. The proof is by induction on laminar PB instances. Recall that a set of projects is in the core if for every group of voters S N and set of projects T C such that S can afford T with their share of the budget there is a voter i S such that ui(W) ui(T). The proof then shows that if for any unanimously approved project c in W either c is part of T, or there is some project in T that costs at least as much as c, then there exists a voter i S such that ui(W) ui(T). The interesting case concerns the step with a unanimous candidate c: any group S that could possibly block the core with bundle T should all prefer T over W or not be able to buy W. This is impossible because by u-afford T contains a project with a larger cost than c.

Since the core implies EJR and PJR (as showed by Pierczy nski et al. [2021] and Theorem 4), any laminar profile also satisfies EJR and PJR under the same restrictions. Note that in MWV-instances there always is a project in T that has cost of at least cost(c), so our restriction applies. Hence, there, laminar bundles are in the core, and so satisfy EJR and PJR. Corollary 1. In laminar MWV-instances, LP implies PJR, EJR, and the core.

6 Conclusions and Future Work Our study is a contribution towards the systematization of the axiomatic landscape of proportionality in PB (Figure 1, Table 3). With respect to proportionality-inspired rules, we showed that priceability and PB generalizations of PJR and LP do not discriminate between Phgragm en and Rule X (unlike EJR). We focused on the basic PB framework and on cardinal and approval-based utilities. Extending the study to richer PB settings (e.g., diversity constraints [Bredereck et al., 2018; Lang and Skowron, 2018; Aziz, 2019], project groups [Jain et al., 2021], negative attitudes [Talmon and Page, 2021], or resource types [Aziz and Shah, 2021]), or the yet more general ordinal preferences setting [Aziz and Lee, 2021], are natural avenues of future research.

Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence (IJCAI-22)

Acknowledgments

The authors are greatly indebted to Jan Maly, who pointed out a mistake in an earlier version of the paper, and to the anonymous reviewers of IJCAI/ECAI 22 for many helpful comments. Zo e Christoff acknowledges support from the project Social Networks and Democracy (VENI project number Vl.Veni.201F.032) financed by the Netherlands Organisation for Scientific Research (NWO). Davide Grossi acknowledges support by the Hybrid Intelligence Center, a 10-year program funded by the Dutch Ministry of Education, Culture and Science through the Netherlands Organisation for Scientific Research (NWO).

[Aziz and Lee, 2021] Haris Aziz and Barton E. Lee. Proportionally representative participatory budgeting with ordinal preferences. In Proceedings of the Thirty-Fifth AAAI Conference on Artificial Intelligence (AAAI 21), pages 5110 5118. AAAI Press, 2021. [Aziz and Shah, 2021] Haris Aziz and Nisarg Shah. Participatory budgeting: Models and approaches. In Tam as Rudas and P eli G abor, editors, Pathways between Social Science and Computational Social Science: Theories, Methods and Interpretations, pages 215 236. Springer, 2021. [Aziz et al., 2017] Haris Aziz, Markus Brill, Vincent Conitzer, Edith Elkind, Rupert Freeman, and Toby Walsh. Justified representation in approval-based committee voting. Social Choice and Welfare, 48:461 485, 2017. [Aziz et al., 2018] Haris Aziz, Barton E. Lee, and Nimrod Talmon. Proportionally representative participatory budgeting: Axioms and algorithms. In Proceedings of the 17th International Conference on Autonomous Agents and Multi Agent Systems (AAMAS 18), page 23 31, Stockholm, Sweden, 2018. International Foundation for Autonomous Agents and Multiagent Systems. [Aziz, 2019] Haris Aziz. A Rule for Committee Selection with Soft Diversity Constraints. Group Decision and Negotiation, 28(6):1193 1200, 2019. [Bredereck et al., 2018] Robert Bredereck, Piotr Faliszewski, Ayumi Igarashi, Martin Lackner, and Piotr Skowron. Multiwinner elections with diversity constraints. In Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, (AAAI 18), pages 933 940, New Orleans, Louisiana, 2018. AAAI Press. [Brill et al., 2017] Markus Brill, Rupert Freeman, Svante Janson, and Martin Lackner. Phragm en s voting methods and justified representation. In Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence (AAAI 17), page 406 413, San Francisco, California, 2017. AAAI Press. [Fain et al., 2016] Brandon Fain, Ashish Goel, and Kamesh Munagala. The core of the participatory budgeting problem. In Web and Internet Economics (WINE 2016), pages 384 399, Berlin, Heidelberg, 2016. Springer.

[Faliszewski et al., 2017] Piotr Faliszewski, Piotr Skowron, Arkadii Slinko, and Nimrod Talmon. Multiwinner voting: A new challenge for social choice theory. In Ulle Endriss, editor, Trends in Computational Social Choice, pages 27 47. AI Access, 2017. [Jain et al., 2021] Pallavi Jain, Krzysztof Sornat, Nimrod Talmon, and Meirav Zehavi. Participatory budgeting with project groups. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence (IJCAI 21), pages 276 282. International Joint Conferences on Artificial Intelligence, 2021. [Lang and Skowron, 2018] J erˆome Lang and Piotr Skowron. Multi-attribute proportional representation. Artificial Intelligence, 263:74 106, 2018. [Peters and Skowron, 2020] Dominik Peters and Piotr Skowron. Proportionality and the limits of welfarism. In Proceedings of the 21st ACM Conference on Economics and Computation (EC 20), page 793 794, New York, New York, 2020. Association for Computing Machinery. [Peters et al., 2021] Dominik Peters, Grzegorz Pierczy nski, Nisarg Shah, and Piotr Skowron. Market-based explanations of collective decisions. Proceedings of the Thirty-Fifth AAAI Conference on Artificial Intelligence (AAAI 21), 35(6):5656 5663, 2021. [Peters, 2018] Dominik Peters. Proportionality and strategyproofness in multiwinner elections. In Proceedings of the 17th International Conference on Autonomous Agents and Multi Agent Systems (AAMAS 18), pages 1549 1557, Stockholm, Sweden, 2018. International Foundation for Autonomous Agents and Multiagent Systems. [Pierczy nski et al., 2021] Grzegorz Pierczy nski, Piotr Skowron, and Dominik Peters. Proportional participatory budgeting with additive utilities. In Advances in Neural Information Processing Systems, volume 34, pages 12726 12737. Curran Associates, Inc., 2021. [S anchez-Fern andez et al., 2017] Luis S anchez-Fern andez, Edith Elkind, Martin Lackner, Norberto Fern andez, Jes us A. Fisteus, Pablo Basanta Val, and Piotr Skowron. Proportional justified representation. In Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence (AAAI 17), page 670 676, San Francisco, California, 2017. AAAI Press. [Skowron et al., 2017] Piotr Skowron, Martin Lackner, Markus Brill, Dominik Peters, and Edith Elkind. Proportional rankings. In Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI 17), pages 409 415, Melbourne, Australia, 2017. International Joint Conferences on Artificial Intelligence. [Talmon and Page, 2021] Nimrod Talmon and Rutvik Page. Proportionality in committee selection with negative feelings. Co RR, abs/2101.01435, 2021.

Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence (IJCAI-22)