Shortlisting Rules and Incentives in an End-to-End Model for Participatory Budgeting

1 Introduction

Participatory budgeting (PB) is a loosely defined range of mechanisms designed to improve the involvement of ordinary citizens in public spending decisions [Cabannes, 2004]. It is usually organised as a two-stage process. In the first stage, participants are invited to propose projects, a selection of which are put on a shortlist. Then, in the second stage, everyone can vote on the shortlisted projects to decide which of them should receive funding [Shah, 2007]. These are problems of social choice with a clear algorithmic component [Brandt et al., 2016; Aziz and Shah, 2020]. Prior formal work-in particular in the AI and the Economics & Computation communities-has concentrated almost exclusively on the second stage [Aziz et al., 2018; Benade et al., 2017; Fluschnik et al., 2019; Fain et al., 2016; Goel et al., 2019; Jain et al., 2020; Rey et al., 2020; Talmon and Faliszewski, 2019]. In this paper, we instead propose an end-to-end model of PB that accounts for both stages. By studying this model, we aim at better understanding real-life processes.

Our contribution, beyond the formulation of the model itself, is twofold. First, we propose and analyse several shortlisting rules for the first stage. Second, we analyse the incentives of engaging in strategic manipulation when making proposals during the first stage-in view of how these affect the second stage. Let us briefly discuss both contributions.

∗Contact Author

During the first stage, the shortlisting stage, participants can propose projects (e.g., planting a tree). It is often seen as desirable to significantly reduce the number of proposals entering the second stage. For instance, if we look at the PB exercises in Lisbon, around 30% of the projects were shortlisted [Allegretti and Antunes, 2014]. In Toronto , this number was as low as 10% [Murray, 2019]. An important objective at this point is diversity. Inspired by the Thiele rules for committee elections [Janson, 2016], we study diversity w.r.t. proposers, by minimising the number of participants without shortlisted proposals. Secondly, inspired by clustering algorithms [Jain and Dubes, 1988], we also explore diversity w.r.t. the shortlist, by avoiding selecting too many similar projects.

During the second stage, the allocation stage, participants vote on the shortlisted projects to decide which of them to fund-subject to a given budget limit. Since the shortlisting stage determines the "input" for this stage, there is significant interaction between the two, which motivates the study of end-to-end models that can account for such effects. Our focus is on participants who strategise during the shortlisting stage to affect the set of shortlisted projects that people can vote for during the allocation stage. To this end, we introduce the notion of first-stage strategyproofness and analyse how it depends on both the information available to participants and the choice of aggregation rules used during the two stages.

Related work. Most prior research of a formal nature regarding PB has focused on the allocation stage only. Topics are ranging from concrete rules [Talmon and Faliszewski, 2019], to strategic behaviour [Goel et al., 2019], or proportionality [Aziz et al., 2018]. Much of this work takes inspiration from the literature on multiwinner voting [Faliszewski et al., 2017], exploiting the fact that electing a committee of k representatives is isomorphic to selecting projects when each project costs 1 dollar and the budget limit is k dollars.

We are not aware of any formal work regarding the shortlisting stage in PB. Note that in multiwinner voting the term 'shortlisting' is used in two different senses: either to emphasise that choosing a set of k candidates is but a first step in making a final decision [Faliszewski et al., 2017], or to refer to the problem of electing a set of variable size [Kilgour, 2016; Faliszewski et al., 2020; Lackner and Maly, 2021]. Only the latter is formally related to shortlisting for PB (but does not involve costs or a budget limit). Note that its connections to clustering techniques have already been developed [Lackner and Maly, 2021].

Paper outline. We develop our end-to-end model for PB in Section 2. Then, Section 3 is dedicated to shortlisting rules and Section 4 to first-stage strategyproofness.

2 The Model

In this section, we introduce the two stages of our model for PB and fix our assumptions regarding agent preferences.

2.1 Basic Notation and Terminology

Let P = {p1, . . . , pm} be the (finite) set of all conceivable projects. The cost of each project is given by c : P → N. The total cost of any set P ⊆ P is written c(P) = ∑p∈P c(p). The budget limit is denoted by B ∈ N. For every project p ∈ P, we assume w.l.o.g. that c(p) ≤ B. The set of agents participating in the PB exercise is denoted by N = {1, . . . , n}.

We shall make use of the following generic procedure to choose a "best" subset (fitting the budget) of a given set of projects in view of a given ranking of those projects.

Definition 1 (Greedy selection). For a set P ⊆ P of projects and a strict linear order ≫ on P, the greedy selection procedure returns the set of projects GREED(P,≫) defined as follows. Projects are examined following ≫. A project p ∈ P is selected iff the total cost of the selected projects does not exceed B. The next project, if any, is then considered.

We are going to require a means for breaking ties, both between alternative projects and between alternative sets of projects. For any P ⊆ P, let idx(P) = {i ∈ N | pi ∈ P} be the set of indices of the projects in P. The canonical tiebreaking rule T returns T(P) = pi with i = min(idx(P)) for any nonempty set P ⊆ P. We also use T to transform weak orders on projects into strict orders. Take any weak order ≥ on P. Then for every indifference class P ⊆ P of ≥, we break ties as follows: p = T(P) is the first project, then comes T(P \ {p}), and so forth. Overloading notation, we denote by T(≥) the strict order thus obtained. Finally, we extend T to nonempty sets P ⊆ 2P of sets of projects in a lexicographic manner: T(P) is the unique set P ∈ P such that T((P \P ′ )∪(P ′ \P)) ∈ P for all P ′ ∈ P\{P}. Thus, we require that, amongst all the projects on which P and P ′ differ, the one with the lowest index must belong to P.

2.2 The Shortlisting Stage

In the first stage, agents are asked to propose projects. A shortlisting instance is a tuple 〈P, c, B〉. Because of bounded rationality, an agent may not be able to conceive of all the projects she would approve of if only she were aware of them. We denote by Ci ⊆ P the set of projects that agent i can conceive of-her awareness set-and we call the vector C = (C1, . . . ,Cn) the awareness profile. Agent i knows the cost of the projects in Ci as well as the budget limit B.

We denote by Pi ⊆ Ci the set of projects agent i ∈ N chooses to actually propose, and we call the resulting vector P = (P1, . . . , Pn) a shortlisting profile. We use (P-i, P ′ i ) to denote the profile we obtain when, starting from profile P , agent i changes her proposal to P ′ i .

A shortlisting rule R maps any given shortlisting instance I = 〈P, c,B〉 and shortlisting profile P to a shortlist, i.e., a set R(I, P ) ⊆ ⋃ P = P1 ∪ · · · ∪ Pn of shortlisted projects.

2.3 The Allocation Stage

In the second stage, agents vote on the shortlisted projects to decide which ones should get funded. An allocation instance is a tuple 〈P, c,B〉, where P ⊆ P is the set of shortlisted projects. Contrary to the shortlisting stage, the agents now know about all the projects they can vote for. They vote by submitting approval ballots, denoted by Ai ⊆ P for each i ∈ N, giving rise to a profile A = (A1, . . . , An). The approval score of a project p in profile A is nAp = |{i ∈ N | p ∈ Ai}|. Moreover, we define the weak order ≥Aapp on P by stipulating that p ≥Aapp p′ holds iff nAp ≥ nAp′ .

For a given instance I, the goal is to choose a budget allocation A ⊆ P. It is feasible if c(A) ≤ B and A(I) is the set of feasible budget allocations. Moreover, A ∈ A(I) is exhaustive if there exists no p ∈ P \ A s.t. c(A ∪ {p}) ≤ B and AEX(I) is the set of exhaustive budget allocations in I.

An allocation rule F maps any given allocation instance I and profile A to a feasible budget allocation F (I , A) ∈ A(I ). Two well-known (polynomial-time) allocation rules try to maximise the approval score of their output, either greedily [Goel et al., 2019] or exactly [Talmon and Faliszewski, 2019].

Definition 2 (Greedy-approval rule). The greedy-approval rule F returns, for any given allocation instance I = 〈P, c, B〉 and profile A, the following budget allocation:

Definition 3 (Approval-maximising rule). The approvalmaximising rule F returns, for any given allocation instance I =〈P, c, B〉 and profile A, the following budget allocation:

We say that an allocation rule F is exhaustive if, for all instances I and all profiles A, we have F(I,A) ∈ AEX(I). We furthermore say that F is unanimous if, for every instance I = 〈P, c, B〉 and every profile of the form A = (A, . . . , A) with A ∈ A(I), we have F (I, A) ⊇ A. We will at one point in the paper need the following strengthening of unanimity.

Definition 4 (Strong unanimity). An allocation rule F is strongly unanimous if, for every allocation instance I = 〈P, c,B〉, every agent i ∈ N, every feasible set A ∈ A(I), and every profile A with |A| ≥ 3 and Ai′ = A for all agents i′ ∈ N \ {i}, we have F (I, A) ⊇ A.

Observe that both of the rules defined above are exhaustive and strongly unanimous (and thus also unanimous).

2.4 Agent Preferences

Suppose agent i ∈ N has preferences over all individual projects in P expressed as a strict linear order ▷i (even though she might not be aware of ▷i in full). For P ⊆ P, we denote by ▷i|P the restriction of ▷i to P. Moreover, amongst the projects in P, agent i has an ideal set topi(P)

of projects, assumed to be determined by the greedy selection procedure: topi(P) = GREED(P,▷i|P). This approach will permit us to model what constitutes a truthful vote by an agent for varying shortlists P. We call the vector top(P) = (top1(P), . . . , topn(P)) the ideal profile given P.

We make use of two already introduced preference models that an agent can use to derive preference relations from her ideal set [Goel et al., 2019; Talmon and Faliszewski, 2019]. For any ideal set P ⊆ P, we denote by ⪰P the induced weak preference relation and by ≻P its strict part. For any two budget allocations A and A′ , under the overlap preference model we have A ⪰P A′ if and only if |A∩ P| ≥ |A′ ∩ P|, while under the cost preference model we have A ⪰P A′ if and only if c(A ∩ P ) ≥ c(A′ ∩ P ).

Finally, for any preference relation ⪰ and any family of budget allocations P ⊆ 2P , we use best(⪰,P) to denote the set of budget allocations that are undominated in P w.r.t. ⪰.

3 Shortlisting Rules

We are not aware of any shortlisting rules introduced in the literature for PB. In the following, we propose several.

The first of these is what arguably is the simplest of all rules, the nomination rule, where every agent acts as a nominator, i.e., someone whose proposals are always all accepted.

Definition 5 (Nomination rule). The nomination rule R returns, for every shortlisting instance I = 〈P, c, B〉 and shortlisting profile P , the shortlist R(I, P ) = ⋃ P .

Although very natural, the nomination shortlisting rule is not effective in reducing the number of projects.

3.1 Equal-Representation Shortlisting Rules

Since the budget limit is not a hard constraint at the shortlisting stage, we might want to try to ensure that every participant has their say. Building on this idea, we introduce the k-equal-representation shortlisting rules-inspired by the Thiele rules for multiwinner voting [Janson, 2016]-where k indicates an upper bound on the total cost of the shortlist.

Definition 6 (k-equal-representation shortlisting rules). Let k ∈ N. The k-equal-representation shortlisting rule R returns, for any given shortlisting instance I = 〈P, c,B〉 and profile P = (P1, . . . , Pn), the following shortlist:

The weight 1/n in the rule ensures that the rule will always select, if possible, a project proposed by the agents with the smallest number of thus-far-selected projects.

While intuitively attractive, computing shortlists under this rule is a computationally demanding task.

Proposition 1. For any k ∈ N, computing the outcome of the k-equal-representation shortlisting rule is NP-hard.

Proof. Note that for any k′ ∈ N, if all projects have cost B/k′ , computing the outcome of the k-equal-representation shortlisting rule amounts to finding a committee of size k′ with a Thiele voting rule with weights (1, 1/n, 1/n2 , . . .) in a multiwinner election [Janson, 2016]. Interestingly, the reduction showing that the well-known rule of proportional approval voting (PAV) is NP-hard [Aziz et al., 2015] works for all Thiele rules with decreasing weights. Since this is the case here, the reduction applies as well and shows NP-hardness for the k-equal-representation rule.

3.2 Median-Based Shortlisting Rules

One criterion frequently used for excluding projects in practice is the similarity between them. Based on this intuition, we introduce a family of shortlisting rules that cluster the projects and only select representatives of each cluster.

We call distance any metric over P. For a distance δ, the geometric median of P ⊆ P is defined as med(P) = T(argminp⋆∈P ∑p′∈P δ(p⋆ , p′ )). A partition of P, denoted by V = {V1, . . . , Vp}, is a (k, ℓ)-Vorono¨ı partition w.r.t. δ if ∑Vj∈V c(med(Vj)) ≤ kB and for every distinct Vj , Vj ′ ∈ V and every p ∈ Vj , we have:

• δ(p,med(Vj)) ≤ δ(p,med(Vj ′)), i.e., every project is in the cluster of its closest geometric median; and
• δ(p,med(Vj)) ≤ ℓ, i.e., every project is within distance ℓ of the geometric median of its cluster.

Let Vδ,k,ℓ(P) be the set of all (k, ℓ)-Vorono¨ı partitions of P. Definition 7 (k-median shortlisting rules). Let k ∈ N. The k-median shortlisting rule R w.r.t. distance δ returns, for any shortlisting instance I and profile P , the following shortlist:

Note that we chose to minimise ℓ in our definition; one could similarly try to minimise k, or both ℓ and k, instead.

For most natural choices of δ, computing outcomes for the k-median shortlisting rule will be NP-hard. For instance, for the Euclidean distance, our formulation coincides with the kmedian problem, known to be NP-hard [Kariv and Hakimi, 1979]. Still, known results on approximation algorithms and fixed-parameter tractability can be exploited here.

3.3 End-to-End Example

Let us now clarify our whole setting with an example.

At the shortlisting stage, if agents are truthful they will all submit their ideal set w.r.t. their awareness set, leading to the profile ({p1, p4, p5}, {p2, p6}, {p2, p7}, {p3, p8}, {p3, p9}). The outcome would be P\{p10} for the nomination rule, and {p1, p2, p3, p4, p6, p7} for the 2-equal-representation rule.

Suppose the shortlist is P = P \ {p10}. All agents now become aware of all the shortlisted projects. The truthful profile for the allocation stage would then be A = ({p1, p4, p5}, {p1, p2, p6}, {p1, p2, p7}, {p1, p3, p8}, {p1, p3, p9}). Both the greedy-approval and the approval-maximising allocation rules would select the budget allocation A = {p1, p2, p3}. △

3.4 Axioms for Shortlisting Rules

We now present several basic axioms for shortlisting rules. The first one, non-wastefulness, stipulates that it should be possible to exhaust the budget in the allocation stage.

Definition 8 (Non-wastefulness). A shortlisting rule R is non-wasteful if, for every shortlisting instance I = 〈P, c,B〉 and profile P , either c(R(I, P )) ≥ B or R(I, P ) = ⋃ P .

The second axiom we put forward here encodes the idea that every agent should be represented by the outcome.

Definition 9 (Representation efficiency). For shortlisting instance I = 〈P, c,B〉 and a shortlisting profile P, a shortlist P ⊆ P is representatively dominated if there exists a set P ′ ⊆ P with c(P ′ ) ≤ c(P), and |P ′ ∩ Pi| ≥ |P ∩ Pi| for all i ∈ N, with a strict inequality for at least one agent.

A shortlisting rule R is representatively efficient if its outcome is never representatively dominated.

Let us now see how our shortlisting rules perform w.r.t. these axioms. The proof of the next result is immediate.

Fact 2. The nomination shortlisting rule is both non-wasteful and representatively efficient.

Proposition 3. For k ≥ 2, the k-equal-representation shortlisting rule R is non-wasteful. For k ≥ 1, the k-equalrepresentation shortlisting rule is representatively efficient.

Proof. First, assume that there exists a k ≥ 2 such that R is wasteful. Then there must exist I = 〈P, c,B〉 and P such that c(R(I, P )) < B and R(I, P ) ̸= ⋃ P . There exists then a project p ∈ ⋃ P \ R(I,P) such that the representation score of the set R(I, P ) ∪ {p} is higher than that of R(I, P ). Moreover, since c(p) ≤ B, we have c(R(I,P) ∪ {p}) ≤ 2B ≤ kB. Hence, R(I, P ) ∪ {p} would have been returned by R, yielding a contradiction.

The fact that, for every k ≥ 1, the k-equal-representation shortlisting rule is representatively efficient is immediate from the choice of the weight 1/n in Definition 6.

Proposition 4. For k ≥ 2, the k-median shortlisting rule is non-wasteful. But there exists no k ∈ N such that the kmedian shortlisting rule is representatively efficient.

Proof. The proof that, for k ≥ 2, the k-median shortlisting rule is non-wasteful is similar to the corresponding part of the proof of Proposition 3. Indeed, for no shortlisting instance I and profile P, can there be a p ∈ ⋃ P \ R(I,P) such that c(R(I, P ) ∪ {p}) ≤ kB, since selecting this p would lead to a smaller within-cluster distance.

Finally, a k-median shortlisting rule is not efficiently representative, since the agents are not taken into account.

4 First-Stage Strategyproofness

We now turn to the analysis of strategic interaction during the shortlisting stage. The central challenge here is that we need to account for agents who, during the first stage, reason about what will happen during the second stage.

Let us first discuss the information available to a manipulator. In the classical voting framework [Zwicker, 2016], it is assumed that the manipulator has access to all the other ballots before submitting her own. In our setting, when considering a manipulator choosing which proposal to submit during the first stage, the same assumption is reasonable w.r.t. the proposals about to be submitted by the other agents during the first stage-but not w.r.t. the ballots the other agents are going to submit during the second stage, after the shortlist will have been determined. Indeed, the set of actions for the second stage depends on the proposal of the manipulator in the first stage. We explore three possibilities. In the first two cases, a manipulator in the first stage is unsure what will happen during the second stage, but assumes that either the worst scenario will be realised (pessimistic manipulation) or the best one (optimistic manipulation). In the third case, she knows the other agents' true preferences and trusts they will vote accordingly (anticipative manipulation).

Let us fix some further notation. For a given allocation rule F , allocation instance I = 〈P, c, B〉, profile A, and agent i ∈ N, let A⋆i (I,A, F) be defined as the ballot T(best(≻topi (P) , {F(I, (A-i,A′i )) | A′i ⊆ P})), the best response of i to A. When clear from the context, we omit I, A, and/or F. Also recall that every agent i ∈ N can determine an ideal set topi(P) for any given set P, which induces a preference relation ⪰topi (P) on budget allocations.

Definition 10 (Successful manipulation). Let R be a shortlisting rule, F an allocation rule, I1 = 〈P, c,B〉 a shortlisting instance, P a shortlisting profile, and P ′ i ⊆ P an alternative proposal for agent i ∈ N. Consider the shortlists P = R(I1, P ) and P ′ = R(I1, (P -i, P ′ i )), determining the allocation instances I2 = 〈P, c, B〉 and I ′2 = 〈P ′ , c, B〉, and abbreviate F(I2, (A-i,A⋆i (I2,A))) as F ⋆ (I2,A) and F(I ′2 , (A′-i ,A⋆i (I ′2 ,A′ ))) as F ⋆ (I ′2 ,A′ ), for any two approval profiles A on P and A′ on P ′ . Then we say that:

• P ′ i is a successful pessimistic manipulation if, for all profiles A on P and A′ on P ′ , it is the case that F ⋆ (I ′2 ,A′ ) ⪰topi (P∪P ′ ) F ⋆ (I2,A), with a strict preference for at least one pair (A,A′ ).
• P ′ i is a successful optimistic manipulation if, for at least one profile A on P and one profile A′ on P ′ , it is the case that F ⋆ (I ′2 ,A′ ) ≻top i (P∪P ′ ) F ⋆ (I2,A).
• P ′ i is a successful anticipative manipulation if, for the two profiles A = top(P) and A′ = top(P ′ ), it is the case that F ⋆ (I ′2 ,A′ ) ≻top i (P∪P ′ ) F ⋆ (I2,A).

Thus, a pessimist is pessimistic w.r.t. the advantages she can gain from manipulating: assuming the best if she is truthful and the worst otherwise. For optimists it is the other way around. Finally, an anticipative manipulator knows everyone's preferences on both P and P ′ and uses them to predict their votes for the second stage. Note that this definition works under both the overlap and the cost preference model.

We are looking for rules that do not allow for successful manipulation, i.e., that are first-stage strategyproof (FSSP). We distinguish two cases: either the manipulator is restricted to her awareness set (R-FSSP) or she can also propose any of the projects proposed by others (unrestricted, U-FSSP).

Definition 11 (FSSP). For a given preference model, a pair 〈R, F〉 consisting of a shortlisting and an allocation rule is R-FSSP w.r.t. a given type of manipulation, if for every shortlisting instance 〈P, c,B〉, every awareness profile C = (C1, . . . ,Cn), every shortlisting profile P = (P1, . . . , Pn) where Pi′ ⊆ Ci′ for all i′ ∈ N, and every agent i ∈ N, there is no P ′ i ⊆ Ci such that submitting P ′ i instead of topi(Ci) is a successful manipulation for i.

In case P ′ i ⊆ Ci ∪ ⋃ P and we consider topi(Ci ∪ ⋃ P) instead of topi(Ci), we say that 〈R, F〉 is U-FSSP.

Thus, under U, agents are assumed to first gain access to everyone's proposals and then decide whether or not to vote truthfully. We are going to use FSSP-P to denote FSSP w.r.t. pessimistic manipulation attempts, FSSP-O for optimistic, and FSSP-A for anticipative manipulation. A simplified overview is given in Figure 1.

The following result summarises how the different notions introduced relate to each other, where X implying X′ means that any pair 〈R, F 〉 satisfying X also satisfies X′ .

Proposition 5. The following implications hold for both the overlap preference model and the cost preference model:

• R-FSSP-O implies R-FSSP-A and R-FSSP-P.
• U-FSSP-O implies U-FSSP-A and U-FSSP-P.
• R-FSSP implies U-FSSP for all types of manipulation.

Proof. To see that the last of these claims is true, observe that U-FSSP is a special case of R-FSSP, namely when the manipulator can conceive of all the proposed projects, i.e., when Ci = ⋃ P . 1 The other claims are immediate.

All results in this section hold for both preference models, so we will not explicitly specify any preference model.

1 This may be counter-intuitive at first, but as explained at the end of Section 4.1, U-FSSP does not imply R-FSSP.

4.1 Awareness-RestrictedManipulation

We start by proving an impossibility theorem stating that, when manipulators are restricted to their awareness sets, no pair of reasonable rules can be first-stage strategyproof.

Theorem 6. Every pair 〈R, F〉 of a non-wasteful shortlisting rule R and an exhaustive allocation rule F is neither RFSSP-P nor R-FSSP-A (and thus also not R-FSSP-O).

Proof. We provide a proof for R-FSSP-P, but the same proof also goes through for R-FSSP-A. The claim for R-FSSP-O then follows from Proposition 5.

Let I = 〈P, c,B〉 be the shortlisting instance with P = {p1, p2}, c(p1) = c(p2) = 1, and B = 1. Suppose there are two agents, with p2 ▷1 p1 and C1 = {p1} and p1 ▷2 p2 and C2 = {p2}, i.e., each agent is aware only of the project they like less. The truthful shortlisting profile is P = ({p1}, {p2}). Since R is non-wasteful, we have |R(I, P )| ≥ 1. We distinguish three cases for R(I, P ).

In case R(I, P ) = {p1}, whichever way the agents vote in the allocation stage, as F is exhaustive, the final budget allocation must be {p1}. If agent 1 manipulates by not proposing any project for the shortlist, {p2} will get shortlisted, since R is non-wasteful. In that case, {p2} will also be the final budget allocation, since F is exhaustive. It is clear that for either preference model, agent 1 prefers {p2} over {p1}. So agent 1 has an incentive to pessimistically manipulate.

The case of R(I, P) = {p2} is symmetric to the previous one, except that now agent 2 can manipulate.

Finally, consider the case R(I,P) = {p1, p2}. W.l.o.g., suppose the final budget allocation is {p1} in case both agents vote truthfully. Then, just as in the first case, agent 1 has an incentive to submit an empty set of proposals instead, as that guarantees a final budget allocation of {p2}.

Note that the scenario used in the proof shows that strategyproofness under U does not imply strategyproofness under R. Indeed, under U no agent would have an incentive to manipulate in this scenario, as they would have all the information they need to submit an optimal truthful proposal.

4.2 UnrestrictedManipulation

For the case of U, let us start with the nomination rule. We first prove that it is immune to pessimistic manipulation when used with a strongly unanimous allocation rule.

Proposition 7. For every allocation rule F that is exhaustive and strongly unanimous, the pair 〈R, F〉, where R is the nomination rule, is U-FSSP-P.

Proof. Let I = 〈P, c,B〉 be a shortlisting instance, and P the truthful shortlisting profile. Consider an agent i ∈ N. Let Pi = topi(Ci ∪ ⋃ P). From Definition 5, we know that if i submits P ′ i instead of Pi, the shortlist will become P ′ i ∪ (⋃i′∈N\{i} Pi′ ). Since now weakly fewer projects from topi(Ci∪⋃ P ) are shortlisted, none of the budget allocations newly reachable will be strictly better for i. Moreover, strong unanimity entails that for every exhaustive budget allocation A, there is a profile realising it, namely, the one where every agent except i submits A. This directly implies that i cannot be better off by pessimistically manipulating.

On the other hand, we can show that the nomination shortlisting rule paired with either one of the allocation rules defined in Section 2.3 is not U-FSSP-A (and thus not U-FSSP-O).

Example 2. Recall Example 1, where for both the greedyapproval and the approval-maximising rule the outcome was A = {p1, p2, p3}. Suppose now that agent 1 submits {p4, p5, p10} instead of {p1, p4, p5} in the shortlisting stage. The shortlist then becomes P = P \ {p1}. In the second stage, all agents now approve of their second, third, and fourth most preferred projects, leading to the budget allocation {p2, p4, p5}. It is clear that under both of our preference models, this is better than A for agent 1. △

Unfortunately, also the other shortlisting rules we defined turn out to not be first-stage strategyproof.

Proposition 8. For all k ∈ N, the pair 〈R, F〉, where R is the k-equal-representation shortlisting rule and F is a unanimous allocation rule, is neither U-FSSP-P nor U-FSSP-O.

Consider the 1-equal-representation shortlisting rule. Under the truthful profile P = {{p3, p4}, {p1, p2}, {p2}}, the shortlist would be P = {p2}. Note that P ∩ top1(⋃ P ) = ∅. Assume now that agent 1 submits {p1, p3} instead of {p3, p4}. Then the outcome of the first stage becomes P ′ = {p1, p3}. It is clear that every A′ ∈ A(〈P ′ , c,B〉) is weakly preferred by agent 1 to every A ∈ A(〈P, c,B〉) and some are strictly preferred (the ones in which p3 appears). Since the allocation rule is unanimous, all these budget allocations can be reached (when every agent submit the budget allocation) so agent 1's manipulation is pessimistically successful.

To generalise to k > 1, add 3(k - 1) agents in groups of 3. Each group can conceive and approve of two new projects. It is easy to check that all the new projects will always be shortlisted, so we are back to the scenario above.

Proposition 9. For all k ∈ N, the pair 〈R, F 〉, where R is the k-median shortlisting rule based on the Euclidean distance over R2 and F is a unanimous allocation rule, is neither UFSSP-P nor U-FSSP-O.

Proof. We first prove the claim for k = 1 and then explain how to generalise it to all k ∈ N. Consider the shortlisting instance I = 〈P, c,B〉 with P = {p1, . . . , p6}, all projects have cost 1, and B = 3. Suppose the distance δ is the usual distance in the plane, with the projects as in the figure below:

Consider two agents such that p1 ▷1 p2 ▷1 p3 ▷1 . . . and C1 = {p1, p2, p3, p5}, and p4 ▷2 p6 ▷2 p7 ▷2 . . . and C2 = {p4, p6, p7}. The truthful profile is (C1 \ {p5},C2) which will lead to the clusters {p1, p2, p3, p4}, {p5}, and {p6} for the 1-median shortlisting rule. The set of shortlisted projects then is P = {p4, p6, p7}. Note that P ∩ top1(P) = ∅.

Now assume that agent 1 submits {p1, p2, p5}. Then there will be the clusters {p1}, {p2, p4}, and {p5, p6, p7}. The shortlist would then be P ′ = {p1, p2, p5}. For the same reason as in the proof of Proposition 8, since F is unanimous, agent 1's manipulation is pessimistically successful.

To extend this to all k > 1, add k - 1 agents, all knowing and approving of three new projects of cost 1. All the new projects are placed uniformly on a circle with centre p4 and a radius large enough so that all new projects will be in their own cluster. Then all the new projects will be shortlisted and we are back to the original case for k = 1.

Note that the previous statement can be generalised to other distances; in particular, it holds for any surjective distance.

To conclude this section, note that the proofs of Propositions 8 and 9 do not extend to U-FSSP-A as that notion is about a specific profile for which we have no relevant information. However, the following facts hold for U-FSSP-A.

Fact 10. For no k ∈ N is the pair 〈R, F 〉 U-FSSP-A, when R is the k-equal-representation shortlisting rule and F is either the greedy-approval or the approval-maximising rule.

Fact 11. For no k ∈ N is the pair 〈R, F 〉 U-FSSP-A, when R is the k-median shortlisting rule and F is either the greedyapproval or the approval-maximising rule.

The counterexample used in the proof of Proposition 9 also works for Fact 11. That of Proposition 8 can be made to work for Fact 10 by slightly changing the agent preferences (making p1 and p3 the most preferred projects of many agents).

5 Conclusion

To account for the fact that real-life PB is a two-stage process, we have initiated the study of PB encompassing not only the allocation stage but also the shortlisting stage preceding it. This has prompted several proposals for concrete shortlisting rules, and allowed us to analyse the incentives of agents to manipulate the shortlisting stage, in view of how their actions affect the ultimate outcome during the allocation stage. Our results suggest that it is hard to devise sensible shortlisting rules that incentivise the citizens to truthfully propose the projects they would like to see achieved.

This paper is a first step towards the principled investigation of the full PB process. There are still many other features deserving attention. For instance, it would be interesting to consider other allocation rules, not only based on approval scores, e.g., proportional rules [Aziz et al., 2018]. More generally, other types of interaction between the two stages can be investigated, such as devising allocation rules that take into account not only the outcome of the shortlisting stage but also the shortlisting profile itself, to enforce some kind of fairness across the two stages. This leads to the idea of defining and studying single rules for the whole process instead of taking the composition of a shortlisting and an allocation rule.