Time-Constrained Participatory Budgeting Under Uncertain Project Costs

1 Introduction

As an introduction, we consider the following example, which will accompany us through our work.

Example 1. The country "Participation Island" wants to address climate change. The government decides to provide 200 million dollars for new mobility projects that reduce emissions. Climate change will not wait forever, so these projects should be finished within the next five years. Companies send proposals for projects that each cost at most 200 million and can be realized within the given five years: bike sharing (BS); an express train route (ET); electric vehicle charging stations (EV); and development of fuel-cell vehicles (FV). The citizens of Participation Island are asked to vote on these projects by approving each project they like. The government then chooses which projects should be realized according to the voters' preferences and the constraints on time and money.

This problem has been extensively studied in Knapsack and participatory budgeting literature. Yet, it is not realistic.

Example 1 (continued). While it is very predictable how much EV and BS will cost (because one knows the cost for each station/bike and the number of stations/bikes), there is some uncertainty about the other projects. It is known that the train route goes through undeveloped swamps, where it is unclear yet, how many foundations are needed. The company which proposed the project guarantees that the costs are between 80 and 150 million. Hydrogen technologies are still in the development and while the company is sure that they can develop the cars, they are unsure about the exact costs. They guarantee the costs to be between 100 and 160 million.

The exact costs of a project are usually only known after finishing it. A common way to accommodate this uncertainty is to submit the project application with an estimated cost. However, if the estimation is far too expensive, the company will probably not get the bid. On the other hand, if it is far too low, the company is unable to realize the project and will have to ask for additional money. 1 So a more realistic approach is to provide a cost range, which moves the uncertainty risk to Participation Island. The question is now: how should Participation Island select projects? Of course, the limit of 200 million should not be exceeded, or at least this should be improbable. To reduce this risk, they could implement the projects sequentially, and wait for the exact costs before deciding which project to start next. But this is a slow process, and the time limit of five years should also not be exceeded.

Our Contribution. We develop a framework for timeconstrained participatory budgeting under uncertain project costs based on the existing framework for approval-based participatory budgeting by Talmon and Faliszewski [2019]. We propose desirable properties for such budgeting methods and explore which properties can be combined and which are incompatible. In addition, we experimentally evaluate algorithms for uncertain project costs that sequentially start new projects using the information of the cost of already finished projects and thus optimize the utilization of the budget. Meanwhile, they do their best effort to satisfy as many desirable properties as possible. Furthermore, we analyze different forms of proportionality for uncertain project costs.

RelatedWork. First, our work is related to scheduling and project planning literature. Given a set of tasks (which may form a bigger project), this research area is about making a plan on how to complete all tasks while respecting their dependencies and resource requirements. In the ResourceConstrained Project Scheduling Problem the goal is to minimize the completion time of the last project while projects have dependencies and resource requirements (e.g. workers), so parallelization of projects is not always possible. A similar problem is the Time-Constrained Project Scheduling Problem where the goal is to minimize the amount of extra resources needed to finish all projects in time. Both problems have been studied with uncertain project durations (see [Ma et al., 2016] and [Moradi and Shadrokh, 2019]). However, the resource requirements are deterministic. Vaziri et al. [2007] analyze project planning where the time for tasks is uncertain and can be influenced by the resources allocated to that task.

1 Depending on the contract, the company will have to pay from own resources. However, it is common that cost estimations may be exceeded by 10 - 20% without further consultation with the client. And if the company has not enough own resources to pay for the extra cost, they may become bankrupt, and the client has to pay someone else for finishing the project.

Note that in comparison to the above problems, we do not aim at implementing all projects and we also want to take into account the voters' preferences. In fact, if there is enough budget available to implement all projects our problem is trivial. Instead, we want to implement a subset of projects that makes the stakeholders happy, while facing the budget and the time as resource constraints. This is related to project portfolio management where the question is which projects should be implemented, suspended, or canceled, to serve the overarching objective of an institution. For an introduction to project portfolio management see [Rad and Levin, 2006, Chapter 1]. Another difference is that projects in our model have no dependencies on other projects, and our resources money and time are bounded, unlike resources in scheduling.

Also related is the work of Pindyck [1993], who studies projects that require continuous investment, and the final cost is only known after completion. However, there is no time constraint, no preferences, and projects can be canceled.

Another closely related field is Knapsack, as we study maximizing the (additive) utility of a set of projects while facing a cost constraint. For a broad overview, we refer to the textbook by Kellerer et al. [2004], which includes a chapter on multidimensional Knapsack problems considering more than one resource (in our case cost and time). Setting aside the time dimension, Knapsack has been studied under uncertain weights similar to our model by Monaci and Pferschy [2013] and Monaci et al. [2013]. Following a concept by Bertsimas and Sim [2004], both aim to find robust solutions, that perform well even if the exact weights turn out to be unfavorable. The model by Goerigk et al. [2015] allows for querying the exact weight of a fixed number of items in order to find a good solution when weights are uncertain.

A collective variant of Knapsack, namely participatory budgeting, has gained some attention in computational social choice lately. For notation, we adopt the formal participatory budgeting framework for approval-based preferences, which was introduced by Talmon and Faliszewski [2019] and extended to irresolute budgeting rules by Baumeister et al. [2020]. We refer to the bookchapter by Aziz and Shah [2021] for a broad overview on participatory budgeting in the context of computational social choice. Gomez et al. [2016] present a broad model considering uncertainty for both, cost and utility, for every project. In contrast to ours, their model is purely stochastic (a set of projects is feasible if its expected cost is within the budget limit), and projects are implemented all at the same time. An important stream of research we follow is the concept of proportionality in collective decision making, where every voter should be represented equally by a given solution. Aziz et al. [2018] study a variety of axioms suitable for participatory budgeting, while Pierczy´nski et al. [2021] also provide a rule with desirable properties with respect to proportional representation. We generalize some of their results to work with uncertain costs.

2 Preliminaries

Throughout this paper, for i, j ∈ N we write [i, j] = {i, . . . , j} and [i] = [1, i]. Let A = {a1, . . . , am} be the set of projects and each subset B ⊆ A is a bundle. 2 In our model we assume uncertainty about the exact cost for every project. Therefore, each project is associated with a total of four cost functions ˜c = (cmin, cmax, c, cp), where cmin and cmax model lower and upper bounds on the project's costs, while c models the exact costs. Hence, all three functions map from A to N+ and for each project a ∈ A it holds that c(a) ∈ [cmin(a), cmax(a)]. For simplicity, we abuse notation by denoting c(B) = ∑a∈B c(a) as the cost of a bundle B (analogously for cmin and cmax). By cp(a, x) we denote the probability that project a ∈ A costs at most x ∈ N+. Note that cp is monotonic, cp(a, cmin(a) - 1) = 0, and cp(a, cmax(a)) = 1. Slightly abusing notation we write cp(B, x) to denote the probability that for a given bundle B the cost c(B) is bounded by x. Finally, each project a ∈ A takes time δ : A → N+ to finish, and we have an overall time limit τ ∈ N+ at which all projects have to be finished, and a budget limit ℓ (also referred to as budget) 2 , which is the available money to implement projects. We assume for no project a ∈ A holds δ(a) > τ or cmax(a) > ℓ.

The projects are evaluated by a set of voters V = {v1, . . . , vn}. Each voter v approves a subset of projects denoted by appv ⊆ A. By sv(B) = |B ∩ appv| we denote the satisfaction of voter v with bundle B, i.e. the number of items in B approved by v. 3 We define s(B) = ∑v∈V sv(B) as the total satisfaction of all voters. We assume s({a}) > 0 for all a ∈ A, i.e., each project is approved by at least one voter.

Let E = (A, V, ˜c, ℓ, δ, τ ) ∈ E be a budgeting scenario with uncertain cost, where E is the set of all such scenarios. An online budgeting method R works in discrete time steps, and successively builds a budgeting log L : A → N ∪ {⊥} representing at which time step a project has been started, where ⊥ denotes that the project will not be realized. The budgeting method has limited access to the cost function c. If L(a) = t∗ , then c(a) is available only after the project has been implemented, i.e. at time step t∗ + δ(a). Obviously, the decision made at step t∗ is fixed and may not be revised when more information is available. Formally, the output of a budgeting method R(E) is a budgeting log. Further, the set of realized projects for a budgeting log L is denoted by R(L) = {a ∈ A | L(a) ̸= ⊥}. On the other hand, an offline budgeting method may access the exact cost function c. Hence, an optimal solution can be precomputed and every project can be implemented simultaneously.

2 We differ in terminology from Talmon and Faliszewski [2019], who refer to a project selection as budget.

3 Also studied by Talmon and Faliszewski [2019]. Other satisfaction functions (e.g. cost based) do not fit varying costs that well.

The budget limit is ℓ = 200 and we have time τ = 5. If we knew the exact costs, we would immediately start the projects BS, EV, and FV since with cost of 199 they fit in our budget and have the maximum number of 22, 000 approvals. However, this bares a high risk if the cost is unknown. The projects could also cost up to 263 which is far beyond our budget. An online budgeting method could for instance do the following. Start ET in the first year and wait four years until it finishes. If we are lucky, it turns out that it costs at most 97 so that we can safely implement both BS and EV in the remaining year. If it costs more, we can implement at least BS or in some cases EV. Also, the following is possible. If it is very improbable that FV costs more than 139, we could also relatively safely begin FV and EV simultaneously in the first year. Note that a sequential implementation of FV and EV fails the time limit.

We assume each started project in a budgeting log will be implemented regardless of the final cost and completion time. It is often assumed that projects can be stopped if their cost becomes more than their value, i.e. one cannot gain money with the project (e.g. in [Pindyck, 1993]). We decided against canceling for two reasons. First, in our model the "value" of a project is not measured in the same currency as the cost; second, the projects we have in mind cannot simply be canceled (imagine an eternal construction site in the city center).

3 Properties of Online BudgetingMethods

A budgeting log, and thus also an online budgeting method, has rather weak requirements. For instance, it is allowed in a budgeting log to start arbitrarily many projects simultaneously, even if they will certainly exceed the budget limit; or to start projects so late that they cannot be completed in time. These issues are undesirable and should be avoided. In this section, we define some desirable properties a budgeting log (and the algorithm that generates it) should satisfy.

Definition 1. Let E ∈ E be a budgeting scenario and L be a budgeting log with respect to E. L satisfies the following axioms if respective conditions are met.

Punctuality (PU): Every realized project finishes within the given time limit. Formally, for all a ∈ A it holds that either L(a) = ⊥ or L(a) + δ(a) ≤ τ .

• α-Risk-assessment (α-RA): A (set of) project(s) may only be started if the probability for exceeding the budget limit is at most α. Formally, for every t ∈ [τ], let Ut = {a ∈ A | L(a) ≤ t < L(a) + δ(a)} be the running yet unfinished projects, and Ft = {a ∈ A | L(a) + δ(a) ≤ t} the finished projects. For given

α ∈ [0, 1), it holds that a set of projects S may only be started at time t if cp(Ut ∪ S, ℓ - c(Ft)) ≥ 1 - α.

κ-Limitation (κ-LI): The budget limit may not be exceeded by a factor greater than κ. Formally, c(R(L)) ≤ κℓ.

Exhaustiveness (EX): There should be no project, which could have been implemented even with maximum cost without breaking feasibility. Formally, for B = R(L)

and every a ∈ A \ B, it holds that c(B) + cmax(a) > ℓ.

Note that 0-risk-assessment and 1-limitation coincide. A budgeting method R satisfies some axiom χ if R(E) satisfies χ for every E ∈ E (assuming parallel universe tie-breaking).

We study punctuality as a property since it is very interesting to see what kind of restriction it is, and what algorithms are possible if we relax it. Risk-assessment and limitation can be interpreted as follows. The client (e.g. Participation Island) has (κ-1)ℓ extra money as a security - for instance as a loan option - which should be used only if absolutely necessary. With a good risk-assessment (i.e. small α) it is improbable that the security is ever touched. Exhaustiveness has two interpretations. First, voters naturally expect that approved projects are realized if there is money left to do so safely. Second, it is common that the budget of a department may be reduced in the next period if it is not completely spent.

Independent of the above properties we want to maximize the satisfaction of the voters with the outcome. One key metric for the analysis of online optimization algorithms is the worst-case ratio between a solution found by an online algorithm and an optimal (satisfaction maximizing) solution with complete knowledge. This factor is known as competitive ratio (CR) (see Fiat and Woeginger [1998]).

Definition 2. An online budgetingmethodR is σ-competitive (σ-CR) if there is a constant ∆ ∈ R, such that for every E ∈ E and Bℓ = {B ⊆ A | c(B) ≤ ℓ} it holds that s(R(R(E))) +∆ ≥ 1σ maxB∈Bℓ s(B).

So which combinations of properties are possible, and is there a perfect online budgeting method? Unfortunately, the answer is no, i.e. no method can satisfy all properties simultaneously for all combinations of parameters.

Theorem 3. For any fixed α < 1, no online budgeting method simultaneously satisfies α-risk-assessment, punctuality, and exhaustiveness.

Proof. Consider an odd budget limit ℓ ≥ 3, and A = {a1, a2, a3, . . .}. Each project ai ∈ A has minimum cost cmin(ai) = (ℓ-1)/2, maximum cost cmax(ai) = (ℓ+1)/2, and takes time δ(ai) = τ . Note that a set of two projects exceeds the budget limit if and only if both projects have maximum cost. Let each project have maximum cost with probability greater than √α. Due to α-risk-assessment a budgeting method can only start one project at the first time step, say a1. By punctuality it is impossible to start another project. Since c(a1) = ℓ/2 is possible, there are instances for which c(a1) + cmax(a2) ≤ ℓ, thus exhaustiveness is violated.

Similar holds for κ-limitation as long as κ < m = |A|.

Theorem4. For any fixed κ <m, there exists no online budgeting method simultaneously satisfying κ-limitation, punctuality, and exhaustiveness.

Proof. Consider E ∈ E with A = {a1, . . . , am}, m ≥ 3, and ℓ > m. Each project ai ∈ A takes time δ(ai) = τ to realize, has cost c(ai) = 1, and maximum cost cmax(ai) = ℓ-m. By exhaustiveness, all projects must be realized, since for each ai ∈ A holds c(A \ {ai}) + cmax(ai) = ℓ and by punctuality, all projects must be started simultaneously. However, this decision has to be made without knowing the exact cost. Let E′ ∈ E be equivalent to E, except for having maximum cost as exact cost for each project. An online budgeting method that implements all projects to satisfy exhaustiveness and punctuality might end up spending cmax(A) = m · (ℓ -m). Thus, to start all projects, it cannot be better than m·(ℓ-m) ℓ = (m- m2 ℓ )-limited. By choosing ℓ large, we can approach m to any fixed value κ < m.

Interestingly, for κ ≥ m, above properties are compatible and can be satisfied by a 1-competitive algorithm. Since cmax(a) ≤ ℓ holds for every a ∈ A, we can implement every project at the first time step, only violating risk-assessment.

Observation 5. There exists a 1-competitive online budgeting method satisfying m-limitation, punctuality, and exhaustiveness.

However, trading off some desirable properties, it is possible to achieve 0-risk-assessment (or equivalently 1-limitation) together with either punctuality or exhaustiveness.

Theorem 6. There is an m-competitive online budgeting method satisfying 0-risk-assessment (and thus 1-limitation) and either punctuality or exhaustiveness.

Proof. First, we start the most valuable project, say a1, which has by definition maximum cost of at most ℓ. This way we achieve m-competitiveness already, since s(A) ≤ m · s({a1}). If we want to achieve punctuality, we stop now. For exhaustiveness, we sequentially add those projects, that can be safely added without exceeding the budget.

A competitive ratio of m is bad. Yet, for fixed α this factor cannot be improved if the projects' cost intervals are large.

Theorem 7. For any online budgeting method that satisfies α-risk-assessment for a fixed α < 1, the competitive ratio is in Ω(m). If cmax(a) = cmin(a) + 1 holds for all a ∈ A, the competitive ratio is in Ω(2).

Proof. Consider E ∈ E with A = {a1, a2, a3, . . . , am} and a set of voters, such that each project ai ∈ A yields the same (additive) satisfaction s(ai) = λ ∈ N+. Let ℓ = m, cmin(ai) = 1 and cmax(ai) = m for every ai ∈ A. Further, for each ai we set the probability that ai costs exactly m to α (thus, cp(ai, ℓ - 1) = 1 - α). An online algorithm with α-risk-assessment cannot start more than one project at the same time because for every pair of projects ai ̸= aj it holds cp({ai, aj}, ℓ) ≤ cp(ai, ℓ - 1) · cp(aj , ℓ - 1) = (1 - α)2 < 1-α. Thus it starts at most one project, for example a1. Revealing c(a1) = m and c(ai) = 1 for i ∈ [2,m], an offline algorithm may select the optimal solution B = A\ {a1} with s(B) = λ · (m- 1), while the online algorithm yields a satisfaction of s({a1}) = λ. Overall we deduce a competitive ratio of (m - 1) ∈ Ω(m).

For bounded uncertainty by cmax(a) = cmin(a) + 1 for all a ∈ A, we can use a similar argument. Let ℓ ≥ 2 be an even number, A = {a1, a2, a3, . . . , am} with cmin(ai) = ℓ/2 and cmax(ai) = ℓ/2 + 1. Again, we assume equal utility of λ for every project. We set cp(ai, ℓ/2) = 1 - α, so the probability that two projects can be implemented within ℓ is (1 - α)2 < 1 - α. Let an online budgeting method implement a1 first (due to α-RA it cannot implement two projects). Revealing c(a1) = ℓ/2+1 and c(a2) = c(a3) = ℓ/2, the optimal solution is {a2, a3}, yielding a competitive ratio of 2λ λ .

Theorems 6 and 8 show that these bounds are tight.

Theorem 8. If the uncertainty on the cost is bounded by a small factor c∗ , that is, cmax(a) - cmin(a) < cmax(a′ ) m = c∗ for all a, a′ ∈ A, there is a 2-competitive method satisfying 0-risk-assessment and either punctuality or exhaustiveness.

Proof. We use the optimal offline method to retrieve an optimal bundle B, assuming the lower bound cost for each project, i.e. ∑b∈B cmin(b) ≤ ℓ.

Case 1: If ∑b∈B cmax(b) ≤ ℓ, we are done.

Case 2: Otherwise, since implementing B may exceed the budget limit, we remove the least valuable project a ∈ B and implement B′ = B \ {a} at the first time step. It holds that ℓ ≥ ∑b∈B cmin(b) ≥ ∑b∈B cmax(b) - |B|c∗ ≥ ∑b∈B cmax(b)-cmax(a) = ∑b∈B′ cmax(b), due to |B|c∗ ≤ |B| · cmax(a) m ≤ cmax(a). On the other hand, since a is the least valuable project in B, the satisfaction with B′ is at least s(B′ ) ≥ s(B) · |B′ | |B| = s(B) · |B|-1 |B| . The worst competitive ratio of two is achieved if |B| = 2, since |B| = 1 is already covered by case 1. We can now return B′ which satisfies punctuality or we add projects to B′ until we achieve exhaustiveness. Note that in both cases there is no risk for exceeding the budget limit.

Table 1 summarizes the lower bound competitive ratios any online algorithm can achieve while satisfying given axiomatic properties, while Table 2 summarizes incompatible axioms.

4 Best Effort Online Budgeting

The possibility and impossibility results show that there is no perfect online budgeting method, i.e., no method satisfies all properties and has a good competitiveness. So the only way is to design "best effort" algorithms that trade-off properties and have a good competitiveness in most cases.

We propose the online budgeting method Best effort exhaustiveness (BEE) that trades exhaustiveness against punctuality, risk-assessment, and limitation. That is, the method guarantees punctuality, α-risk-assessment, and κ-limitation for given τ, α, κ, but not exhaustiveness. However, it tries to be as exhaustive as possible. With small modifications, we get the Best effort punctuality (BEP) method which trades punctuality against exhaustiveness, risk-assessment, and limitation. Both algorithms generalize a common greedy algorithm for Knapsack (see [Kellerer et al., 2004]) to our setting.

We test both algorithms using real data from the Participatory Budgeting Library (see [Stolicki et al., 2020]), modified to fit our uncertainty scenario. BEE performs better in terms of both exhaustiveness and competitiveness the more we increase τ . If projects have durations in [1, 10], the performance is already remarkably good at time limits between 20 and 30. However, our experiments with the BEP method imply that guaranteed exhaustiveness results in massive unpunctuality. Also, κ-limitation plays a role for the exhaustiveness, however, the role of α-risk-assessment is negligible unless α is almost 0.

5 Proportionality

Apart from maximizing the overall utility, another way to satisfy voters is a proportional distribution of the realized projects among them. There is a variety of proportionality axioms in the literature. We focus on justified representation, considering BPJR-L by Aziz et al. [2018] and Extended Justified Representation by Pierczy´nski et al. [2021]. Assuming uncertainty over the exact projects' costs, we provide two relaxations for proportionality axioms: ex ante and ex post. For the relaxations, we assume the upper cost bound is given for all projects (ex ante) or not implemented projects (ex post).

Definition 9. Consider a budgeting scenario E = (A, V, ˜c, ℓ, δ, τ) ∈ E and a bundle B ⊆ A. We define the following axioms in different variants, distinguishable by respective cost functions. Let c′ : A → N+ be a cost function. Typically, for known exact cost, we consider c′ = c for both of the following axioms. We study two relaxations for our setting with uncertain cost. That is, for the ex ante variant, we study c′ = cmax and for the ex post variant, for a ∈ A we study c′ (a) = c(a) if a ∈ B and c′ (a) = cmax(a), otherwise.

A bundle B satisfies following axioms if the respective condition holds, while a budgeting method R satisfies an axiom if it holds for every R(R(E)) with E ∈ E.

BPJR-L: For all k ∈ [ℓ] there exists no set of voters V ′ ⊆ V with |V ′ | n ≥ kℓ such that c′ (⋂v∈V ′ appv ) ≥ k, but there is a set T ⊆ ⋂v∈V ′ appv with c′ ((⋃v∈V ′ appv ) ∩ B) < c′ (T ) ≤ ℓ·|V ′ | n .

Extended Justified Representation (EJR): For all V ′ ⊆ V and T ⊆ ⋂v∈V ′ appv it holds that, if c′ (T) ≤ ℓ·|V ′ | n , then there exists some v ∈ V ′ with |appv ∩ B| ≥ |T |.

Informally, a group of voters should not be worse off, if they could spend their proportional share of the budget on projects they collectively approve of. If every voter had exactly ℓ/n to spend, BPJR-L states that if a group of voters can afford a set of unanimously approved projects T, the funds spent on projects no one of the group approves should be lower than ℓ-c′ (T). EJR on the other hand states that not all voters of a group should get less projects implemented than they could afford with joint funds.

Other axioms can be defined analogously in an ex ante and ex post version. In many cases stronger variants imply weaker variants. In case of EJR, consider some bundle that satisfies EJR. If the cost function is altered in a way that items only become more expensive, we observe that EJR is still satisfied (even though the price increase may now exceed the budget). Surprisingly, similar implications do not hold for BPJR-L.

Observation 10. EJR implies ex post EJR and ex post EJR implies ex ante EJR.

Theorem 11. BPJR-L does not imply ex post (or ex ante) BPJR-L.

Proof. Consider E ∈ E with three projects A = {a1, a2, a3}, two voters V = {v1, v2}, and ℓ = 3. The first two projects are known to be unit cost in advance, i.e., c(ai) = cmax(ai) = 1 for i ∈ [2]. For a3 it holds that c(a3) = 2 and cmax(a3) = 3. For i ∈ [2], voter vi approves both ai and a3.

First, we will show that the bundle B = {a1, a2} satisfies BPJR-L. There are three nonempty subsets of voters V1 = {v1}, V2 = {v2} and V3 = {v1, v2}. Let Ti = ⋂v∈Vi appv and Ui = ⋃v∈Vi appv. For i ∈ [2] it holds that c(Ti) = c(Ui ∩ B) = 1. For V3 it holds that c(T3) = c(U3 ∩ B) = 2. Yet, ex post (and ex ante) BPJR-L is violated. For k = 3 it holds that |V3| = kn ℓ , cmax(T3) = 3 = k but c(U3 ∩ B) = cmax(U3 ∩ B) = 2 < k.

Theorem 12. There is no online budgeting method satisfying α-risk-assessment and ex post BPJR-L.

Proof. Consider two projects A = {a1, a2} with cmin(ai) = 1 and cmax(ai) = 2 for i ∈ [2]. Further, let cp(ai, 1) < 1-α and ℓ = 2. If some budgeting method R selects both projects simultaneously, α-risk-assessment is violated. If R selects one project a ∈ A first, revealing c(a) = 1 yields two options. B = {a} violates BPJR-L and implementing the remaining project violates α-risk-assessment.

To compute a feasible outcome satisfying an ex ante proportionality axiom, we can assume maximum cost for each project and compute a bundle that satisfies the strong variant of the axiom. For the actual cost the result may not be exhaustive, but we may implement it instantly. Aziz et al. [2018] showed that a feasible outcome satisfying BPJR-L is guaranteed to exist (although hard to compute). Regarding EJR, Peters and Skowron [2020] recently introduced an aggregation method for committee elections, called Rule X and Pierczy´nski et al. [2021] showed that a generalization of Rule X

for participatory budgeting satisfies EJR (although they consider cardinal utilities instead of approval based preferences).

Observation 13. There is an online budgeting method, satisfying 0-risk-assessment, punctuality and ex ante BPJR-L (respectively ex ante EJR).

We slightly adjust Rule X to also work with uncertain cost and show subsequently that our variant satisfies ex post EJR.

Definition 14. Rule X for uncertain cost (RX) works as follows. Every voter v ∈ V is given a (real valued) individual budget of bv = ℓ/n, which they can use to implement projects sequentially. We start with an empty bundle B = ∅ and fund exactly one project in each iteration. The cost will be deducted from supporting voters' funds. For ρmax > 0 a project a ∈ A\B is ρmax-affordable if the following equation holds.

RX implements the project a∗ with the lowest ρmaxaffordability, waits for it to finish to obtain the exact cost, and finally withdraws the required funds from approving voters. That is, we replace the upper cost bound cmax(a∗ ) in Equation (1) with c(a∗ ) and calculate the ρ-affordability for a∗ . Then for every voter v ∈ V with a∗ ∈ appv, bv is set to max(0, bv - ρ). If there is no ρmax-affordable project left, Rule X returns the corresponding budgeting log.

By definition, RX always satisfies 0-risk-assessment (and 1-limitation) but fails punctuality. Following Pierczy´nski et al. [2021], Rule X (and thus RX) fails exhaustiveness.

Theorem 15. RX satisfies ex post EJR (and ex ante EJR).

Proof. Let E = (A, V, ˜c, ℓ, δ, τ) ∈ E and assume that B = R(RX(E)) violates ex post EJR. Consider the cost function c′ with c′ (a) = c(a) if a ∈ B and c′ (a) = cmax(a) if a ∈ A\B. Then by assumption there is a set of voters V ′ ⊆ V and a set of projects T ⊆ ⋂v∈V ′ appv with c′ (T ) ≤ ℓ·|V ′ | n and for all v ∈ V ′ it holds that |appv∩B| < |T |. We investigate what led to the violation of EJR, by simulating RX with (ex post) knowledge of the exact cost for projects in B. We index the elements in T \B = {t1, . . . , tk} in a way that c′ (ti) ≤ c′ (tj) for all i < j. Let every voter v ∈ V ′ split her initial individual budget bv = ℓ/n into k + 1 piles bjv , such that for j ∈ [k] the pile bjv = c′ (tj) |V ′ | is v's equal share for funding tj (w.r.t. V ′ ).

The leftover funds b0v = ℓn - c′ (T) |V ′ | will be reserved to fund projects in B ∩ T. We execute RX again, but this time we try to keep track of which project is financed with which pile of funds. We will show, that after execution either some voter v ∈ V ′ has no funds left, but at least |T| preferred projects in the outcome, or every voter has some pile left, which could have been used to implement a project in T \ B.

By assumption, each voter v ∈ V ′ helps funding T ∩B and at most k - 1 additional projects. We let each voter v ∈ V ′ pay for projects in T ∩ B with the leftover funds b0v . In the following numbering we skip projects in T (each voter in V ′ has reserved funds for T ∩ B and T \ B wont be budgeted). For each v ∈ V ′ , let ajv be the j-th project, v helps funding (in addition to T ∩B). We let v pay her share for ajv with bjv . Note that cmax(ajv ) ≤ bjv . Otherwise, either tj has a lower

ρmax-affordability and would have been funded instead, or some voter v′ ∈ V ′ has not enough budget left to pay her (full) share. In the latter case, consider the first iteration that leads to some v′ ∈ V ′ being bankrupt. Then v′ has paid all the other projects with respective dedicated piles, resulting in at least k projects being funded (in addition to the projects T ∩ B). This is a contradiction to EJR being violated, since |appv′ ∩B| ≥ k + |T ∩B| = |T |. Following cmax(ajv ) ≤ bjv , our assumption can only hold if every voter v ∈ V ′ has at least one pile untouched. This is a contradiction, as RX could implement project t1 with a total of |V ′ | piles.

Punctuality cannot be added without violating ex post EJR. Theorem 16. There is no online budgeting method satisfying α-risk-assessment, punctuality and ex post EJR.

Proof. Consider the following example with A = {a1, a2} with cmin(ai) = 1 and cmax(ai) = 2 for i ∈ [2]. The budget limit is set to ℓ = 3 and a single voter approves both projects. We choose cp, such that cp(A, 3) < 1 - α. Finally, projects need to be implemented at the first time step, i.e., δ(ai) = τ for i ∈ [2]. Let B ⊆ A be the realized projects by an online budgeting method R. We study three cases assuming punctuality is satisfied. If |B| = 0, B clearly fails ex post EJR. If |B| = 1, B might fail ex post EJR in case c(B) = 1. R may not select B = A while respecting α-risk-assessment, as the probability of c(A) = 4 is greater than α.

6 Conclusions And Outlook

In a participatory budgeting campaign with uncertain costs one has to trade-off between the desirable properties punctuality, exhaustiveness, risk-assessment, limitation, but also voter satisfaction and proportionality. In a way, this confirms the old project management principle "fast, cheap, good, pick two." Being punctual and within the cost limit makes proportionality or a good competitive ratio usually impossible.

In some applications, projects compete for resources like machines or workers. Thus not all projects can run simultaneously (see Hans et al. [2007]). As a next step, we propose to extend our model in that direction. Additionally, more realistic satisfaction functions could model that a voter's satisfaction with a project may be affected by discovering the exact cost. Dependencies between parameters could be especially interesting for time and money, allowing for the possibility to speed up a project by spending more money. Finally, our model only considers uncertainty in one of two resources. Swapping respective functions to study uncertain finishing times instead, we are interested in which implications still hold (although uncertainty concepts for proportionality are more reasonable for the cost dimension). A more general model may explore uncertainty of both dimensions.

Acknowledgements

The authors would like to thank J´erˆome Lang and the anonymous reviewers for their helpful comments. This work was supported in part by the project "Online Participation," funded by the NRW Ministry for Innovation, Science, and Research and by the DFG grants RO-1202/21-1 and BA6270/1-1.