Discrete Budget Aggregation: Truthfulness and Proportionality

1 Introduction

The summer break is approaching, and you are looking forward to hosting a workshop at your university with participants from around the world. As the organizer, you need to determine how to allocate the workshop time among paper presentations, poster sessions, and social activities. Naturally, the participants have varying preferences regarding how the time should be divided. How should you combine these preferences into the actual allocation?

The problem of aggregating individual preferences on how a budget should be distributed among a set of alternatives is known as budget aggregation or portioning [Freeman et al., 2021; Elkind et al., 2023; Brandt et al., 2024; Caragiannis et al., 2024; de Berg et al., 2024; Freeman and Schmidt-Kraepelin, 2024]. In addition to time, the budget can also represent financial resources, such as when a city council is tasked with allocating its annual funds across different projects. Several budget aggregation mechanisms have been proposed and investigated in the literature. An example is the average mechanism, which simply returns the average of the preferences of all voters. Despite its simplicity, this mechanism is susceptible to manipulation: if a voter can guess the outcome of the mechanism, she can usually misreport her preference and bring the average closer to her true preference. In light of this, a number of authors have focused on designing truthful mechanisms, i.e., mechanisms for which it is always in the best interest of the voters to report their true preferences. Notably, Freeman et al. [2021] introduced the class of moving-phantom mechanisms and demonstrated that every mechanism in this class is truthful. In addition, a specific moving-phantom mechanism called the independent markets mechanism is (single-minded) proportional-this means that when every voter is single-minded (i.e., would like the entire budget to be spent on a single alternative), the output of the mechanism coincides with the average of all votes.

As far as we are aware, all prior work on budget aggregation allows a mechanism to output any distribution of the budget. 1 However, this can result in "fractional" distributions, which may be difficult or even impractical to implement in certain applications. For instance, a distribution that allots 6.37 hours from the 10 available hours at a workshop to paper presentations might be infeasible due to scheduling considerations or the inability to utilize such precise time increments. 2 Likewise, when allocating funds, it is often more convenient to work with round numbers. In this paper, we study discrete budget aggregation, where an integral budget must be distributed among a set of alternatives in such a way that every alternative receives an integral amount of the budget. Beyond the allocation of time and money, discrete budget aggregation is generally applicable when the "budget" comprises indivisible items, for example, in the distribution of faculty hiring slots among university departments.

1.1 Our Contributions

We study two variants of our model: In the integral setting, the voter ballots and the output allocation must be integral, while in the fractional-input setting, the voter ballots are allowed to be fractional. For both settings, we establish interesting connections to several social choice frameworks.

1 Lindner [2011] considered rules that take integral distributions as their input, but did not place any requirement on the output.

2 Note that such a distribution can be output, e.g., by the average mechanism, even if all participants submit preferences consisting only of integral numbers of hours.

Integral Mechanisms: Truthfulness. We explore two approaches for adapting truthful mechanisms from the fractional setting to our integral setting. Firstly, we round the output of fractional mechanisms using apportionment methods. We show that combining a well-known fractional mechanism with several standard apportionment methods fails truthfulness. Secondly, we translate the idea behind moving-phantom mechanisms directly into our setting. Specifically, we define the class of integral moving-phantom mechanisms, and prove that every mechanism in this class is truthful.

Integral Mechanisms: Proportionality. We show that there exist truthful mechanisms (from our class of integral moving-phantom mechanisms) that satisfy single-minded quota-proportionality. While this property is rather weak, we derive stronger proportionality notions for our setting by viewing it as a subdomain of approval-based committee elections. However, using a computer-aided approach, we show that even the weakest of these notions (called JR) is incompatible with truthfulness.

Fractional-Input Mechanisms. Allowing voters to cast fractional ballots has major implications on the space of truthful mechanisms. Building upon the literature on dictatorial domains, we show that any fractional-input mechanism that is truthful and onto must be dictatorial. This can be viewed as a variant of the Gibbard-Satterthwaite theorem.

All omitted material can be found in the full version of our paper [Schmidt-Kraepelin et al., 2025].

1.2 RelatedWork

The analysis of aggregating individual distributions into a collective distribution dates back to the work of Intriligator [1973]. However, Intriligator did not assume that agents possess utility functions and, as a result, did not address the aspect of truthfulness. Most of the work on truthful budget aggregation thus far assumes that agents are endowed with ℓ1 utilities. Under this assumption, Lindner et al. [2008] and Goel et al. [2019] showed that the mechanism that optimizes utilitarian social welfare (with a certain tie-breaking rule) is truthful. After Freeman et al. [2021] proposed the class of moving-phantom mechanisms, Caragiannis et al. [2024] and Freeman and Schmidt-Kraepelin [2024] investigated them with respect to the distances of their output from the average distribution, while de Berg et al. [2024] presented truthful mechanisms outside this class. Brandt et al. [2024] proved that truthfulness is incompatible with single-minded proportionality and an efficiency notion called Pareto optimality under ℓ1 utilities, but these properties are compatible under a different utility model. Elkind et al. [2023] conducted an axiomatic study of various budget aggregation mechanisms.

Given the integral nature of the output distribution, discrete budget aggregation bears a resemblance to the long-standing problem of apportionment [Balinski and Young, 1982]. The main difference is that, in apportionment, the input can be viewed as a single distribution (representing the fractions of voters who support different alternatives) rather than a collection of distributions. Brill et al. [2024] studied an approvalbased generalization of apportionment, where each voter is allowed to approve multiple alternatives instead of only one.

Delemazure et al. [2023] established the incompatibility between truthfulness and representation notions in that setting.

2 Model and Preliminaries

For any z ∈ N, let [z] denote {1, . . . , z} and [z]0 denote {0, 1, . . . , z}. In the setting of budget aggregation, we have a set [n] of n voters deciding how to distribute a budget of b ∈ N over a set [m] of m ≥ 2 alternatives. We write

for the set of vectors distributing a budget b over a number of alternatives m ∈ N, i.e., Sm b is an (m-1)-simplex. Similarly,

denotes the set of vectors integrally distributing the budget b over m alternatives. We sometimes refer to an element of Sm b or I m b as an allocation or a distribution. We denote by Sn,m,b = (Sm b )n the set of all fractional profiles with n voters, m alternatives, and a budget of b, and by In,m,b = (I m b )n the set of all integral profiles with the same parameters. For each voter i, let pi ∈ Sm b denote her vote, where pi = (pi,1, . . . , pi,m).

Budget-AggregationMechanisms. We will consider three types of budget-aggregation mechanisms (or mechanisms for short). Generally, a mechanism is a family of functions An,m,b, one for every triple n,m, b ∈ N with m ≥ 2. We distinguish three types of mechanisms by the type of input and output space of the corresponding functions.

• An integral mechanismmaps any integral profile to an integral aggregate, i.e., An,m,b : In,m,b → I m b .
• A fractional mechanism maps any fractional profile to a fractional aggregate, i.e., An,m,b : Sn,m,b →Sm b .
• A fractional-input mechanismmaps any fractional profile to an integral aggregate, i.e., An,m,b : Sn,m,b → I m b .

Since n, m, and b are often clear from context, we slightly abuse notation and write A instead of An,m,b. While our primary focus is on integral and fractional-input mechanisms, we will build upon fractional mechanisms from the literature.

We define the disutility of voter i with truthful vote pi ∈ Sn,m,b towards aggregate a ∈ Sn,m,b (or a ∈ In,m,b) as the ℓ1-distance between pi and a, denoted by ∥pi - a∥1.

Truthfulness. A mechanism A is truthful if for any n,m, b ∈ N with m ≥ 2 and any profile P = (p1, . . . , pn), voter i ∈ [n], and misreport p⋆i , the following holds for profile P ⋆ = (p1, . . . , pi-1, p⋆i , pi+1, . . . , pn):

For fractional(-input) mechanisms, both the true profile P and the misreport P ⋆ belong to Sn,m,b, while for integral mechanisms these profiles must be from In,m,b.

2.1 Moving-PhantomMechanisms

Freeman et al. [2021] introduced a class of truthful fractional mechanisms, which we summarize below.

Moving-Phantom Mechanisms [Freeman et al., 2021]. For fixed n, m, b, a phantom system Fn is a collection of n+1 continuous, non-decreasing functions fk : [0, 1] → [0, b], with fk(0) = 0 and fk(1) ≥ b · n-k n for k ∈ [n]0. We refer to these functions as phantom votes (or just phantoms) and to their input as time. Any collection of phantom systems F = {Fn}n∈N induces a fractional budget aggregation mechanism AF , called a moving-phantom mechanism. Namely, for a profile P = (p1, . . . , pn) ∈ Sn,m,b, an alternative j ∈ [m], and time t ∈ [0, 1], we denote by med(P, F, j, t) := med(p1,j, . . . , pn,j, f0(t), . . . , fn(t)) the median of all votes on alternative j and all phantom votes (from Fn) at time t. Let t⋆ be a time such that ∑j∈[m] med(P, F, j, t⋆ ) = b; then, the moving-phantom mechanism AF returns the allocation AF (P) = a with aj = med(P,F, j, t⋆ ) for all j ∈ [m]. Such t⋆ is guaranteed to exist 3 , and while it may not be unique, the resulting allocation AF (P) is.

We recap two prominent moving-phantom mechanisms from the literature that we will build upon later.

INDEPENDENTMARKETS [Freeman et al., 2021]. The INDEPENDENTMARKETS mechanism is induced by the phantom system with

for k ∈ [n]0 and n ∈ N. This corresponds to the phantoms moving towards b simultaneously, while being equally spaced (before they get capped at b).

UTILITARIAN [Lindner et al., 2008; Goel et al., 2019; Freeman et al., 2021]. The UTILITARIANmechanism is induced by the phantom system with

for k ∈ [n]0 and n ∈ N. This corresponds to all phantoms moving towards b one after another (except fn which stays at 0). UTILITARIAN maximizes utilitarian social welfare (i.e., minimizes the sum of the voters' disutilities).

3 Integral Mechanisms: Truthfulness

We embark on our search for integral mechanisms that are truthful. If one of the truthful fractional mechanisms from Section 2.1 were guaranteed to output an integral distribution for any integral profile, then this mechanism would directly yield a truthful integral mechanism. However, no movingphantommechanism satisfies this property-e.g., for the profile ((1, 0), (0, 1)), every anonymous and neutral mechanism, and thus every moving-phantom mechanism, must return (1/2, 1/2). In this section, we discuss two approaches for discretizing moving-phantom mechanisms, and exhibit their differing levels of success in achieving truthfulness.

3 We slightly deviate from the definition by Freeman et al. [2021] by requiring the sum of medians to reach b instead of 1. Since we also require phantoms to reach at least b · n-k n instead of n-k n , this is merely a matter of scaling. Freeman et al. [2021, Proposition 3] showed that requiring fk(1) ≥ n-k n for all k ∈ [n]0 implies that the sum of medians at t = 1 is at least 1, thus normalization occurs.

3.1 Rounding Fractional Mechanisms

Our first approach is to take a fractional mechanism and round its output into an integral output, i.e., we need to map any element of Sm b to an element of I m b . In fact, this is a wellstudied task in the apportionment literature [Balinski and Young, 1982]; an apportionment method is a family of functions (for any m, b ∈ N) such that Mm,b : Sm b → I m b . Given a fractional mechanism A and an apportionment method M, we call M◦ A the integral mechanism that is composed of A and M. Commonly studied apportionment methods include stationary divisor methods, Hamilton's method, and the quota method. Stationary divisor methods are parameterized by ∆ ∈ [0, 1], where ∆ = 1 corresponds to the Jefferson (or d'Hondt) method and ∆ = 1/2 corresponds to the Webster (or Sainte-Lagu¨e) method. However, applying any of these methods to the outcome of INDEPENDENTMARKETS does not yield a truthful mechanism.

Theorem 1. The composition of INDEPENDENTMARKETS and the following apportionment methods is not truthful:

• Hamilton's method
• Quota method
• Any stationary divisor method for which ∆ > 0 and 2∆ ̸∈ N
• Any stationary divisor method for which ∆ > 0 and 2∆ ∈ N, if we assume that tie-breaking is in favor of alternatives with higher amounts in the input allocation

The proof of Theorem 1, along with all other omitted proofs, can be found in the full version of our paper [SchmidtKraepelin et al., 2025]. Clearly, this theorem does not rule out the possibility that combining a different fractional mechanism with an apportionment method gives rise to a truthful integral mechanism; in fact, we will show that this is possible for the UTILITARIAN mechanism. However, the theorem implies that this combination approach does not preserve truthfulness in general. In the following section, we show that by embedding the rounding within the definition of the moving-phantom mechanism itself, we obtain a general recipe for constructing truthful mechanisms.

3.2 Integral Moving-PhantomMechanisms

The reason why moving-phantom mechanisms can produce non-integral outputs, even when all votes are integral, is that the sum of medians can normalize when phantom votes (which are continuous functions) occupy non-integral positions. We will adjust the phantom systems to the integral setting by modifying them in two ways. First, to guarantee integral medians, we let phantom votes increase in discrete steps rather than continuously. Second, to guarantee normalization, we define phantom votes for each alternative separately; this also reflects the inherent necessity for non-neutrality.

For n, m, b ∈ N, an integral phantom system

is a set of (n + 1) · m non-decreasing functions

with the following properties, where z := b · m · (n + 1):

1. ϕk,j(0) = 0 and ϕk,j(z) ≥ ⌈ n-k n · b⌉ holds for every alternative j ∈ [m] and every k ∈ [n]0, and
2. ∑nk=0 ∑mj=1 (ϕk,j(τ)-ϕk,j(τ-1)) ≤ 1 for all τ ∈ [z].

The idea is that we have n + 1 phantom votes on each alternative j ∈ [m], all starting at position 0 at time τ = 0. In each time step τ → τ + 1 at most one of the phantom votes increases its position by 1, until eventually all phantom votes reach the position ⌈ n-k n · b⌉ or higher. (We will discuss later why this lower bound is useful.)

A family of integral phantom systems Φ = {Φn,m,b | n,m, b ∈ N} defines the integral moving-phantom mechanism AΦ. For a given profile P = (p1, . . . , pn) ∈ In,m,b, and a time τ ∈ [z]0, we are interested in the median of the votes and the phantom votes on each alternative j, denoted as

The integral moving-phantom mechanism AΦ finds τ ⋆ ∈ [z]0 such that ∑j∈[m] med(P,Φ, j, τ ⋆ ) = b, and returns AΦ(P) = a with aj = med(P,Φ, j, τ ⋆ ) for each alternative j ∈ [m]. We remark that τ ⋆ necessarily exists, because by Condition 1 of an integral phantom system it holds that ∑j∈[m] med(P, Φ, j, 0) = 0 and ∑j∈[m] med(P, Φ, j, z) ≥ b, and by Condition 2 it holds that this sum increases by at most 1 in each time step. 4 While τ ⋆ is not necessarily unique, the outcome AΦ(P) is. We illustrate an example in Figure 1.

We show in the full version of our paper that any integral phantom system leads to a truthful mechanism. The proof closely follows the proof of truthfulness for fractional moving-phantom mechanisms by Freeman et al. [2021].

Theorem 2. Any integral moving-phantom mechanism is truthful.

4 The statement ∑j∈[m] med(P,Φ, j, z) ≥ b follows from the fact that moving-phantom mechanisms are guaranteed to reach normalization when every phantom k reaches n-k n · b (see Footnote 3).

Rounding Phantom Systems. We can construct integral moving-phantom mechanisms by rounding phantom systems. Let Fn = {f0(·), . . . , fn(·)} be a phantom system and �·� be a rounding function. 5 Then, we first track the point in (fractional) time t ∈ [0, 1] at which �fk(t)� changes for some k. We construct an integral phantom system by iterating over these points in time and moving the phantoms ϕk,1, . . . , ϕk,m up by 1, one after another. We have to be careful when �fk(t)� changes for the same t and more than one k; in this case, we first move the phantoms with lower k. Formally, this leads to the following procedure (see also Figure 2):

• Let 0 ≤ t1 < t2 < · · · < tℓ ≤ 1 be all points in time such that for some k ∈ [n]0 there is a change in �fk(·)�.
• Let ϕk,j(0) = 0 for j ∈ [m], k ∈ [n]0. Let τ = 0.
• For ti ∈ {t1, . . . , tℓ}, iterate over all k ∈ [n]0 such that �fk(·)� changes at ti and, starting with the lowest such k, do the following for j ∈ [m] one after another:
• ϕk,j(τ + 1) = ϕk,j(τ) + 1,
• ϕk′ ,j ′ (τ + 1) = ϕk,j(τ) for all (j ′ , k′ ) ̸= (j, k),
• increase τ by 1.

Two integral moving-phantom mechanisms that will be of particular interest are the combination of a variant of INDEPENDENTMARKETS and the floor rounding function (referred to as FLOORIM), and the combination of UTILITARIAN and the floor rounding function (referred to as FLOORUTIL). We show that FLOORUTIL is equivalent to the mechanism induced by combining UTILITARIAN with Hamilton's apportionment method via the process described in Section 3.1. In particular, this shows that the approach from Section 3.1 can lead to truthful mechanisms.

Proposition 1. The composition of UTILITARIAN and Hamilton's method (with tie-breaking by indices of alternatives) is equivalent to FLOORUTIL.

In the following section, we show that FLOORIM offers a desirable property beyond truthfulness.

4 Integral Mechanisms: Proportionality

Having established the existence of truthful mechanisms in the integral setting, we next examine how well these mechanisms perform with respect to other properties. We focus on proportionality, i.e., we want a mechanism to reflect the preferences of voter groups proportionally. There exists a proportionality notion in the fractional setting, which requires a mechanism to output the average distribution if all voters are single-minded. A voter i is said to be single-minded if pi,j = b for some alternative j (and therefore pi,j ′ = 0 for all alternatives j ′ ̸= j). We call a profile single-minded if all voters are single-minded, and define the average allocation µ(P) where µ(P)j = 1n ∑i∈N pi,j for each j ∈ [m].

5 A rounding function maps any x ∈ R to either ⌊x⌋ or ⌈x⌉ in such a way that if it maps x to ⌈x⌉, then it also maps every number between x and ⌈x⌉ to ⌈x⌉.

Single-Minded Proportionality 6 [Freeman et al., 2021]. A fractional budget-aggregation mechanism A is singleminded proportional if for any n,m, b ∈ N with m ≥ 2 and any single-minded profile P , it holds that A(P) = µ(P).

Clearly, outputting exactly the average is not always possible in the integral setting. We therefore adapt the axiom to make it satisfiable in our setting.

Single-Minded Quota-Proportionality. An integral budget-aggregation mechanism A is single-minded quotaproportional if for any n,m, b ∈ N with m ≥ 2 and any single-minded profile P, the output allocation a = A(P) satisfies aj ∈ {⌊µ(P)j⌋, ⌈µ(P)j⌉} for all j ∈ [m].

We establish the existence of truthful, single-minded quota-proportional mechanisms by adapting the fractional phantom system of single-minded proportional movingphantom mechanisms and then translating them into integral mechanisms as described in Section 3.2. For n, b ∈ N, we call a (fractional) phantom system Fn = {f0, . . . , fn} upperquota capped if for all k ∈ [n]0 we have fk(1) = ⌈b · n-k n ⌉.

Theorem 3. For any single-minded proportional and upperquota capped phantom system F, the integral movingphantom mechanism induced by F and the floor function satisfies single-minded quota-proportionality.

We can transform any phantom system Fn into an upperquota capped system F ′n : First extend Fn to guarantee fk(t) ≥ ⌈b · n-k n ⌉ (if necessary), then set f ′k (t) = min(fk(t), ⌈b · n-k n ⌉). Generally, AF and AF ′ need not be equivalent, but in the case of the INDEPENDENTMARKETS phantom system-call it G-they are. We define FLOORIM as the integral moving-phantom mechanism induced by G ′ and the floor function. Theorem 3 then implies that FLOORIM is single-minded quota-proportional. We remark that the theorem does not hold if we use G ′ (or G) and the ceiling function. For example, consider the instance with n = 6, m = 4, and b = 4, where three voters vote (4, 0, 0, 0) and one voter each votes (0, 4, 0, 0), (0, 0, 4, 0), and (0, 0, 0, 4). The upper n phantoms are immediately rounded to 1, leading to the output (1, 1, 1, 1), which violates single-minded quota-proportionality for the first alternative.

6 Freeman et al. [2021] called this axiom proportionality; we deviate from this to distinguish it from other proportionality notions.

Single-minded quota-proportionality is a rather weak proportionality notion, as it only applies to a highly restricted subclass of profiles. Consider, for example, the non-singleminded profile P = (p1, p2) for n = 2, m = 4, and b = 2 with p1 = (1, 1, 0, 0) and p2 = (0, 0, 1, 1). Clearly, a desirable outcome should allocate 1 to either alternative 1 or 2 and also 1 to either alternative 3 or 4, so that both voters are equally represented. However, integral moving-phantom mechanisms do not consider which of the votes on different alternatives come from the same voter, and may therefore (depending on the tie-breaking) return an allocation like (1, 1, 0, 0).

In order to define notions that capture a wider range of scenarios, we interpret our setting as a subdomain of the wellstudied domain of approval-based committee voting [Lackner and Skowron, 2023]. This allows us to import established axioms of proportional representation to our setting. We show that the failure to satisfy these axioms is not a weakness of integral moving-phantom mechanisms per se, but rather stems frommore general limitations of truthful mechanisms.

Connection to Approval-Based Committee Voting. In approval-based committee voting, we have a set of voters N, a set of candidates M, and a committee size k ∈ N. Each voter i approves a subset of the candidates Ai ⊆ M, and a voting rule chooses a committee W ⊆ M of size |W| = k. The satisfaction of a voter i with a committee W is |Ai ∩W|.

We can interpret any instance of our setting as an approvalbased committee election with an equivalent utility model (see also Goel et al. [2019]). Let P = (p1, . . . , pn) be a profile in the integral budget aggregation setting. We set M = {cj,ℓ | j ∈ [m], ℓ ∈ [b]} to be the set of candidates, k = b, and Ai = ⋃j∈[m] {cj,ℓ | ℓ ∈ [pi,j]}. Intuitively, for each alternative we create b (ordered) candidates corresponding to it, and a voter approves as many of these candidates (in order) as the amount of budget that she would like to allocate to that alternative. This translation is illustrated in Figure 3. Any chosen allocation a ∈ I m b can similarly be translated into a committee W = ⋃j∈[m] {cj,ℓ | ℓ ∈ [aj]}. To see that the (dis)satisfactions of the voters coincide in both models, observe that for a voter i and allocation a ∈ I m b , the following holds: ∥pi - a∥1 = 2b - 2 ∑j∈[m] min(pi,j , aj). This is equal to 2b - 2|Ai ∩W|, so a voter i prefers an allocation a over another allocation a′ if and only if voter i prefers the corresponding committee W over W ′ .

Using this connection to approval-based committee voting, we translate two representation axioms to our setting.

Justified Representation (JR) [Aziz et al., 2017]. For a profile P = (p1, . . . , pn), we say that a voter group N ′ ⊆ [n] is cohesive if |N ′ | ≥ nb and, for some alternative j, it holds that pi,j > 0 for all i ∈ N ′ . An allocation a ∈ I m b provides JR if for each cohesive group N ′ ⊆ [n], there is a voter i ∈ N ′ and an alternative j such that aj > 0 and pi,j > 0. A mechanism provides JR if it always returns an allocation providing JR.

Extended Justified Representation+ (EJR+) [Brill and Peters, 2023]. For a profile P = (p1, . . . , pn), an allocation a ∈ I m b provides EJR+ if there is no alternative j, integer ℓ ∈ [b], and voter group N ′ ⊆ [n] with |N ′ | ≥ ℓ · nb such that pi,j > aj and ∑j ′∈[m] min(pi,j ′ , aj ′ ) < ℓ for all voters i ∈ N ′ . A mechanism provides EJR+ if it always returns an allocation providing EJR+.

We establish an impossibility result for each of these axioms. For the first impossibility, we need the additional axiom anonymity, which disallows a mechanism from making decisions based on the identity of the voters. (However, a mechanism can still discriminate among the alternatives.)

Anonymity A mechanism A is anonymous if for any profile (p1, . . . , pn) and any permutation of voters σ : [n] → [n], it holds that A(p1, . . . , pn) = A(pσ(1), . . . , pσ(n)).

Theorem 4. No integral mechanism satisfies anonymity, truthfulness, and JR.

In order to prove Theorem 4, we use a computer-aided approach similar to the ones used, e.g., by Peters [2018], Brandl et al. [2021], and Delemazure et al. [2023]. For fixed n,m, b, we translate the search for an anonymous, truthful, and JR mechanism into a SAT formula, and use a SAT-solver to check for satisfiability. Each satisfying assignment corresponds to a mechanism An,m,b satisfying these axioms. For n = 3, m = 4, and b = 3, the SAT formula is unsatisfiable, which implies that no anonymous, truthful, and JR mechanism exists. We explain how to encode these axioms into a SAT problem and give a proof of Theorem 4 in the full version of our paper. We extracted a proof that is human-readable, but lengthy-it argues over 45 different profiles and applies truthfulness 203 times. Therefore, we additionally present a second result with a (much) shorter proof. For this result, we consider the stronger proportionality notion EJR+ and add range-respect to the list of axioms. In return, this impossibility does not require anonymity as one of the axioms.

Range-respect. A mechanism A is range-respecting if for any n,m, b and any profile P = (p1, . . . , pn) ∈ In,m,b, the following holds for the allocation a = A(P):

Theorem 5. No integral mechanism satisfies truthfulness, EJR+, and range-respect.

Proof sketch. Suppose for contradiction that there is a truthful, EJR+, and range-respecting mechanism A. Let n = 3, m = 4, and b = 3, and consider the profile P = ((1, 2, 0, 0), (1, 0, 2, 0), (1, 0, 0, 2)). Range-respect requires the first alternative to receive exactly 1, leaving alternative 2, 3, or 4 with zero budget. Assume without loss of generality that A(P)2 = 0. Consider the profile P ⋆ = ((0, 3, 0, 0), (1, 0, 2, 0), (1, 0, 0, 2)). One can argue that EJR+ implies that A(P ⋆ )2 ≥ 1 and A(P ⋆ )1 ≥ 1. However, this contradicts truthfulness, as voter 1 from profile P can misreport (0, 3, 0, 0) to decrease her disutility.

5 Fractional-Input Mechanisms

While both the integral and fractional budget aggregation settings allow for truthful mechanisms, we demonstrate in this section that truthful fractional-input mechanisms (i.e., those that map from Sn,m,b to I m b ) are significantly more restricted. In particular, we prove that the only truthful and onto fractional-input mechanisms are dictatorial. This stands in contrast to the integral setting, where one can verify that, e.g., FLOORIM is onto and non-dictatorial. Our result builds upon the literature on dictatorial domains in ranked-choice elections. Thus, before formalizing our result in Section 5.2, we briefly introduce ranked-choice elections along with a result on dictatorial domains by Aswal et al. [2003].

5.1 Dictatorial Domains

Let A be a set of alternatives and L(A) be the set of all strict rankings over A. We call D ⊆ L(A) a (sub)domain. In the following, we state the concept of linkedness for subdomains, as defined by Aswal et al. [2003].

Linked Domains. Let D ⊆ L(A) be a subdomain.

• We call two alternatives a, a′ ∈ A connected in D if there exist strict rankings ▷, ▷′ ∈ D such that a is ranked first by ▷ and second by ▷′ , and vice versa for a′ .
• We say that alternative a ∈ A is linked to a subset B ⊆ A if there exist distinct a′ , a′′ ∈ B such that a is connected to both a′ and a′′ in D.
• We call the subdomain D linked if we can order the alternatives in A into a vector (a1 , . . . , a|A| ) such that a1 is connected to a2 and, for all k ∈ {3, . . . , |A|}, it holds that ak is linked to {a1 , . . . , ak-1 }.

Informally, Aswal et al. [2003] have shown that the Gibbard-Satterthwaite theorem [Gibbard, 1973; Satterthwaite, 1975] holds for all linked domains. We state their theorem below and defer the formal definitions of a social choice function, unanimous, truthful, and dictatorial in the context of ranked-choice voting to the full version of our paper.

Theorem 6 ([Aswal et al., 2003, Theorem 3.1]). For any set of alternatives A with |A| ≥ 3, the following holds: If a subdomain D ⊆ L(A) is linked, then any unanimous and truthful social choice function on domain D is dictatorial for any number of voters n ∈ N.

For our proof, we need a stronger version of this theorem, which works even for weak rankings that have no ties in the two top ranks. We formalize this version and argue why it holds in the full version of our paper.

5.2 Truthful Fractional-Input Mechanisms

There exists a direct connection between our model and that of weak rankings. Namely, each vote p ∈ Sm b induces a weak ranking ⊵p over the integral allocations in I m b (i.e., rank points in I m b by their ℓ1-distance to p). At a high level, our goal is therefore to show that these weak rankings form a linked domain, which together with the stronger version of Theorem 6 yields a similar result in our setting.

Before doing so, we return to the context of fractionalinput mechanisms and formalize the desired result.

Onto. A fractional-input mechanism A is onto if for any n, m, b ∈ N with m ≥ 2 and any integral allocation a ∈ I m b , there exists a profile P ∈ Sn,m,b with A(P ) = a.

Dictatorial. Given n,m, b ∈ N with m ≥ 2, voter i ∈ [n] is a dictator for a fractional-input mechanism A for n,m, b if for all profiles P = (p1, . . . , pn) with parameters m and b, it holds that A(P) has rank 1 (i.e., is most preferred) in ⊵pi . The mechanism A is dictatorial for n,m, b if there exists a voter that is a dictator for A for n,m, b.

Theorem 7. Any onto and truthful fractional-input mechanism is dictatorial for any n, m, b with m ≥ 3.

Proof sketch. We start by defining a set of weak rankings induced by Sm b , namely,

where ⊵p is as defined at the beginning of Section 5.2, and r1(⊵p) (resp., r2(⊵p)) denotes the set of alternatives ranked first (resp., second) by ⊵p. We prove that this domain is linked, according to an adaptation of the definition of linkedness by Aswal et al. [2003] to weak rankings that have singleton top ranks. To this end, we carefully construct a ranking of the elements in I m b that witnesses the linkedness of ∇. Assume for contradiction that there exists a fractionalinput mechanismA that is onto, truthful, and non-dictatorial for some n ∈ N. We show that this implies the existence of a social choice function B on domain ∇ that is unanimous, truthful, and non-dictatorial for n voters, which contradicts the strengthened version of Theorem 6. While proving unanimity and truthfulness for B is rather immediate, establishing that B is non-dictatorial requires more effort, as A being non-dictatorial on Sn,m,b does not directly imply that B is non-dictatorial on ∇n .

The sharp contrast between the fractional-input and integral settings in relation to truthfulness may seem surprising. However, we remark that integral moving-phantom mechanisms can be used to construct fractional mechanisms that are approximately truthful, and the incentive to misreport diminishes as the budget increases. Specifically, we map each vote p ∈ Sm b to a point in I m b closest to it (with ℓ1-distance at most m2 ) and apply an integral moving-phantom mechanism. By the triangle inequality, the disutility decrease from misreporting is bounded by 2 · m2 = m. Thus, for constant m, (relative) misreporting incentives vanish as b grows.

6 Conclusion and FutureWork

In this paper, we have introduced the setting of discrete budget aggregation, which reflects the integrality requirement on the output often found in budget aggregation applications, and studied it with respect to truthfulness and proportionality axioms. Regarding truthfulness, we established a sharp contrast between the integral and the fractional-input settings: in the former, we presented a class of truthful mechanisms by building upon the literature on fractional budget aggregation, while in the latter, we exhibited the limitations of truthful mechanisms by leveraging existing results on dictatorial domains. Regarding proportional representation, we interpreted our integral setting as a subdomain of approval-based committee voting, and demonstrated that even basic representation guarantees from this literature are incompatible with truthfulness. In contrast, we proved that proportionality can be attained when voters are single-minded.

Our paper leaves several intriguing directions for future work. First, it would be useful to characterize the class of truthful integral mechanisms. For the fractional setting, de Berg et al. [2024] have recently shown that there exist truthful mechanisms beyond moving-phantom mechanisms. While characterizing all truthful mechanisms appears to be difficult in the fractional case given that some of these mechanisms are arguably unnatural, the question may be easier to answer in the integral case. Another interesting avenue is to further explore the connections of budget aggregation to approvalbased committee voting, independently of truthfulness. For example, which mechanisms do we obtain in the fractional setting if we apply well-established committee rules, such as the method of equal shares [Peters and Skowron, 2020], in the integral setting and let the budget approach infinity?

Acknowledgments

This work was partially supported by the Dutch Research Council (NWO) under project number VI.Veni.232.254, by the Singapore Ministry of Education under grant number MOE-T2EP20221-0001, and by an NUS Start-up Grant. We thank the anonymous reviewers for their valuable feedback.