Participatory Budgeting with Multiple Degrees of Projects and Ranged Approval Votes

1 Introduction

Participatory budgeting (PB) is a democratic voting paradigm that aggregates the opinions of citizens while deciding on how to fund the public projects [Cabannes, 2004; Shah, 2007; Sintomer et al., 2008; Wampler, 2010; R¨ocke, 2014].

Divisible PB assumes that the costs of the projects are totally flexible and any amount can be allocated to each of them [Airiau et al., 2019; Sreedurga et al., 2022b]. The existing work on indivisible PB, on the other hand, assumes that every project has a fixed cost that is to be allocated to the project if it is selected. However, many times in real-world, each project can be implemented upto different levels of sophistication. For example, a building can be built with wood or stone, depending on the amount allocated to it. That is, each project has a set of possible and permissible costs. Each cost in this set corresponds to a degree of sophistication of the project. In addition to choosing the set of projects that are to be funded, the mechanism designer must also choose a permissible cost for each of the selected projects. This idea of having multiple permissible costs for each project was first proposed in a survey by Aziz and Shah [Aziz and Shah, 2021], in which the authors called each of these costs a degree of completion. However, the idea still remained to be studied and our paper bridges this gap.

Preference elicitation methods typically studied in any voting framework include approval votes, ordinal votes, and cardinal votes. These methods also continue to be the most studied preference elicitation approaches in PB [Aziz et al., 2018; Talmon and Faliszewski, 2019; Rey et al., 2020; Jain et al., 2020; Fairstein et al., 2022; Sreedurga et al., 2022a; Benade et al., 2021; Shapiro and Talmon, 2017; Aziz and Lee, 2021; Sreedurga and Narahari, 2022; Peters et al., 2020]. However, PB is a setting with several attributes like costs attached to the projects. The preferences and utilities of the voters are thus much more complex. This propels the need to devise preference models specific to PB, as pointed out by Aziz and Shah [Aziz and Shah, 2021]. One step in this direction is the introduction of a special case of approval votes, called knapsack votes, by Goel et al. [Goel et al., 2019], where each voter reports her most favorite budget division. This idea however is criticised for its assumption that any project not in this division yields no utility to the voter.

Our paper is another step in the direction of preference modeling for PB. We introduce the approach of ranged approval votes, which strictly generalizes the approval votes. Each voter reports a lower bound and an upper bound on the cost that she thinks each project deserves. All the bounds are initially set to 0 by default. Voting proceeds in two steps. In the first step, the voter starts by approving the projects she likes. For these approved projects, only the upper bounds will automatically change to the highest permissible cost. In the second step, the voter may optionally change bounds for some of these approved projects, if she wishes to have a say on the amount they deserve. Note that this is cognitively not much more demanding than the approval votes since we do not force the voters to report the bounds. Notably, all our computational results can also be extended to more general utility functions with minor tweaks. Nevertheless, we present the results for ranged approval votes due to their cognitive simplicity and natural relevance in the model.

It needs to be mentioned that a work by Goel et al. [2019] views divisible PB as a model of indivisible PB where every unit of money in the cost corresponds to one possible degree of sophistication, and proposes a greedy algorithm. Their work however imposes knapsack constraint on each vote as well as assumes all lower bounds to be zero. Their model hence forms a very restricted special case of ours.

Our contributions. The primary goal of this paper is to systematically study the PB model where each project has a set of permissible costs. Such a study has been conducted by Talmon and Faliszewski [Talmon and Faliszewski, 2019] for approval-based PB, which is a special case of our model with every project having only one permissible cost. We generalize the PB rules and all the positive results in [Talmon and Faliszewski, 2019] to our model. Namely, we propose polynomial-time, pseudo-polynomial time, and PTAS algorithms. Followed by this, we present some results on parameter tractability using a recently introduced parameter scalable limit [Sreedurga et al., 2022a] and another novel parameter we introduce in the further sections. It needs to be highlighted that, as a part of our study, we also introduce and investigate some novel utility notions that are specific to our model and are not extensions of the literature. Finally, we propose some budgeting axioms for our model and examine their satisfiability with respect to our PB rules. All the axiomatic results are summarized in Table 1. We conclude by discussing the impact of our computational and axiomatic results and pointing out future directions.

Organization of the paper. We start by introducing the mathematical model in Section 2. We define different utility notions (some extended from the existing ones in the literature and some new) and the corresponding PB rules in Section 2.1. In Section 3, we analyze the computational complexity of our PB rules and suggest ways to cope up with intractabilities. In Section 4, we define budgeting axioms for our model and examine their satisfiability.

2 Model

In our model, a budget b is given. We denote the set of n voters by N = {1, . . . , n} and the set of m projects by P. Each project j ∈ P has tj possible degrees of sophistication captured by the set D(Pj) = {P 0 j , P 1 j , . . . , P tj j }. The cost of each degree P t j is indicated by ctj . We assume that c0j is zero for all j ∈ P and it corresponds to not funding the project j.

Each voter i ∈ N reports for every project j, a lower bound li(j) and an upper bound hi(j) such that li(j), hi(j) ∈ {c0j , . . . , ctj j } and li(j) ≤ hi(j). Let L and H respectively denote the collection all the lower bounds and upper bounds reported by all the voters.

Let D denote the set of all the possible degrees of all projects, or in other words, D = ⋃j∈P D(Pj). We denote the cost of a set S ⊆ D, ∑P t j ∈S ctj , by c(S) . Given a subset S ⊆ D, we use S(j) to denote the chosen degree(s) of project j in S. In other words, S(j) = S ∩ D(Pj). We use the shorthand notation cS (j) to denote c(S(j)) . We say a subset S ⊆ D is valid if c(S) ≤ b and |S(j)| = 1 for every j ∈ P . Let V denote the collection of all the valid subsets.

A PB instance with multiple degrees of sophistication is denoted by I = ⟨N,D, c, b,L,H⟩. Given an instance, the objective of a PB rule R is to output a valid subset S ∈ V.

2.1 The PB Rules

The PB rules we study are utilitarian rules. This implies that, given a function u that measures utility a voter derives from a subset of projects, the corresponding PB rule outputs a valid set of projects that maximizes the sum of utilities of all the voters, i.e., it outputs some S ∈ V such that ∑i∈N ui (S) is maximized. We say a subset S of projects is selected under a PB rule R if it maximizes the total utility of the voters. We say a project P t j ∈ D wins under a PB rule R if it belongs to some set that can be selected under R. Let R(I) be the collection of all the projects that win under the PB rule R, given an instance I.

Now, we only need to define different utility functions. Given the lower and upper bounds reported by the voters, we define the utility of a voter from a valid set S ∈ V in four ways. For each of these utility functions, we also give a shorthand notation for the utilitarian PB rule associated to it.

1. Cardinal utility (R|S| rule): Each voter i derives a utility of 1 from a project j if the cost of the chosen degree falls within the bounds specified by the voter. Thus, ui (S) = |j ∈ P : li(j) ≤ cS (j) ≤ hi(j)|, cS (j) ̸= 0.
2. Cost utility (Rc(S) rule): A voter i derives a utility of cS (j) from a project j if its value falls within the bounds specified by the voter.

1. Cost capped utility (R̂ c(S) rule): Each voter i derives a utility of cS (j) from a project j if the value falls within the bounds reported by her, a utility of hi(j) if cS (j) > hi(j), and a utility of 0 if cS (j) < li(j). That is, with slight abuse of notation, ui (S) = ∑j∈P ui (S, j), where ui (S, j) is defined as:

1. Distance disutility (R∥ ∥ rule): From every project j, each voter derives a disutility of 0 if the value falls within the bounds reported by her, a disutility of cS (j) - hi(j) if cS (j) > hi(j), and a disutility of li(j) - cS (j) if cS (j) < li(j). That is, with slight abuse of notation, di (S) = ∑j∈P di (S, j), where di (S, j) is defined as

follows:

The corresponding PB rule R∥ ∥ minimizes the total disutility.

The first two notions of utilities are the natural extensions of the notions considered in [Talmon and Faliszewski, 2019]. The former reflects that the voter is happy as long as the cost allocated to the project is acceptable to her, whereas the latter reflects that as the project gets more money, the voter gets happier if the cost is acceptable to her.

The second utility notion clearly assumes that if the project gets more money than what the voter thinks it deserves, voter derives zero utility. However, this need not always be the case in real-world. For example, say a voter will be happy to have an entertainment park in the neighborhood but feels that the park deserves any amount between 1000 and 5000 units. Now, if the park project is allocated 7000 units, the voter could still be happy that there is a park in the neighborhood but derive no more utility than 5000 (since it is the maximum value she thinks the park deserves). The third utility notion tackles such scenarios by modifying the second utility notion to cap the utility at hi(j) instead of dropping it to 0.

The first three utility notions assume that allocating any cost outside the range reported by the voter yields the same utility to her. However, in many situations, closer the cost of the project is to the acceptable range of the voter, higher is the satisfaction voter derives from it. For example, say a voter feels that a certain project is worth at least 1000 units. An outcome that allocates 900 units to it is likely to be more preferred by the voter over something that allocates 50 units to it. The fourth rule handles such situations by considering the distance between the cost allocated and the closest acceptable cost as the disutility. Farther the cost is from the acceptable range, higher is the amount misspent.

3 Computational Complexity

Here, we analyze the computational complexity of our PB rules. We strengthen the existing positive results in the literature [Talmon and Faliszewski, 2019] and also present a few new results on fixed parameter tractability. All the exact algorithms we present are based on dynamic programming. The approximation schemes we present depend on both dynamic programming as well as a clever rounding scheme.

3.1 The Rule R|S|

Recall that R|S| outputs a valid set that maximizes the sum of the utilities of voters, where the utility of a voter is defined as ui (S) = |j ∈ P : li(j) ≤ cS (j) ≤ hi(j)|. Talmon and Faliszewski [2019] prove that for the case with only one permissible cost for each project, a subset maximizing the utility can be computed in polynomial time. We strengthen this result and prove that even when there are multiple permissible costs for each project, a subset maximizing the total utility can be computed in polynomial time.

Theorem 1. For any instance I, a subset S ∈ V that is selected under R|S| can be computed in polynomial time.

Proof. We present an algorithm that uses dynamic programming. Let s(P t j ) denote the number of voters i such that li(j) ≤ ctj ≤ hi(j). Construct a dynamic programming table such that A(x, y) corresponds to the cost of cheapest valid subset of ⋃xj=1 D(Pj) such that the total score of projects in the set is exactly y.

Let F(y) ⊆ D(P1) such that s(P t 1 ) = y for every P t 1 ∈ D(P1). We compute the first row as: A(1, y) = min(ctj : P t j ∈ F(y)). All the remaining rows are computed recursively as follows: A(x, y) = min (A(x - t=1 (A(x - 1, y - s(P tx ) ) + ctx )). In addition to

1, y) , mintx computing this table, we store the sets corresponding to each entry in A in a separate table B as follows: if A(x, y) achieves the minimum value at A(x - 1, y), we copy B(x - 1, y) to B(x, y) and append P 0 j . If A(x, y) achieves the minimum value at A(x-1, y -s(P tx ))+ctx for some t ∈ [1, tx], we set B(x, y) = B(x - 1, y) ∪ {P tx }. Finally, we output the set at B(x, y) such that A(x, y) ≤ b and y is maximized.

Correctness. Recurrence ensures that for any entry in B, we select at most one project from D(Pj) for every j. While selecting the outcome from B, we ensured that its cost is within the budget. Hence, the output of the algorithmwill be a valid subset. Optimality follows from the way A is defined.

Running time. Each row in A corresponds to making a decision about one project from P, and hence the number of rows is m. Each column corresponds to a possible total score. Since we select only one project from each D(Pj) and maximum score of any degree of a project is n by definition, maximum total score is mn. Thus, we have mn columns. Computing each entry in row x takes O(tx) time. Thus, the running time is O(m2nt∗ ), where t∗ = maxj∈P tj .

3.2 The Rule Rc(S)

Recall that Rc(S) outputs a valid set that maximizes the sum of the utilities of voters, where the utility of a voter is:

Talmon and Faliszewski [2019] prove that for the case where each project has only one permissible cost, it is NP-hard to determine if there exists a feasible subset that guarantees a total utility of at least a given value. Since their model can be modeled as a special case of ours, the hardness easily follows.

Proposition 1. For an instance I and a value s, it is NP-hard to check if Rc(S) outputs a set with at least a total utility s.

Proof. Given a PB instance with approval votes (each project j has some cost c(j) and every voter reports a subset Ai of projects that she likes), we construct an instance for Rc(S) as follows: For every project j ∈ P, create exactly two degrees such that c0j = 0 and c1j = c(j). For each voter i, set li(j) = 0 for every project j and set hi(j) = c1j if and only if j ∈ Ai. Clearly, both the instances are equivalent and we skip the proof of correctness.

To cope up with the intractability, Talmon and Faliszewski [2019] prove that if every project has only one permissible cost, the problem has a pseudo-polynomial time algorithm and FPTAS. We extend both these results to our model with multiple permissible costs.

Proposition 2. For any instance I, a subset S ∈ V selected under Rc(S) can be computed in pseudo-polynomial time.

Proof. We multiply every s(P t j ) in the proof of Thm. 1 with ctj . DP tables are also constructed as explained in Thm. 1. The maximum score achievable by each P t j is nctj . The total score is upper bounded by nc(S) since at most a single project from each D is chosen into each B(x, y). This is bounded by nb since S ∈ V. Thus, the table size is O(mnb) and the time is O(mnt∗b), where t∗ = maxj∈P tj .

Theorem 2. There is an FPTAS for Rc(S).

Proof. The idea is inspired from one of the existing FPTAS algorithms of the knapsack problem [Ibarra and Kim, 1975]. We round the scores of all the projects and use the DP table explained in Thm. 1 on the modified instance.

Given an instance I, let M be the maximum score of a degree of project, i.e., M = maxj∈P,t∈[1,tj] s(P t j ). We can easily ensure that M ≤ OPT by eliminating all the project degrees that cannot be part of any set with cost within b. Take any ϵ ∈ (0, 1). Now, create new scores of all the projects as follows: α(P t j ) = ⌊ s(P t j )m ϵM ⌋. We construct the DP tables similar to those in Thm. 1, considering new scores. By the definition of α(P t j ) , for every j ∈ P and t ∈ [1, tj]:

Let S be the outcome of this DP algorithm. Say O denotes the optimal solution for I under Rc(S). Please note that the DP ensures that S is a valid set. Since S is the optimal solution for the modified scores,

Now, we prove that the approximation factor of (1-ϵ) holds.

Running Time: The table has m rows. The modified score of each degree of project is upper bounded by s(P t j )m ϵM , which is further bounded by mϵ due to the definition of M. Since the output is a valid set, it has at most m projects and the maximum possible total score is upper bounded by m2 ϵ , which is the number of columns. Computing each entry in row x takes O(tx) time. Thus, the running time is O( m3 t∗ ϵ ), where t∗ =maxj∈P tj.

Fixed Parameter Tractability

Recently, Sreedurga et al. [2022a] introduced a new parameter called scalable limit for PB. The authors observed that this value is often small in PB elections in real life (e.g., datasets at https://pbstanford.org/ where budget and all the costs are multiples of some really high value). Motivated by this, we prove that Rc(S) is in FPT w.r.t. scalable limit. Before that, we define the scalable limit in our model as follows:

Definition 1. For any instance I, we refer to maxP t j ∈D ctj GCD(c11 ,...,ctm m ,b) as the scalable limit (δ) of the instance.

Intuitively, we scale down all the costs and budget as much as possible, while ensuring that all these values continue to be integers. The scalable limit then refers to the cost of the costliest degree in D in this scaled down instance.

Proposition 3. For any instance I, computing a subset S ∈ V that is selected under Rc(S) is in FPT w.r.t. scalable limit δ.

Proof. We again prove this by constructing a DP table. Let k = 1 GCD(c11 ,...,ctm m ,b) . First, we get a new instance I ′ by scaling down all the costs and budget as follows: c′ t j = kctj and

b′ = kb. Then, construct the DP table similar to Theorem 1.

Running Time: The table has m rows. The modified cost of each degree of project is upper bounded by δ and hence the maximum score possible from each degree of a project is upperbounded by nδ. Since the output is a valid set, there can be at most m projects in it and hence the maximum possible total score is upper bounded by mnδ, which is the number of columns. Computing each entry in row x takes O(tx) time and the running time is O(m2nδt∗ ).

Proposition 4. For any instance I, computing a subset S ∈ V that is selected under Rc(S) is in FPT w.r.t. m.

The above proposition follows from the fact the total number of valid subsets is exponential in m (upper bounded by (t∗ )m, where t∗ = maxj∈P tj) and computing the total utility of any set under Rc(S) can be done in polynomial time.

3.3 The Rule R̂ c(S)

This rule is similar to the previous rule Rc(S), with the only difference being the way a voter is assumed to view the projects allocated higher cost than the approved limit. The utility is defined as ui (S) = ∑j∈P ui (S, j), where ui (S, j) is taken as defined in Section 2.1. The proof of the following result is deferred to the appendix [Sreedurga, 2023].

Proposition 5. Given an instance I, the following statements hold:

1. For any value s, it is NP-hard to determine if R̂ c(S) outputs a set that has a total utility of at least s.
2. A subset S ∈ V that is selected under R̂ c(S) can be computed in pseudo-polynomial time.
3. There is an FPTAS for R̂ c(S) .
4. Computing a subset S ∈ V that is selected under R̂ c(S) is in FPT w.r.t. scalable limit δ.
5. Computing a subset S ∈ V that is selected under Rc(S) is in FPT w.r.t. m.

3.4 The Rule R∥ ∥

Recall that R∥ ∥ outputs the feasible set that minimizes di (S) = ∑j∈P di (S, j), where di (S, j) is defined as in Section 2.1. It is worth bearing in mind that the results from Section 3.2 and Section 3.3 cannot be transferred since we have a minimization problem and the fact that we cannot upper bound the disutilities by b. We start the section by proving that this rule too is NP-hard, using a slightly different but simple reduction from the same problem (used in Proposition 1) solved by Talmon and Faliszewski [2019]. Then, we give a parameterized approximation algorithm, more specifically a parameterized FPTAS, which guarantees the approximation ratio when the parameter is small [Feldmann et al., 2020].

Proposition 6. For an instance I and a value s, it is NP-hard to determine if R∥ ∥ outputs a set that has a total disutility of at most s.

Proof. For a PB instance with approval votes (each project j has some cost c(j) and every voter reports a subset Ai of projects that she likes) and a positive value x, we construct an instance for Rc(S) as follows: For every project j ∈ P , create exactly two degrees such that c0j = 0 and c1j = c(j). For each voter i, set hi(j) = c(j) for every project j and set li(j) = c1j if and only if j ∈ Ai. Let Z = ∑i∈N c(Ai). Set s = Z - x.

Correctness. To prove the forward direction, say the approval-based PB instance is a YES instance. That implies, there exists a set S of projects such that ∑i∈N c(S ∩Ai) ≥ x. Now calculate the disutility of S under R∥ ∥. Then, di (S, j) = c(j) for every j ∈ Ai \ S and 0 otherwise. Therefore, di (S) = -c(Ai) - c(Ai ∩ S). Then, total utility from S = Z - ∑i∈N c(Ai ∩ S). Since the former is at least x, this total disutility is at most Z-x. The backward direction can be argued similarly.

Parameterized Approximation Algorithm (FPTAS)

The very high disutilities that are hard to be bound motivate us to propose a parameterized FPTAS, which has been of a great interest recently [Feldmann et al., 2020]. We consider a parameter that we call variance coefficient, γ, which, on being given an instance I, intuitively shows how divergent the disutilities of different degrees of projects in the instance are. It is captured by measuring the highest disutility a single project can have, relative to sum of the least possible disutilities from all the projects. We explain this formally below.

Given an instance I, for each degree of a project P t j ∈ D, we use qt j to denote the disutility the project will contribute to any set that contains it. We call this disutility contribution of P t j . Suppose for example, P t j ∈ S. That implies, cS (j) = ctj (∵ S is valid). Therefore,

It can be observed that, ∑i∈N di (S) = ∑P t j ∈S qt j .

Let qm = maxP t j ∈D qt j . That is, qm is the maximum of disutility contributions of all the degrees of all the projects. We use qσ to denote the sum of minimum disutility contributions from each D(Pj) , i.e., qσ = ∑j∈P mint∈D(Pj) qt j . Our parameter γ is the ratio qm/qσ. Intuitively, this parameter means that we want the disutility contribution from a single project not to be extremely higher than the sum of the least disutility contributions from all the m projects.

Theorem 3. For any instance I and ϵ ∈ [0, 1], a subset S ∈ V such that ∑i∈N di (S) ≤ (1 + ϵ)OPT can be computed in O( m3 γt∗ ϵ ) time, where OPT is the optimal possible total disutility under R∥ ∥, γ is the variance coefficient, and t∗ = maxj∈P tj.

Proof. The idea is similar to that in Thm. 2. We define new disutilities for each project by rounding their disutility contributions. We then construct a DP table using which we select a set. For each project P t j , we define α(P t j ) as follows:

We construct the DP tables A and B similar to those in Thm. 1, with a slight change the each column now represents the total disutility, and s(P t j ) is replaced by α(P t j ) defined in the above para. We output the set at B(x, y) such that A(x, y) ≤ b and y is minimized. Let S be the resultant outcome. Say O denotes the optimal solution for I under R∥ ∥. Please note that the DP ensures that S is a valid set. Since S is the optimal solution w.r.t. new disutilities (i.e., w.r.t. α's),

By the definition of α, we have

Now, we prove that the approximation factor of (1+ϵ) holds.

qσ is the sum of minimum possible disutility contribution from each D(Pj) . Any valid set should have one degree (degree 0 corresponds to not funding the project) from each D(Pj) . Since the optimal solution has to be a valid set, the optimal disutility must be at least qσ, i.e., OPT ≥ qσ. Applying this in Eqn. 7, results in ∑mj=1 qS(j) j ≤ (1+ ϵ)OPT.

Running time. Now, we need to check the running time of constructing the DP table. The table has m rows. The disutilities calculated for each degree of project is upper bounded by qt j m ϵqσ , which is further bounded by mγ ϵ (by the definition of γ, ∵ qt j ≤ qm). Since the output is a valid set, there can be at most m projects in the output and hence the maximum possible total disutility is upper bounded by m2 γ ϵ , which is the number of columns. Computing each entry in row x takes O(tx) time. Thus, the running time is O( m3 γt∗ ϵ ), where t∗ =maxj∈P tj.

Fixed parameter tractability. Here, we prove that R∥ ∥ is also in FPT with respect to the parameters δ or m.

Proposition 7. For any instance I, computing a subset S ∈ V that is selected under R∥ ∥ is in FPT w.r.t. scalable limit δ.

The proof of the above proposition is similar to the proof of Proposition 3. We scale down the costs of the projects and the budget as explained in that proof. Followed by this, the DP table and the output will be computed as explained in Proposition 7. The running time analysis is exactly the same as explained in Proposition 3

Proposition 8. For any instance I, computing a subset S ∈ V that is selected under R∥ ∥ is in FPT w.r.t. m.

The above result follows from the fact that when m is constant, we can exhaustively search all the valid sets for the set with optimal disutility.

4 Budgeting Axioms

An enormous amount of work has been done on the axiomatic study of PB with approval votes [Aziz et al., 2018; Aziz and Lee, 2019; Talmon and Faliszewski, 2019; Rey et al., 2020; Baumeister et al., 2020; Sreedurga et al., 2022a]. However, our PB model in which each project has a set of permissible costs is unique technically as well as realistically. This uniqueness demands the development of novel axioms applicable explicitly in such a setting. We introduce different axioms and investigate which of the PB rules introduced in Section 2.1 satisfy our axioms and which do not. We defer some proofs in this section to appendix [Sreedurga, 2023].

The first axiom implies that if the voters are narrowing down their interval towards a degree that was winning, then the degree still continues to win.

Definition 2 (Shrink-resistant). A PB rule R is said to be shrink-resistant if for any instance I, a voter i, any j ∈ P, it holds that a set S selected under R continues to be selected even if li(j) and hi(j) are shifted closer to cS (j) .

Proposition 9. All the four rules R|S|, Rc(S), R̂ c(S) , and R∥ ∥ are shrink-resistant.

Given an instance I, for each project j ∈ P, we define τj = {ctj : P t j ∈ D, ∀i ∈ N li(j) ≤ ctj ≤ hi(j)}. Let τj = max (τj) and τj = min (τj). The second axiom requires that if some range of costs is found to be acceptable unanimously by all the voters, then the cost allocated to the project must not go beyond this range.

Definition 3 (Range-abiding). A PB rule R is said to be range-abiding if for any instance I, a project j ∈ P, and a set S selected under R, it holds that τj ̸= ∅ =⇒ cS (j) ≤ τj.

Proposition 10. The rules R|S| and R∥ ∥ are range-abiding, whereas Rc(S) and R̂ c(S) are not.

Proof. First, we prove that Rc(S) and R̂ c(S) are not rangeabiding. Recall that b denotes the budget. Say we have a single project j with exactly two permissible costs, respectively equal to ⌊ b-1 n ⌋ and b. Say all the voters set li(j) = c1j . One voter i sets hi(j) = c2j , whereas all the remaining voters report c1j as the upper bound. Clearly, in a set S containing P 1 j , the utility from project j is at most b - 1. Whereas, if S selects P 2 j , the utility from j is equal to b (but all due to the utility of a single voter). Thus P 2 j is selected. Note that, in this example, τj = ⌊ b-1 n ⌋ and clearly c2j > τj .

Now, assume that R|S| and R∥ ∥ are not range-abiding. That is, in a set S selected under the rule, cS (j) > τj. Consider the set S′ = S \ {S(j)} ∪ {P t j : τj = ctj }. Clearly, S′ is valid since cS (j) > τj and S is valid. Also, ui (S′ , j) > ui (S, j) since the degree chosen in S′ is within the bounds reported by every voter (it gives the optimal utility of n for R|S| and the optimal disutility of 0 for R∥ ∥). Thus, S′ is a strictly better set and S must not be selected. This forms a contradiction.

The next axiom requires that increasing the budget should result in the winning degree of some project moving closer to the range of costs for it found to be acceptable unanimously by all the voters.

Definition 4 (Range-converging). A PB rule R is said to be range-converging if for any instance I, a set S selected for I under R, and a set S′ ̸= S selected under R on increasing the budget, it holds that whenever there is at least one project k with τk ̸= ∅, there also exists some project j ∈ P such that: cS (j) /∈ τj =⇒ |cS (j) - τj| > |cS′ (j) - τj|.

Proposition 11. All the four rules R|S|, Rc(S), R̂ c(S) , and R∥ ∥ are range-converging.

The next axiom requires that if some range of costs is found to be acceptable unanimously by all the voters, the project must be allocated the maximum amount in this range.

Definition 5 (Range-unanimous). A PB rule R is said to be range-unanimous if for any instance I, whenever ∑j∈P τj ≤ b, the set {P t j : j ∈ P, ctj = τj} is selected under R.

Note that the above holds by default if τj is not defined for some j. Range-unanimity and range-abidingness do not imply each other, though they seem closely related. For example, take the rule that picks for each project j, degree with minimum cost in τj (whenever this set costs lesser than b). This is range-abiding but not range-unanimous. In an instance where the maximum costs in τj together cost more than the budget, range-unanimity is satisfied by default by any rule. However, a rule that selects a degree for project j whose cost is greater than maximum cost in τj, does not satisfy range-abidingness. Thus, range-unanimity does not imply range-abidingness.

Proposition 12. The rules R|S| and R∥ ∥ are rangeunanimous, whereas Rc(S) and R̂ c(S) are not.

The following axiom essentially implies that if two valid sets differ only on the degree of one project, then the set with higher degree needs to be preferred.

Definition 6 (Degree-efficient). A PB rule R is said to be degree-efficient if for any instance I, any project j ∈ P, any set S selected under R, and the degree x ∈ S(j), it holds that k > x =⇒ c(S) - cS (j) + ckj > b.

Proposition 13. The R̂ c(S) is degree-efficient, whereas R|S|, Rc(S), and R∥ ∥ are not.

Proof. Let R be R|S|, Rc(S), or R∥ ∥. Consider the example with single project j such that for every i: (i) ctj j <b and hi(j)<ctj j (ii) there exists t<tj such that li(j)≤ctj≤hi(j). The set {P t j : ctj = τj} is selected under R since we know that τj ̸= ∅ and τj < b. Assume that the axiom is satisfied. Then, by the definiton of tj , ctj j > b contradicting (i). The proof for R̂ c(S) is deferred to appendix [Sreedurga, 2023].

The next two axioms insist that the valid set closer to the bounds reported by all the voters must be preferred over a valid set farther from them.

Definition 7 (Lower bound-sensitive). A PB rule R is said to be lower bound-sensitive if for any instance I, any project j ∈ P, and any two valid set S, S′ such that for every voter i we have cS (j)<cS′ (j)<li(j), S is not selected under R.

Proposition 14. The R∥ ∥ is lower bound-sensitive, whereas R|S|, Rc(S), and R̂ c(S) are not.

Proof. The proof for R∥ ∥ is deferred to appendix [Sreedurga, 2023]. Let R be R|S|, Rc(S), or R̂ c(S) . For lowerbound sensitivity, consider a counter example as follows: (i) there are two projects with D(P1) = {P 0 1 , P 1 1 , P 2 1 , P 3 1 } and D(P2) = {P 0 2 , P 1 2 } (ii) c11 = 1, c21 = 2, c31 = b - 3, and c12 = b - 2 (iii) for every voter i ∈ N, li(1) = hi(1) = c31 and li(2) = hi(2) = c12 . Clearly, S = {P 1 1 , P 1 2 } is a set that is selected under R. Set S′ = {P 2 1 , P 1 2 } and j = 1.

Definition 8 (Upper bound-sensitive). A PB rule R is said to be upper bound-sensitive if for any instance I, any project j ∈ P, and any two valid set S, S′ such that for every voter i we have cS (j)>cS′ (j)>hi(j), S is not selected under R.

Proposition 15. The rules R|S|,Rc(S), and R∥ ∥ are upper bound-sensitive, whereas R̂ c(S) is not.

Next, we extend discount montonicity [Talmon and Faliszewski, 2019] to ensure that a winning degree of project shouldn't be omitted if it becomes less expensive.

Definition 9 (Discount-proof). A PB rule R is said to be discount-proof if for any instance I, any project j ∈ P, and a set S that is selected under R, S continues to be selected if cS (j) is decreased by 1.

Proposition 16. The R|S| is discount-proof, whereas Rc(S), R̂ c(S) , and R∥ ∥ are not.

5 Summary

Many times, there are multiple ways of executing a public project and hence several, but limited number of, choices for the amount to be allocated to this project. Unfortunately, the existing preference elicitation methods and aggregation rules for participatory budgeting do not take this factor into account. Our work is an attempt to bridge this gap. We generalized two utility notions defined for PB with approval votes to our model. We also proposed two other utility notions unique to our model. We analyzed all the corresponding utilitarian PB rules computationally and axiomatically.

Our computational part strengthens all the existing positive results, and also introduces several new parameterized tractability results (FPT, parameterized FPTAS) taking into account the parameters recently introduced in the PB literature. It is worth highlighting that all our computational results in Section 3 can be generalized by replacing the utilities with cardinal utility for every degree of each project. However, we present all the results for ranged approval votes due to their practical relevance, simplicity, and deep association with axiomatic analysis.

Followed by this, we introduce several axioms for our model with ranged approval votes and investigate which of these are satisfied by our PB rules. Note that, though none of the proposed PB rules satisfies all the axioms, every rule satisfies some axioms. Axiomatic analysis reflects the properties of each rule, using which the PB organizer can pick a rule based on the context. Also, it is worth bearing in mind that the novel disutility notion and PB rule R∥ ∥ we proposed for our model satisfies as many axioms as any simple approval-based PB rule satisfies. One of the key takeaways of this paper is hence a conclusion that R∥ ∥ is a very good choice when each voter approves a range of costs.

Acknowledgements

Sreedurga gratefully acknowledges the support of prime minister research fellowship (PMRF) by Government of India, and also thanks Prof. Ulle Endriss, Simon Rey, and Dr. Jan Maly for their helpful feedback.