## Distribution Aggregation via Continuous Thiele's Rules

Jonathan Wagner , * and Reshef Meir

Technion-Israel Institute of Technology

Abstract. We introduce the class of Continuous Thiele's Rules that generalize the familiar Thiele's rules [15] of multi-winner voting to distribution aggregation problems. Each rule in that class maximizes ∑ i f ( π i ) where π i is an agent i 's satisfaction and f could be any twice differentiable, increasing and concave real function. Based on a single quantity we call the 'Inequality Aversion' of f (elsewhere known as "Relative Risk Aversion"), we derive bounds on the Egalitarian loss, welfare loss and the approximation of Average Fair Share , leading to a quantifiable, continuous presentation of their inevitable trade-offs. In particular, we show that the Nash Product Rule satisfies Average Fair Share in our setting.

## 1 Introduction

In distribution aggregation problems [9] we study the problem of reaching a collective decision that concerns the division of some continuous public resource into different channels, e.g. the public budget allocated between various objectives (or 'projects') [13], time or land allocated between different activities, etc. The important defining feature is that we allocate any public resource, meaning that all alternatives serve, in principle, everyone, albeit to variable extents according to personal taste. That is in contrast to different branches of Social Choice, e.g. Cake cutting [20] or Fair Division [18] where we allocate resources among agents which enjoy them individually as private goods. The collective decision is reached via some voting rule or 'mechanism' that inputs everyone's preference regarding the different possible outcomes and outputs an outcome that would be implemented.

## 1.1 Preference Modeling

Accordingly, the preference of generic agents in distribution aggregation concerns the distribution as a whole rather than some personal endowment. In general, the full structure of such preference might be complex. Realistically, however, an aggregation rule that requires deep inquiry into each voter's personal preference seems too bothering and not very likely. Thus, as in other areas of Social Choice, "single-peaked" preferences where an agent's optimal outcome entails the complete description of her preferences over the decision space, are many times favored as a reasonable compromise between the accuracy and applicability [17, 6]. Moreover, such models typically perform better in terms of strategy-proofness. Specifically, /lscript p -norm preference where an agent (dis)satisfaction is expressed as the distance ∥ ∥ x i -x ∥ ∥ p between her preferred distribution x i to the one implemented x , and especially /lscript 1 is probably the most prevailing choice [9, 14, 13]. In our work we adopt the /lscript 1

∗ Corresponding Author. Email: sjwagner@campus.technion.ac.il

model, albeit adhering to its equivalent, less common representation that was introduced in [14] of overlap utilities. That is, an agent i enjoys | x i ∩ x | = ∑ j min( x , x i j j ) in allocation x , where j covers the set of alternatives. This formulation not only lets us more conveniently relate to satisfaction rather than dissatisfaction, but also mirrors the canonical notion in the discrete multi-winner voting setting of | A i ∩ W A | , i being the set of alternatives approved by agent i and W the winning set.

## 1.2 Axiomatic Demands And Their Incompatibilities

A well known fact that dates back as far as to Arrow's Theorem [1] is that good axiomatic properties of social choice rules are often contradictory. For instance, the utilitarian welfare maximizing allocation x ∈ arg max ∑ i | x i ∩ x | is known to also promise strategyproofness [14, 13], while the egalitarian maxmin allocation x = max y min i | x i ∩ y | can be advocated as the more fair solution and in particular guarantees a 1 n satisfaction the least for every agent. The Nash Product Rule x = max y ∑ i ln ( | x i ∩ x | ) is somewhat a middle ground between the two, that, as we later show, satisfies Average Justified Representation ( AFS ) that cares for the well being of subgroups rather than just individuals. Each of these three admits a certain demand that captures a different angle on social justice. Not surprisingly, they are generically incompatible with each other. In particular, [6] shows that even the weakest Justified Representation demand of 'proportionality' is incompatible with welfare maximization and strategyproofness.

## 1.2.1 Contribution

In this work, we offer non-axiomatic approach to deal with these impossibilities, via studying the class of Continuous Theile's Rules that maximize ∑ i f ( | x i ∩ x | ) where f could be any concave real function.

1 + 1 2 + 1 3 + · · · + 1 | A i ∩ W | that satisfies Extended Justified Representation [3]. When applied to our continuous setting, much resemblance is found between corresponding rules and the properties they guarantee. The advantage in moving to a continuous space is that we can consider a continuum of rules that lie 'in between' those that properly satisfy different axioms, and characterize the trade-off

The original Thiele's Voting Rules [15] are a well known class of multi-winner voting rules, each characterized by a function f , that choose the winning set W to maximize ∑ i f ( | A i ∩ W | ) . In affinity to the discussion above, this class includes some of the most practiced and well studied multi-winner voting rules, e.g. the welfare maximizing k -approval with f = id , the egalitarian ChamberlinCourant with f = 1 | A i ∩ W |≥ 1 , and PAV where f ( | A i ∩ W | ) =

each of them offers in terms of approximating either axiom. We will show how a rule's approximation guarantees depend on the Inequality Aversion of f , IAV f = -tf ′ ( t ) f ′′ ( t ) (elsewhere known as 'Relative Risk Aversion' [8]). In particular, we show that in our setup the Nash product rule satisfies AFS by its full meaning.

## 1.3 Related Work

Compared to its neighbouring branches of Social Choice, the literature on distribution aggregation is not abundant. The most natural application is Participatory Budgeting (PB) that has drawn increased attention in late years, however that literature mainly focuses on the discrete form where each project has a fixed cost [19, 2, 21], which is in compliance with the vast majority of PB instances in reality. In some works, the aggregation rule outputs a distribution while preferences are yet binary or ordinal [4, 5, 16]. As customary in Social Choice, the divisible PB literature treats the trade-off between fairness and welfare-optimality mainly by means of offering different mechanisms that can or cannot satisfy specific axiomatic properties [9, 4, 13]. [13] introduces the class of strategy-proof Moving-Phantom mechanisms within which the ( /lscript 1 ) welfare maximizing mechanism is the only pareto-efficient one, while the novel "Independent-Market" mechanism is the only one to satisfy a fairly weak notion of proportional fairness. This incompatibility of efficiency, strategy-proofness and proportionality has lately been proven to be generally inevitable [6] under /lscript 1 and /lscript ∞ preferences. Remarkably, however, [6] also shows that under Minimal Quotient preferences - where the satisfaction of agent i in x equals min { j x i &gt; : j 0 } x j x i

j

- these typically contradicting objectives can be achieved all at once. The most closely related predecessor of our work is found in [16], where group-fairness and welfare guarantees of different CTR rules (however named differently) are compared, under preference model slightly different than ours. Our work expands on it by considering egalitarian fairness two, and characterizing the trade-off by a single parameter. Other "flexible" approaches for handling the inherent trade-off include the relaxation of some of the axioms [4, 14], or searching for approximation guarantees different rules hold for different axioms [10, 11]. Under /lscript 1 preferences in particular, in [7] and [12] fairness is measured as the /lscript 1 distance of an allocation to the preferences mean. They introduce optimal rules for minimizing that gap within the Moving-Phantom class [13], with quantifiable bounds. However, to the best of our knowledge, the introduction of a continuum of parameterized rules to our choice, where each offers a concrete approximation guarantees, have not yet been attempted.

## 2 Preliminaries

Let [ n ] be a set of agents and [ m ] be a set of alternatives, where [ k ] := { 1 , ..., k } for each positive integer k . Subsets of [ n ] are denoted by lowercase letters e.g. s ⊂ [ n ] , and in many places we abuse the notation to represent also the subset size. For vectors in R m + := { y ∈ R m | y j ≥ 0 ∀ j ∈ [ m ] } , we denote | y | = ∑ j y j and y ≤ z means y j ≤ z j ∀ j . For any tuple y , . . . , y 1 t , we define the overlap ( y 1 ∩ · · · ∩ y t ) by ( y 1 ∩ · · · ∩ y t ) j := min 1 ≤ ≤ q t y q j . An allocation x ∈ ∆ m := { y ∈ R m + | ∑ m j =1 y j = 1 } is a distribution of some continuously divisible resource (e.g. time, money) among the m alternatives, where we normalize the overall budget to 1 . The preferences of every agent i are expressed by a single allocation x i ∈ ∆ m that she would like to be implemented ideally, and /vector x := ( x , . . . , x 1 n ) ∈ (∆ m n ) is the preferences profile . We denote by /vector x -i the partial profile consisting of all agents excluding i , and /vector x -s accordingly for a subset s ⊂ [ n ] . The satisfaction of agent i in allocation x is π i x := | x i ∩ x | = ∑ j min( x , x i j j ) . Or, just π i when specifying the allocation is unnecessary.

## 2.1 Aggregation Rules and their Properties

Definition 1. An aggregation rule is a function F : (∆ m n ) → ∆ m that inputs the preferences profile /vector x and outputs an allocation x ∈ ∆ m .

We survey here several properties that may or may not be satisfied by an allocation x given a profile /vector x . We say that an aggregation rule F satisfies any of these properties if for all /vector x ∈ (∆ m n ) , F /vector ( x ) satisfies the corresponding property with respect to /vector x .

- · Efficiency ( EFF ): An allocation x is efficient if no other allocation y ∈ ∆ m exists such that π i x ≥ π i y ∀ i ∈ [ n ] with at least one agent for which that inequality is strict.
- · Range Respecting ( RR ): An allocation x is Range Respecting if min i x i j ≤ x j ≤ max x i i j ∀ j ∈ [ m ] . Note that EFF = ⇒ RR .
- · Individual Fair Share ( IFS ): An allocation x satisfies Individual Fair Share if π i x ≥ 1 n ∀ i ∈ [ n ] . From an agents' individual perspective, that means that x allocates at least 1 /n of the budget according to her desire.
- · Average Fair Share ( AFS ): A subset of agents s ⊂ [ n ] is called α -cohesive for some 0 &lt; α ≤ | s | n if ∣⋂ ∣ i ∈ s x i ∣ ∣ ≥ α . An allocation x satisfies Average Fair Share if for every α ∈ (0 , 1] , if s ⊂ [ n ] is α -cohesive then 1 | s | i ∈ s π i x ≥ α .
- ∑ · Core Stability ( CS ): An allocation x satisfies Core Stability if for every s ⊂ [ n ] , no y ∈ R m + exists such that | y | = | s | n and π i y ≥ π i x ∀ i ∈ s with strict inequality for at least one member of s .
- · Proportionality ( PROP ) [13]: This much weaker demand requires the fulfilment of all Fair Share axioms above, but only for a simple structure of the preference profile (in which they all coincide). Single-minded profiles are profiles where x i is a unit vector for all i , in other words that every agent wishes to allocate the full budget to a single alternative. If /vector x is single-minded, then x satisfies proportionality if x = 1 n ∑ i x i . The next two properties refer directly to rules rather than allocations.
- · Participation ( PAR ): Aggregation rule F satisfies (strict) participation if

$$| F ( \vec { x } ) \cap x ^ { i } | \stackrel { ( > ) } { \geq } | F ( \vec { x } _ { - i } ) \cap x ^ { i } | \ \forall \vec { x }, x ^ { i }$$

meaning that agents should always prefer voting over abstaining.

- · Strategyproofness ( SP ): Aggregation rule F is strategyproof is for all x i and /vector x -i ,

$$| F ( x ^ { i }, \vec { x } _ { - i } ) \cap x ^ { i } | \geq | F ( y, \vec { x } _ { - i } ) \cap x ^ { i } | \ \forall y \in \Delta ^ { m }$$

meaning, no agnet i can increase her satisfaction by misreporting some y ∈ ∆ m instead of her true preference x i .

## 3 Continuous Theile's Rules

In this paper we study the following class of mechanisms.

Definition 2 (Continuous Thiele's Aggregation Rules) . For any increasing, twice differentiable and strictly concave function f : [0 , 1] → R , we define the corresponding Continuous Thiele's Rule (CTR) T f by

$$T _ { f } ( \vec { x } ) \in \arg \max _ { x \in \Delta ^ { m } } \sum _ { i = 1 } ^ { n } f ( \pi _ { x } ^ { i } )$$

## 3.1 Optimal allocations

CTRs can be computed efficiently via convex optimization as ∑ n i =1 f ( π i x ) is a concave function of x (note that π i x = ∑ j min( x , x i j j ) is in itself a sum of concave functions). . Thanks to that, optimal allocations can be characterized conveniently by first order conditions. We formalize here these constraints that will help us derive much of our later results.

Definition 3. Let x ∈ ∆ m . For each j ∈ [ m ] ,

$$s _ { j } ^ { \uparrow ( \downarrow ) } ( x ) \coloneqq \{ i \in [ n ] | x _ { j } ^ { i } > ( \geq ) x _ { j } \}$$

/negationslash

That is, s ↑ j ( x ) consists of all agents i ∈ [ n ] for which increasing (or reducing, for s ↓ ) x j while keeping all other { x k } k = j fixed will increase (reduce) their satisfaction π i x . The reason we distinguish between the two is that if x i j = x j for some agent i , she suffers from a reduction in x j while not gaining if we increase it. If no such agent exist, the sets coincide and we can just write s j . We also do that for the sake of abbreviation in many places, where the intention should be clear or the distinction is not crucial.

Notation 4. For every agent i and allocation x ,

$$\sigma _ { x } ^ { \uparrow ( \downarrow ) } ( i ) \coloneqq \{ j \in [ m ] | i \in s _ { j } ^ { \uparrow ( \downarrow ) } ( x ) \}$$

Next, we want to define the partial derivative of ∑ n i =1 f ( π i x ) w.r.t. alternative j ∈ [ m ] .

Definition 5 (marginal contributions) . Let x ∈ ∆ m . For every j ∈ [ m ] ,

$$m c _ { j } ^ { \uparrow ( \downarrow ) } ( x ) \coloneqq \sum _ { i \in s _ { j } ^ { \uparrow ( \downarrow ) } ( x ) } f ^ { \prime } ( \pi _ { x } ^ { i } )$$

Note that mc j ( x ) depends on x j only through s j , however the contribution of each member to the sum is a function of their overall satisfaction π i x := ∑ j min( x , x i j j ) . In case x i k = x k for some k ∈ [ m ] (whether k = j or other), f ′ ( π i x ) does not exist, and we take the right or left derivative accordingly.

Proposition 1 (MRS condition) . x ∈ arg max y ∈ ∆ m ∑ i f ( π i y ) if and only if

$$m c _ { j } ^ { \uparrow } ( x ) \leq m c _ { k } ^ { \downarrow } ( x ) \ \forall j, k \in [ m ]$$

Note that when s ↑ j = s ↓ j and s ↑ k = s ↓ k , marginal contributions also coincide and the two inequalities for j and k are reduced to the equation mc j = mc k . Intuitively, optimal allocations must admit the MRS demand because if mc ↑ j ( x ) &gt; mc ↓ k ( x ) for some j and k , increasing x j at the expense of x k would increase ∑ i f ( π i ) , up to the point where the MRS condition is satisfied. (And, every local maximum of a concave function is also a global one).

## 3.2 Axiomatic Properties of CTRs

We start with examining the satisfaction of the axiomatic demands mention above for CTRs. It is easy to observe that EFF and PAR are satisfied by all members in the class. As for other demands, their performance is not as satisfying.

Proposition 2. No CTR satisfies SP .

Proof. Consider the following counter example. Let n = m = 2 , x 1 = ( 5 . , . 5) and x 2 = (0 1) , . Let x = T f ( /vector x ) . Since T f satisfies RR , we know that x = ( y, 1 -y ) for some y ∈ [0 , 0 5] . , so that s 1 = 1 , s 2 = 2 , π 1 x = y +0 5 . and π 2 x = 1 -y . Thus,

$$f ^ { \prime } ( y + 0. 5 ) = m c _ { 1 } = m c _ { 2 } = f ^ { \prime } ( 1 - y ) \implies y =. 2 5$$

( f ′ is strictly decreasing, thus injective). Now assume agent 1 misreports ˆ x 1 = (1 0) , instead, and call the new outcome ( z, 1 -z ) . Then

$$f ^ { \prime } ( z ) = m c _ { 1 } = m c _ { 2 } = f ^ { \prime } ( 1 - z ) \implies z =. 5$$

and agent 1 's satisfaction has increased from 0 75 . to 1 .

Whenit comes to proportional fairness, the only CTR that achieves any such demand (for m &gt; 2 ) is the logarithmic rule where f = ln , aka the Nash Product Rule, that satisfies the relatively strong AFS . That stands in alignment with the discrete model where the PAV rule that maximizes ∑ i H | ( A i ∩ W | ) (where H is the harmonic function) is the only Thiele rule that admits a somewhat weaker demand called EJR [3]. The proof of Nash Rule's AFS property is dismissed here as a particular case of Theorem 9. On the contrary, we show that it is the only CTR that satisfies the much weaker PROP .

Proposition 3. For m &gt; 2 , the Nash rule T ln is the only CTR that satisfies PROP .

Proof. Let /vector x be a single-minded preferences vector, and T f ( /vector x ) = x . By MRS, s f j ′ ( x j ) = s k f ′ ( x k ) ∀ j, k (note that under single-minded profiles mc ↑ j = mc ↓ j for all j such that 0 &lt; x j &lt; 1 ). If x satisfies PROP then x j = s j n , yielding

$$s _ { j } f ^ { \prime } ( \frac { s _ { j } } { n } ) = s _ { k } f ^ { \prime } ( \frac { s _ { k } } { n } ) \, \Longrightarrow \, \frac { s _ { j } } { n } f ^ { \prime } ( \frac { s _ { j } } { n } ) = \frac { s _ { k } } { n } f ^ { \prime } ( \frac { s _ { k } } { n } )$$

Satisfying this for general n, 1 ≤ s , s j k ≤ n means that xf ′ ( x ) is a constant function, thus f = ln .

Moreover, the logarithmic CTR does not satisfy CS .

Example 4. Let m = 3 and [ n ] consisting of 3 disjoint sets n , n 1 2 , n 3 such that n 1 = n 2 = 0 3 . n, n 3 = 0 4 . n . Each of the subsets is homogeneous with preferences x 1 = (1 0 0) , , , x 2 = ( 5 . , . 5 0) , , x 3 = (0 0 1) , , respectively. Then T ln ( /vector x ) = x = ( 5 . , 0 , . 5) . However, with y = (0 55 0 05) . , . , | y | = n 1 + n 2 n , every agent i ∈ n 1 ∪ n 2 has π i y = 0 55 . &gt; π i x = 0 5 . .

Interestingly, the Nash product does output a core solution under preference model not too far from /lscript 1 [4]. Whether the core is always non-empty, and what rule can find core solutions when they exist, remains an open question.

## 4 Utilitarian vs. Egalitarian Welfare

After reviewing the not-very-impressive axiomatic performance of CTR rules, we develop in this section a more explicit presentation of the compromise one has to make between utilitarianism and distributive fairness. We start with the notion of Inequality Aversion captured in a concave function f .

Definition 6 ( Inequality Aversion) . For any twice differentiable f : [0 , 1] → R , the Inequality Aversion of f , IAV f : (0 , 1] → R is

$$I A V _ { f } ( t ) = - \frac { t f ^ { \prime } ( t ) } { f ^ { \prime \prime } ( t ) }$$

More commonly, -tf ′ ( t ) f ′′ ( t ) is known as the "Relative Risk Aversion" of f , a major concept in decision making under uncertainty [8]. While the two contexts are unrelated, the technical similarity is comprehensible. In principle, the concavity of f implies 1 n ∑ i f ( π i x ) ≤ f ( 1 n ∑ i π i x ) , and -tf ′ ( t ) f ′′ ( t ) is a proxy for how big the gap is. The higher -tf ′ ( t ) f ′′ ( t ) is, the less dispersed will be the optimal distribution for { π i x } i ∈ [ n ] . In decision making under uncertainty, f represents utility and 1 n ∑ i f ( π i x ) is the expectancy E f L [ ( ) ] for some random variable L distributed over { π i x } i ∈ [ n ] , whereas in our case f is a function chosen by a social planner to promote her normative balance between fairness (low disparity) and overall welfare ∑ i f ( π i x ) . Here are some examples for the IAV of different functions.

| f                                 | IAV f                 |
|-----------------------------------|-----------------------|
| - t - p , p> 0 - e t - p , p> 0 p | = 1 + p ∀ t ∈ (0 , 1] |
|                                   | ≥ 1 + p ∀ t ∈ (0 , 1] |
| t , 1 >p> 0                       | = 1 - p ∀ t ∈ (0 , 1] |
| ln( t )                           | = 1 ∀ t ∈ (0 , 1]     |
| t (2 - t )                        | ≤ 1 ∀ t ∈ (0 , 1]     |

The lemma below shows an equivalent representation for IAV that will later come handy. Then, Example 6 that follows will provides a clear intuition to its major role here. When writing IAV = ( ≤ )( ≥ ) λ , we mean that the corresponding relation holds in all [0 , 1] .

Lemma 5. The following are equivalent for any twice differentiable concave function f : [0 , 1] → R :

- · IAV f ( ≤ ) ≥ λ for some λ &gt; 0 .
- · ∀ α &gt; 1 , f ′ ( t ) f ′ ( αt ) ( ≤ ) ≥ α λ

Proof. Essentially, -tf ′′ ( t ) f ′ ( t ) ( ≤ ) ≥ λ means that f ′ ( ) t decreases faster (slower) than t -λ :

$$& \frac { \text{d} } { \text{d} t } \left [ t ^ { \lambda } f ^ { \prime } ( t ) \right ] = t ^ { \lambda - 1 } ( \lambda f ^ { \prime } ( t ) + t f ^ { \prime \prime } ( t ) ) \leq 0 \iff - \frac { t f ^ { \prime \prime } ( t ) } { f ^ { \prime } ( t ) } \geq \lambda \\ & \text{And if } t ^ { \lambda } f ^ { \prime } ( t ) \text{ is non-increasing (non-decreasing), then } \quad \text{$\quad.$}.$$

And if t λ f ′ ( ) t is non-increasing (non-decreasing), then

$$\forall \alpha > 1, \ t ^ { \lambda } f ^ { \prime } ( t ) \stackrel { ( \leq ) } { \geq } ( \alpha t ) ^ { \lambda } f ^ { \prime } ( \alpha t ) \iff \frac { f ^ { \prime } ( t ) } { f ^ { \prime } ( \alpha t ) } \stackrel { ( \leq ) } { \geq } \alpha ^ { \lambda }$$

Example 6. Consider a single-minded profile for m = 2 where s 2 &gt; s 1 . MRS at the outcome x = T f ( /vector x ) gives

$$\dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \delta$$

If λ bounds IAV f , it also bounds the extent to which T f favors the majority s 2 . If IAV f ≥ λ ,

$$( \frac { x _ { 2 } } { x _ { 1 } } ) ^ { \lambda } & \leq \frac { f ^ { \prime } ( x _ { 1 } ) } { f ^ { \prime } ( x _ { 2 } ) } \implies \frac { \pi _ { x } ^ { 2 } } { \pi _ { x } ^ { 1 } } = \frac { x _ { 2 } } { x _ { 1 } } \leq ( \frac { s _ { 2 } } { s _ { 1 } } ) ^ { 1 / \lambda } \\ p \text{articular, for } \lambda \to \infty \, w e \, \text{ get the egalitarian maxmin allocati.}$$

In particular, for λ → ∞ we get the egalitarian maxmin allocation x 1 = x 2 . For IAV f ≤ λ we will have the inequalities reversed :

$$( \frac { x _ { 2 } } { x _ { 1 } } ) ^ { \lambda } \geq \frac { f ^ { \prime } ( x _ { 1 } ) } { f ^ { \prime } ( x _ { 2 } ) } \implies \frac { \pi _ { x } ^ { 2 } } { \pi _ { x } ^ { 1 } } = \frac { x _ { 2 } } { x _ { 1 } } \geq ( \frac { s _ { 2 } } { s _ { 1 } } ) ^ { 1 / \lambda }$$

so that at the limit λ → 0 the welfare maximizing allocation x = (1 0) , is achieved. Finally, if IAV = 1 (meaning f = ln ) the budget is allocated proportionally, x j = s j s j + s k .

Our main results, presented in this section, build on the idea demonstrated in Example 6 to provide fairness / welfare guarantees within the CTR class.

We can figuratively map this class to (0 , ∞ ) based on the IAV parameter, as demonstrated in Figure 4. At the left limit λ = 0 we have the welfare maximizing rule F /vector ( x ) = arg max ∑ i π i . Theorem 7 bounds the welfare loss as a function of the upper bound on the IAV . On the other hand, for 1 ≥ IAV ≥ λ we get increasingly close approximations of AFS as coming closer to the Nash Product Rule where IAV = 1 (Theorem 9), and at the right limit IAV ≥ λ →∞ we have the egalitarian rule (Theorem 12). In other words 0 &lt; IAV &lt; 1 correspond to rules that favor utilitarian over egalitarian welfare (to various degrees), IAV &gt; 1 means favoring egalitarianism, and the Nash rule with IAV = 1 is point of "exact balance" between the two.

$$\begin{smallmatrix} \lambda = 0 & \xrightarrow { \lambda = 1 \left ( f = ln \right ) } \\ \text{utilitarian welfare} & \text{Justified Representation} & \text{egalitarian welfare} \end{smallmatrix}$$

## 4.1 Welfare Loss

Theorem 7 below shows the welfare preserved when the IAV is small enough, and is preceded by some necessary definitions.

Definition 7. The Welfare in allocation x is W x ( ) := ∑ i π i x . Definition 8. The Welfare loss of allocation x is defined

$$\text{WI} ( x ) = 1 - \frac { W ( x ) } { \max _ { y \Delta ^ { m } } W ( y ) }$$

Notation 9. Given two allocations x and y , we write:

$$J _ { x } & \coloneqq \{ j \in [ m ] | x _ { j } \geq y _ { j } \} \, ; \, J _ { y } \coloneqq \{ j \in [ m ] | x _ { j } < y _ { j } \} \\ \delta _ { j } & \coloneqq | x _ { j } - y _ { j } | \, \forall j \in [ m ] \, ; \, a n d \, \delta \coloneqq \sum _ { j \in J _ { x } } \delta _ { j } = \sum _ { j \in J _ { y } } \delta _ { j } \\ \text{The difference in satisfaction between $x$ to $u$ for every $\,$event$ is}$$

The difference in satisfaction between x to y for every agent is thus bounded by

$$\pi _ { y } ^ { i } - \pi _ { x } ^ { i } \leq \sum _ { k \in J _ { y } \cap \sigma _ { x } ^ { \uparrow } ( i ) } \delta _ { k } - \sum _ { j \in J _ { x } \cap \sigma _ { x } ^ { \downarrow } ( i ) } \delta _ { j }$$

Indeed, an agent might gain less then all of δ k for k ∈ J y ∩ σ ↑ x ( ) i if x k &lt; x i k &lt; y k , and may lose some of δ j even if j / J ∈ x ∩ σ ↓ x ( ) i in case y j &lt; x i j &lt; x j .

Theorem 7. Let x = T f ( /vector x ) such that IAV f ≤ λ . Then

$$\text{WI} ( x ) \leq \frac { \lambda m ^ { \lambda } } { \lambda m ^ { \lambda } + \lambda + 1 }$$

Proof. Let x = T f ( /vector x ) and y = arg max i π i . Then

$$\text{WL} ( x ) \leq \frac { \sum _ { i } } { \lambda m ^ { \lambda } + \lambda + 1 } \\ \text{roof} \text{ } Let x = T _ { f } ( \vec { x } ) \text{ and } y = \arg \max \sum _ { i } \pi ^ { i }. \text{Then} \\ W ( y ) - W ( x ) & \leq \sum _ { k \in J _ { y } } s _ { k } ^ { \uparrow } ( x ) \delta _ { k } - \sum _ { j \in J _ { x } } s _ { j } ^ { \downarrow } ( x ) \delta _ { j } \\ & \leq s _ { \max } ^ { \uparrow } \sum _ { k \in J _ { y } } \delta _ { k } - \sum _ { j \in J _ { x } } s _ { j } ^ { \downarrow } \delta _ { j } \\ & = \sum _ { j \in J _ { x } } ( s _ { \max } ^ { \uparrow } - s _ { j } ^ { \downarrow } ( x ) ) \delta _ { j } \\ & \leq \sum _ { j \in J _ { x } } ( s _ { \max } ^ { \uparrow } - s _ { j } ^ { \downarrow } ( x ) ) x _ { j }$$

where s ↑ max := max k ∈ J y s ↑ k and we used ∑ k ∈ J y δ k = ∑ j ∈ J x δ j and δ j ≤ x j . Now, by MRS and IAV f ≤ λ we have for all j, k ∈ [ m ] :

$$& s _ { k } ^ { \uparrow } f ^ { \prime } ( 1 ) \leq m c _ { k } ^ { \uparrow } \leq m c _ { j } ^ { \downarrow } \leq s _ { j } ^ { \downarrow } f ^ { \prime } ( x _ { j } ) \\ & \implies s _ { k } ^ { \uparrow } \leq s _ { j } ^ { \downarrow } \frac { f ^ { \prime } ( x _ { j } ) } { f ^ { \prime } ( 1 ) } \leq s _ { j } ^ { \downarrow } ( \frac { 1 } { x _ { j } } ) ^ { \lambda } \\ \text{fore $\sum_{iota=\dots,\ (s _ { \max } ^ { \uparrow } - s _ { i } ^ { \downarrow } ( x ) ) x_{i} < s _ { \max } ^ { \uparrow } \sum_{iota=\dots,\ (1}$}$$

and therefore ∑ j ∈ J x ( s ↑ max -s ↓ j ( x )) x j ≤ s ↑ max ∑ j ∈ J x (1 -x λ j ) x j . The function g t ( ) = (1 -t λ ) t is concave and has a maximum λ ( λ +1) λ +1 λ at t ∗ = ( λ +1) -1 λ . Thus,

$$\sum _ { j \in J _ { x } } ( 1 - x _ { j } ^ { \lambda } ) x _ { j } & \leq \frac { \sum _ { j \in J _ { x } } x _ { j } } { t ^ { * } } g ( t ^ { * } ) = \sum _ { j \in J _ { x } } x _ { j } \frac { \lambda } { \lambda + 1 } \leq \frac { \lambda } { \lambda + 1 } \\..$$

Now,

$$w, \\ W ( x ) & = \sum _ { i } \pi _ { x } ^ { i } \geq \sum _ { i } \sum _ { j \in \sigma ( i ) } x _ { j } = \sum _ { j } s _ { j } ^ { \downarrow } x _ { j } \\ & \geq s _ { \max } ^ { \uparrow } \sum _ { j } x _ { j } ^ { \lambda } \cdot x _ { j } \geq s _ { \max } ^ { \uparrow } m \left ( \frac { 1 } { m } \right ) ^ { 1 + \lambda } \\ & = s _ { \max } ^ { \uparrow } \left ( \frac { 1 } { m } \right ) ^ { \lambda } \\ \intertext { \ierefore, }$$

Therefore,

$$\frac { W ( y ) - W ( x ) } { W ( x ) } & \leq m ^ { \lambda } \frac { \lambda } { \lambda + 1 } \\ \Longrightarrow \frac { W ( y ) - W ( x ) } { W ( y ) } & \leq \frac { m ^ { \lambda } \frac { \lambda } { \lambda + 1 } } { 1 + m ^ { \lambda } \frac { \lambda } { \lambda + 1 } } = \frac { \lambda m ^ { \lambda } } { \lambda m ^ { \lambda } + \lambda + 1 }$$

Corollary 8 (Welfare loss in single minded profiles) . In the special case of single-minded preferences (where every voter allocates the full budget to some unique alternative j ∈ [ m ] ), the utilitarian allocation puts all budget on the alternative with highest support, meaning W y ( ) = s ↑ max , yielding

$$\text{WI} ( x ) = \leq \frac { s _ { \max } ^ { \uparrow } \sum _ { j \in J _ { x } } x _ { j } \frac { \lambda } { \lambda + 1 } } { s _ { \max } ^ { \uparrow } }$$

/negationslash

$$\text{WI} ( x ) \leq \frac { m - 1 } { m } \frac { \lambda } { \lambda + 1 }$$

Moreover, since s f j ′ ( x j ) = s k f ′ ( x k ) means x k ≥ x j ⇐⇒ s k ≥ s j , if s k = s ↑ max then x k = max j x j ≥ 1 m and thus ∑ j ∈ J x x j = ∑ j = k x j ≤ m -1 m . Hence,

## 4.2 Approximate AFS

The next Theorem shows how good an approximation of AFS we can guarantee when increasing the (lower bound on) IAF towards 1 .

Theorem 9 ( λ -AFS) . Let x = T f ( /vector x ) such that 1 ≥ IAV f ≥ λ . Then, For every α -cohesive set s ∈ [ n ]

$$\frac { 1 } { | s | } \sum _ { i \in s } \pi _ { x } ^ { i } \geq \alpha ^ { \frac { 1 } { \lambda } }$$

Proof. Let an α -cohesive group s ⊂ [ n ] . Since | ⋂ i ∈ s x i | ≥ α ≥ α 1 λ , if ⋂ i ∈ s x i if covered by x we are done. Otherwise, there exists j ∈ [ m ] such that min i ∈ s x i j &gt; x j and, since f ′ is convex,

$$\ m c _ { j } ^ { \uparrow } = \sum _ { i \in s _ { j } ^ { \uparrow } } f ^ { \prime } ( \pi _ { x } ^ { i } ) \geq \sum _ { i \in s } f ^ { \prime } ( \pi _ { x } ^ { i } ) \geq s f ^ { \prime } ( \pi ^ { s } )$$

where π s := ∑ i ∈ s π i x By MRS, sf ′ ( π s ) ≤ mc ↓ k ∀ k ∈ [ m ] . Thus, would now like to bound min k mc ↓ k . To do that, Let σ i ( ) = { k ∈ [ m i ] | ∈ s ↓ k } for every agent i and note that π i x ≥ ∑ k ∈ σ i ( ) x k . Now,

$$\mu _ { \mu } = \mu _ { \mu } \dots \dots \dots \dots \dots \dots \nu _ { \mu } \leq \kappa \in \sigma _ { ( i ) } \mu _ { \mu } \dots \dots, \\ \sum _ { k } m c _ { k } \cdot x _ { k } & = \sum _ { k } x _ { k } \sum _ { i \in s _ { k } } f ^ { \prime } ( \pi _ { x } ^ { i } ) = \sum _ { i } \sum _ { k \in \sigma ( i ) } x _ { k } f ^ { \prime } ( \pi ^ { i } ) \\ & \leq \sum _ { i } \sum _ { k \in \sigma ( i ) } x _ { k } f ^ { \prime } \left ( \sum _ { k \in \sigma ( i ) } x _ { k } \right ) \leq n f ^ { \prime } ( 1 ) \\ \dots$$

where the last inequality is due to the fact that tf ′ ( ) t is an increasing function by IAV f ≤ 1 . As ∑ k x k = 1 , there must exist k ∈ [ m ] such that mc k ≤ nf ′ (1) . Hence,

$$s f ^ { \prime } ( \pi ^ { s } ) \leq n f ^ { \prime } ( 1 ) \, \Longrightarrow \, \frac { s } { n } \leq \frac { f ^ { \prime } ( 1 ) } { f ^ { \prime } ( \pi ^ { s } ) } \leq ( \pi ^ { s } ) ^ { \lambda }$$

$$\text{Overall, we showed $\pi^{s} \geq \min \left ( \alpha, \left ( \frac { s } { n } \right ) ^ { \frac { 1 } { \lambda } } \right ) \geq \alpha ^ { \frac { 1 } { \lambda } }. \\ \text{A} \quad r _ { - - 1 } \rho _ { - 1 } \rho _ { - 1 } \rho _ { - 1 } \rho _ { - 1 } \rho _ { - 1 } \rho _ { - 1 } \rho _ { - 1 } \rho _ { - 1 } \rho _ { - 1 } \rho _ { - 1 } \rho _ { - 1 } \rho _ { - 1 } \rho _ { - 1 } \rho _ { - 1 } \rho _ { - 1 } \rho _ { - 1 } \rho _ { - 1 } \rho _ { - 1 } \rho _ { - 1 } \rho _ { - 1 } \rho _ { - 1 } \rho _ { - 1 } \rho _ { - 1 } \rho _ { - 1 } \rho _ { - 1 } \rho _ _ { - 1 } \rho _ { - 1 } \rho _ { - 1 } \rho _ { - 1 } \rho _ { - 1 } \rho _ { - 1 } \rho _ { - 1 } \rho _ { - 1 } \rho _ { - 1 } \rho _ { - 1 } \rho _ { - 1 } \rho _ { - 1 } \rho _ { - 1 } \rho _ { - 1 } \rho _ { - 1 } \rho _ { - 1 } \rho _ { - 1 } \rho _ { - 1 } \rho _ { - 1 } \rho _ { - 1 } \rho _ { - 1 } \rho _ { - 1 } \rho _ { - 1 } \rho _ { - 1 } \rho _ { - 1 } \rq \rq \rq \rq \rq \rq \rq \rq \rq \rq \rq \rq \rq \rq \rq \rq \rq \rq \rq \rq \rq \rq \rq \rq \rq \rq \rq \rq \rq \rq \rq \rq \rq \rq \rq \rq \rq \rq \rq \rq \rq \rq \rq \rq \rq \rq \rq \rq \rq \rq \rq \rq \rq \rq \rq \rq \rq \rq \rq \rq \rq \rq \rq \rq \rq \rq \rq \langle$$

## 4.3 Egalitarian Loss and Individual Shares

Wemove on now to discuss the egalitarian guarantees we can provide for high enough IAV . We aim on arguing that T f approaches the egalitarian rule at the limit IAV f → ∞ . First, we have the next result on individual share.

Proposition 10. Let x = T f ( /vector x ) such that IAV f ≥ λ and π min x := min i π i x . Then

$$\pi _ { x } ^ { \min } \geq \frac { 1 } { 1 + ( m - 1 ) ( n - 1 ) ^ { \frac { 1 } { x } } }$$

Proof. Since every agent must be in s ↑ j for at least one j ∈ [ m ] (unless her satisfaction is 1 ), there exist j ∈ [ m ] such that s ↑ j ≥ f ′ ( π min x ) . Thus, due to the MRS conditions,

$$\forall k \in [ m ], \ \ f ^ { \prime } ( \pi _ { x } ^ { \min } ) \leq m c _ { k } ^ { \downarrow } \leq ( n - 1 ) f ^ { \prime } ( \min _ { i \in s _ { k } } \pi _ { x } ^ { i } ) \\ \implies ( n - 1 ) ^ { \frac { 1 } { x } } \pi _ { x } ^ { \min } \geq \min _ { i \in s _ { k } } \pi _ { x } ^ { i } \geq x _ { k }$$

and in particular, π min x ≥ x j . Thus,

/negationslash

$$1 = x _ { j } + \sum _ { k \neq j } x _ { k } \leq \pi _ { x } ^ { \min } \left ( 1 + ( m - 1 ) ( n - 1 ) ^ { \frac { 1 } { x } } \right )$$

For λ → ∞ that bound is 1 /m which is max y ∈ ∆ m min i π i y in the worst case. The following definition formalizes "being close to egalitarian rule" by its full meaning.

Definition 10. The egalitarian loss of allocation x is defined

$$\mathrm E L ( x ) \coloneqq 1 - \frac { \min _ { i } \pi _ { x } ^ { i } } { \max _ { y \in \Delta ^ { m } } \min _ { i } \pi _ { y } ^ { i } }$$

.

Nevertheless, Proposition 10 alone does give an upper bound on the egalitarian loss for single-minded profiles.

Corollary 11 (egalitarian loss in single-minded profiles) . The egalitarian allocation for single minded profiles is uniform (assuming all projects j have non-empty support s j ), making π i = 1 /m ∀ i . Thus, by Proposition 10

$$\mathrm E L ( x ) = 1 - \frac { \pi _ { x } ^ { \min } } { 1 / m } \leq 1 - \frac { m } { 1 + ( m - 1 ) ( n - 1 ) ^ { \frac { 1 } { x } } }$$

Bounding EL ( x ) for general profiles, is, however, much more challenging. Our way of doing that can be roughly presented as follows. The egalitarian rule allocation is characterized by the fact the no improvement on all argmin agents is possible, in other words a shift in any direction will harm (or will not benefit) some of them. The proof of Theorem 12 below will show that for large enough IAV , a unanimous improvement is not feasible on all agents with satisfaction close to minimal , thereby limiting the increase in minimum satisfaction. Formalizing that requires the following notion.

Definition 11 (Directional Derivative) . For every agent i an two allocations x, y ∈ ∆ m , define the derivative of π i towards y at x as

Note that

$$\frac { \partial \pi _ { x } ^ { i } } { \partial ( y - x ) } \coloneqq \frac { \mathrm d } { \mathrm d \alpha } \pi ^ { i } ( \alpha y + ( 1 - \alpha ) x ) \Big | _ { \alpha = 0 } \\ \tt t e t \, \text{that}$$

$$\intertext { v o u a } \frac { \partial \pi _ { x } ^ { i } } { \partial ( y - x ) } & = \frac { d } { d \alpha } \left [ \sum _ { j } \min ( \alpha y _ { j } + ( 1 - \alpha ) x _ { j }, x _ { j } ^ { i } ) \right ] \\ & = \sum _ { k \in J _ { y } \cap \sigma _ { x } ^ { \dagger } ( i ) } \delta _ { k } - \sum _ { j \in J _ { x } \cap \sigma _ { x } ^ { \dagger } ( i ) } \delta _ { j } \\ & \geq \pi _ { y } ^ { i } - \pi _ { x } ^ { i } \\ \intertext { v o u a a } \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot$$

We are now ready to this part's main result.

Definition 12. For all m,n,λ, let

$$\gamma ( m, n, \lambda ) \coloneqq \max _ { \omega \in [ 0, 1 ] } \min \left ( m \omega \,, 1 - \left ( \frac { \omega } { n - 1 } \right ) ^ { \frac { 1 } { 4 } } \right )$$

Theorem 12. Let x = T f ( /vector x ) where IAV f ≥ λ . Then

$$\mathbf E L ( x ) \leq \gamma ( m, n, \lambda )$$

Note that γ m,n,λ ( ) ≤ 1 and that lim λ →∞ γ m,n, λ ( ) = 0 for all m,n . Table 1 shows some values of γ m,n,λ ( ) .

|   m |   λ = 0 . 1 |   λ = 1 |   λ = 10 |   λ = 100 |
|-----|-------------|---------|----------|-----------|
|   3 |           1 |   0.997 |    0.474 |     0.079 |
|   8 |           1 |   0.999 |    0.519 |     0.087 |
|  12 |           1 |   0.999 |    0.537 |     0.09  |
|  20 |           1 |   0.999 |    0.558 |     0.094 |

Table 1. Different values of γ m, n, λ ( ) for n = 100 .

Proof. and y the maxmin allocation. Since x is an optimum of ∑ i f ( π i ) ,

$$0 \geq \frac { \partial } { \partial ( y - x ) } \left [ \sum _ { i } f ( \pi ^ { i } ) \right ] = \sum _ { i } f ^ { \prime } ( \pi ^ { i } ) \frac { \partial \pi _ { x } ^ { i } } { \partial ( y - x ) }$$

Now let us add some notations. Let s 1 be all agents i for which π i y &gt; π i x , and s 2 := [ n ] \ s 1 . Denote ρ := min i ∈ s 2 π i x and µ := min i ∈ arg min i π i x ∂π i x ∂ y ( -x ) . Surely arg min i π i x ⊆ s 1 , therefore

$$\stackrel { \bullet } { \text{all} } \\ \text{s}, \quad 0 \geq \frac { \partial } { \partial ( y - x ) } \left [ \sum _ { i } f ( \pi ^ { i } ) \right ] \geq f ^ { \prime } ( \pi _ { x } ^ { \min } ) \cdot \mu - ( n - 1 ) f ^ { \prime } ( \rho ) \\ \implies \frac { n - 1 } { \mu } \geq \frac { f ^ { \prime } ( \pi _ { x } ^ { \min } ) } { f ^ { \prime } ( \rho ) } \geq \left ( \frac { \rho } { \pi _ { x } ^ { \min } } \right ) ^ { \lambda } \\ \text{Since } \alpha = \pi ^ { i } \text{ for some agent in } \varepsilon _ { \lambda } \ \pi ^ { \min } < \alpha \text{ And } \pi ^ { \min } - \pi ^ { \min } <$$

Since ρ = π i x for some agent in s 2 , π min y ≤ ρ . And, π min y -π min x ≤ µ because the directional derivative is greater then the actual gain in satisfaction for every agent. Thus,

$$( n - 1 ) \left ( \frac { \pi _ { x } ^ { \min } } { \pi _ { y } ^ { \min } } \right ) ^ { \lambda } \geq \pi _ { y } ^ { \min } - \pi _ { x } ^ { \min } \\. \quad.$$

Thus, if π min y -π min x = ω ∈ [0 , 1] , then EL ( x ) = ω π min y ≤ mω because π min y ≥ 1 m , and on the other hand, EL ( x ) = 1 -π min x π min y ≤

$$1 - \left ( \frac { \omega } { n - 1 } \right ) ^ { \frac { 1 } { \lambda } }. \, \text{Thus}, \\ /$$

$$\mathbf E L ( x ) \leq \min \left ( m \omega \,, 1 - \left ( \frac { \omega } { n - 1 } \right ) ^ { \frac { 1 } { \lambda } } \right ) \leq \gamma ( m, n, \lambda )$$

## 5 Discussion

This article presents a less common approach to the well known welfare-fairness trade-offs introduced in almost every Social Choice problem. Instead of separately testing the performance of different rules [9, 4], we offered a class of rules that almost none of them properly satisfy common axioms, but rather introduce a continuum of quantifiable trade-off points between the contradicting desires. From a practical point of view, such presentation of the range of possibilities might be more appealing and convenient to work with for social planners. Graph (a) in Figure 5 compares our results for welfare and egalitarian loss as functions of λ .

As this is a work in progress, we surely hope for possible improvements in some of our results. For example, we presented significantly lower bounds for welfare and egalitarian losses under single-minded profiles (Figure 5 graph (b)). Intuitively, however, in single-minded profiles the interests of different agents are as contradictory as they could be, leading to the conjecture that they might actually be the worst possible cases. We thus hope for some room for improvement in the results for general profiles as well. Moreover, some potentially interesting directions still await for further investigation. E.g., we did not look for approximate strategy-proofness in this article. Intuitively, what makes the strategy-proofness of the utilitarian rule is that mc j = s j for all j , making it impossible for an agent i ∈ s j to force an increase in x j towards x i j via manipulating her vote. On the other hand, the IAV of a function determines the impact that low satisfaction has compared to size in mc j = ∑ j f ′ ( π i ) . Thus, we might expect a bound on the agent's ability to increase mc j that depends on the IAV .

## References

- [1] K. J. Arrow. A difficulty in the concept of social welfare. Journal of political economy , 58(4):328-346, 1950.

## (a) Loss bounds on general profiles

(b) Loss bounds on single-minded profiles

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.01054v1-figure-60bab5ab-a48c-41b8-ac08-268c224a28f2.jpg)

Figure 1. Green lines show welfare loss upper bounds, scarlet lines show Egalitarian loss. Thick lines are for m = 15 and n = 100 , dashed lines for

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.01054v1-figure-1b99acc0-bd4c-4f0f-87c5-89dbe0095e89.jpg)

- m = 3 and ziz and N. Shah. Participatory budgeting: Models and approaches. n = 20 . [2] H. A Pathways Between Social Science and Computational Social Science: Theories, Methods, and Interpretations , pages 215-236, 2021.
- [3] H. Aziz, M. Brill, V . Conitzer, E. Elkind, R. Freeman, and T. Walsh. Justified representation in approval-based committee voting. Social Choice and Welfare , 48(2):461-485, 2017.
- [4] H. Aziz, A. Bogomolnaia, and H. Moulin. Fair mixing: the case of dichotomous preferences. In Proceedings of the 2019 ACM Conference on Economics and Computation , pages 753-781, 2019.
- [5] A. Bogomolnaia, H. Moulin, and R. Stong. Collective choice under dichotomous preferences. Journal of Economic Theory , 122(2):165184, 2005.
- [6] F. Brandt, M. Greger, E. Segal-Halevi, and W. Suksompong. Optimal budget aggregation with single-peaked preferences. arXiv preprint arXiv:2402.15904 , 2024.
- [7] I. Caragiannis, G. Christodoulou, and N. Protopapas. Truthful aggregation of budget proposals with proportionality guarantees. In Proceedings of the AAAI Conference on Artificial Intelligence , volume 36, pages 4917-4924, 2022.
- [8] J. S. Dyer and R. K. Sarin. Relative risk aversion. Management science , 28(8):875-886, 1982.
- [9] E. Elkind, W. Suksompong, and N. Teh. Settling the score: Portioning with cardinal preferences. arXiv preprint arXiv:2307.15586 , 2023.
- [10] B. Fain, A. Goel, and K. Munagala. The core of the participatory budgeting problem. In Web and Internet Economics: 12th International Conference, WINE 2016, Montreal, Canada, December 11-14, 2016, Proceedings 12 , pages 384-399. Springer, 2016.
- [11] R. Fairstein, R. Meir, D. Vilenchik, and K. Gal. Welfare vs. representation in participatory budgeting. arXiv preprint arXiv:2201.07546 , 2022.
- [12] R. Freeman and U. Schmidt-Kraepelin. Project-fair and truthful mechanisms for budget aggregation. In Proceedings of the AAAI Conference on Artificial Intelligence , volume 38, pages 9704-9712, 2024.
- [13] R. Freeman, D. M. Pennock, D. Peters, and J. Wortman Vaughan. Truthful aggregation of budget proposals. In Proceedings of the 2019 ACM Conference on Economics and Computation , pages 751-752, 2019.
- [14] A. Goel, A. K. Krishnaswamy, S. Sakshuwong, and T. Aitamurto. Knapsack voting for participatory budgeting. ACM Transactions on Economics and Computation (TEAC) , 7(2):1-27, 2019.
- [15] S. Janson. Phragmén's and thiele's election methods, 2018.
- [16] M. Michorzewski, D. Peters, and P. Skowron. Price of fairness in budget division and probabilistic social choice. In Proceedings of the AAAI conference on artificial intelligence , volume 34, pages 21842191, 2020.
- [17] H. Moulin. On strategy-proofness and single peakedness. Public Choice , 35(4):437-455, 1980.
- [18] H. Moulin. Fair division in the internet age. Annual Review of Economics , 11:407-441, 2019.
- [19] D. Peters, G. Pierczy´ski, and P. Skowron. n Proportional participatory

budgeting with additive utilities. Advances in Neural Information Processing Systems , 34:12726-12737, 2021.

- [20] A. D. Procaccia. Cake cutting algorithms. 2016.
- [21] N. Talmon and P. Faliszewski. A framework for approval-based budgeting methods. In Proceedings of the AAAI Conference on Artificial Intelligence , volume 33, pages 2181-2188, 2019.
Jonathan Wagner Reshef Meir
Distribution Aggregation via Continuous Thiele's Rules
We introduce the class of \textit{Continuous Thiele's Rules} that generalize
the familiar \textbf{Thiele's rules} \cite{janson2018phragmens} of multi-winner
voting to distribution aggregation problems. Each rule in that class maximizes
$\sum_if(\pi^i)$ where $\pi^i$ is an agent $i$'s satisfaction and $f$ could be
any twice differentiable, increasing and concave real function. Based on a
single quantity we call the \textit{'Inequality Aversion'} of $f$ (elsewhere
known as "Relative Risk Aversion"), we derive bounds on the Egalitarian loss,
welfare loss and the approximation of \textit{Average Fair Share}, leading to a
quantifiable, continuous presentation of their inevitable trade-offs. In
particular, we show that the Nash Product Rule satisfies\textit{ Average Fair
Share} in our setting.