--- title: "Portioning Using Ordinal Preferences: Fairness and Efficiency" authors: - "Stéphane Airiau" - "Haris Aziz" - "Ioannis Caragiannis" - "Justin Kruger" - "Jérôme Lang" - "Dominik Peters" doi: "10.24963/ijcai.2019/2" url: "https://ijcai.org/proceedings/2019/2" pdf: "https://ijcai.org/proceedings/2019/0002.pdf" venue: "Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence" year: 2019 pages: "11-17" track: "Main track" keywords: - "Agent-based and Multi-agent Systems: Cooperative Games" - "Agent-based and Multi-agent Systems: Computational Social Choice" --- # Portioning Using Ordinal Preferences: Fairness and Efficiency Stéphane Airiau, Haris Aziz, Ioannis Caragiannis, Justin Kruger, Jérôme Lang, Dominik Peters *Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence*, pages 11-17. DOI: [10.24963/ijcai.2019/2](https://doi.org/10.24963/ijcai.2019/2) ## Abstract A public divisible resource is to be divided among projects. We study rules that decide on a distribution of the budget when voters have ordinal preference rankings over projects. Examples of such portioning problems are participatory budgeting, time shares, and parliament elections. We introduce a family of rules for portioning, inspired by positional scoring rules. Rules in this family are given by a scoring vector (such as plurality or Borda) associating a positive value with each rank in a vote, and an aggregation function such as leximin or the Nash product. Our family contains well-studied rules, but most are new. We discuss computational and normative properties of our rules. We focus on fairness, and introduce the SD-core, a group fairness notion. Our Nash rules are in the SD-core, and the leximin rules satisfy individual fairness properties. Both are Pareto-efficient. ## Full text ## 1 Introduction The members of an organization need to divide its budget among several projects. They have different opinions about the relative value of different projects, and would like to vote over the budget. What kind of voting rule could they use? Some cities let citizens vote over the use of the city budget, giving rise to participatory budgeting. In deployed applications (such as in Paris or Brazil), the projects are indivisible, and can be either fully funded or not at all, such as refurbishing a school or adding a bike lane. We focus on divisible projects on which an arbitrary fraction of the budget could be spent, such as 'education' or 'transport' or 'parks'. The result of the vote can be visualized as a pie chart showing which percentage of the budget is spent on each type of expense. The 'budget' need not be monetary, and we refer to this general scheme as portioning. There are many applications: - A conference board deciding how much time to assign to talks, poster sessions, invited talks, and coffee breaks. - A parliamentary election deciding what percentage of parliament seats should go to each party. - Coauthors deciding how much space to devote to various topics in a textbook or article with fixed total length. - A company annually donates money to charity, and lets employees vote over which charities should receive a donation. We ask voters to report their preferences over projects as rankings, the most common format considered in social choice. If a project is ranked more highly, the voter thinks it is more worthwhile and should receive a larger fraction of the budget. The space of sensible aggregation rules is large, so let us illustrate some important design considerations by an example. ## An Example A family is planning a road trip by car. The family members have different musical tastes; they need to decide which type of music to play for how long. The genres under consideration are a, b, c, d, e. The three children all think a ≻ b ≻ c ≻ d ≻ e; mother thinks e ≻ b ≻ c ≻ d ≻ a; and father thinks c ≻ a ≻ e ≻ d ≻ b. ![Image](https://ijcai.org/proceedings/2019/fulltext/2/image_000000_bc8c2c4c068384fc209bf05b187b146d3c0d68495b5a98983068c07b97013441.png) One simple way to split the time is to allocate each person the same share of time (20%) and let them decide what music to play, as a temporary dictator. During their time, each person plays their favorite music. To the social choice theorist, this rule sounds familiar: it is formally identical to Random Dictatorship, whose output is usually seen not as a division of a budget, but as a probability distribution. Indeed, any probabilistic social choice function can be repurposed to divide budgets; but these are often not attractive for portioning since many of them were designed as tie-breaking devices. ![Image](https://ijcai.org/proceedings/2019/fulltext/2/image_000001_3dca4b2bf9320bee53fdb8fca73465eb7fd60fdf07787bfdefe9442f046a2989.png) The output of random dictatorship can be a good choice, especially if our family strongly prefers their top choice to any other music. But it is also plausible that mother and the children agree that b is good common ground. Random Dictator- ship, using plurality scores, ignores this. Instead, we could impute Borda scores on our family: for example, the children give 4 'utility' points to a, 3 to b, 2 to c, 1 to d, and 0 to e. Proportional Borda then allocates time in proportion to the total Borda score of the genres. This leads to a significant time share for b. On the other hand, the family now also listens to d, which is dominated: everyone agrees that c is better than d! So Proportional Borda is inefficient. ![Image](https://ijcai.org/proceedings/2019/fulltext/2/image_000002_2adfaf80b885203b3e3e93da20e13292138c8d49a6338727663dd5547384a873.png) To restore efficiency, it makes sense to maximize a notion of social welfare. Suppose the utility enjoyed by a family member is the weighted average of the Borda scores of the music played on the trip, where the weights come from the fraction of time spent on each genre. Utilitarian Borda then picks the distribution where the sum of utilities is greatest. In our example, we listen to a during 100% of the time. While this is Pareto-efficient, it is unfair to mother, who only gets to listen to her least-preferred style. In fact, many rules suffer from this phenomenon of completely overriding some voters' preferences: For example, the 'maximal lotteries' rule also only plays a since it is the Condorcet winner. ![Image](https://ijcai.org/proceedings/2019/fulltext/2/image_000003_f9a1d9164bf4944842aa0037cee66c6106d507fd0e4684a0c799b47eb470dad6.png) To avoid frustration during the trip, we may take a more egalitarian approach, and aim to give every family member a significant share. BordaEgalitarian picks the distribution maximizing the utility of the worst-off passenger. In our example, we can give every passenger an average Borda-utility of 2.4. To ensure Pareto-efficiency, we can refine this to BordaLeximin (which does not change the outcome on this example). ![Image](https://ijcai.org/proceedings/2019/fulltext/2/image_000004_20c5bb13fceb64352bb1231a5bdab782dc668e06c4f7743a21f5cfede71de11e.png) We can also maximize Nash social welfare, the product of utilities. This is often seen as a compromise between maximizing utilitarian and egalitarian welfare notions. While egalitarian rules perform well when we wish to be fair to each individual, Nash rules tend to be fair to groups. In our example, the children form a large group, and Borda-Nash plays a almost half the time. If there were more children with the same preferences in the car, Borda-Nash would increase the time share of a. In contrast, Borda-Leximin avoids playing a to benefit the mother, and the output of egalitarian rules does not change with the number of children. Depending on the context, either of these behaviors might be more appropriate. ## Our Contributions We introduce a class of aggregation rules called positional social decision schemes. Rules in this class first convert each input ranking into scores for the alternatives, using a scheme such as plurality or Borda scores. Then, they select a distribution of the budget maximizing social welfare given those scores, where different notions of welfare can be used; classically, we consider utilitarian, egalitarian (leximin), and Nash welfare. Our class contains known rules such as random dictatorship, but most have not been studied. We begin by noting basic properties of the rules in our class, giving closed forms and equivalent definitions in some cases. We also show that the rules in this class can be calculated or approximated in polynomial time. For rules based on Nash welfare, we show that their output can involve irrational percentages; we prove that those rules are guaranteed to be rational if the scoring vector used is plurality or veto, but that no other scoring vector guarantees rational output. We then formalize intuitive notions of fairness in the budgeting context. The axioms we propose require that no individual is ignored by the procedure, in the sense of having none of the budget allocated to favored causes. We also give some group fairness notions. Our strongest axiom is the SD-core which, roughly, requires that a group of α% of the voters can control what happens with α% of the budget. We show that the rules in our class based on Nash welfare satisfy the SD-core, while the egalitarian rules satisfy the individual fairness notions. We close by studying the performance of our rules on standard social choice properties, such as Pareto-efficiency, strategyproofness, and monotonicity. ## Related Work Bogomolnaia et al. [2005] introduced the portioning problem, motivated by time-sharing. They assume dichotomous preferences, and agents report a subset of the alternatives (an approval vote), rather than rankings. They study the compatibility of Pareto-efficiency and strategyproofness, with positive results (for example, spending the entire budget on the approval winner satisfies both requirements). However, after adding a fairness axiom, they get an impossibility result. A related impossibility is proved by Duddy [2015]. Aziz et al. [2019] introduce some new rules based on welfare maximization, and introduce new fairness axioms (including a core notion), and a weakened strategyproofness axiom. Brandl et al. [2019] study cases when the budget is owned by the voters. Fain et al. [2016] study portioning in a cardinal model which allows agents to give a full utility function over alternatives (which may also feature decreasing returns). They study the core and connect it to the Lindahl equilibrium from the study of public goods, and prove that a core solution always exists. For a broad class of utility functions, they show that a core solution can be found in polynomial time by solving a suitable convex program. They also use differential privacy to design a mechanism for this setting which satisfies approximate versions of efficiency, truthfulness, and the core. With rankings as input, this setting has been studied in the formally isomorphic guise of probabilistic social choice [see Brandt, 2018 for a recent survey]. In this literature, the outcome distribution is interpreted as a random device, which is used to eventually implement a single outcome. This makes notions of fairness and proportionality less relevant, and it is seen as desirable for a rule to randomize as little as possible. For example, the maximal lotteries rule [Kreweras, 1965; Brandl et al., 2016], while attractive according to consistency axioms, spends the entire budget on the Condorcet winner if it exists. This is often undesirable in a budgeting context. On the other hand, results like Gibbard's [1977] random dictatorship theorem are important in the portioning context. Some papers on probabilistic social choice also discuss fairness concerns [see, e.g., Aziz et al., 2018b; Aziz and Stursberg, 2014]. In a related setting, projects are indivisible and come with a fixed cost; they can either be fully funded or not at all. This is known as combinatorial public projects [Papadimitriou et al., 2008] in a literature focussing on computational aspects and truthfulness. This setting is also what is often meant by "participatory budgeting" [Cabannes, 2004; Goel et al., 2016; Benade et al., 2017]. Several recent papers have studied fairness in this setting [Aziz et al., 2018a; Fain et al., 2018; Conitzer et al., 2017], inspired by multi-winner elections, for which fairness and proportionality are well-studied [Aziz et al., 2017; Faliszewski et al., 2017]. The literature on cake-cutting and item allocation is mostly unrelated to our work: in those settings, goods are allocated to specific agents for their exclusive use. In our setting, resources are spent on projects which can be enjoyed by all agents. On a technical level, the idea of scoring followed by aggregation has been explored in fair division [Brams and King, 2005; Darmann and Schauer, 2015; Baumeister et al., 2016], and work on group fairness raises related issues [see, e.g., Manurangsi and Suksompong, 2019; Bade and Segal-Halevi, 2018]. ## 2 Positional Social Decision Schemes Let X = {x1, . . . , xm} be a set of alternatives and N = {1, . . . , n} be a set of voters. Let L(X) be the set of linear orders over X. For ≻ ∈ L(X), the rank of alternative xj is r(≻, xj) = 1 + |{xi ∈ X : xi ≻ xj}|. A profile P = (≻1, . . . ,≻n) ∈ L(X)n is a collection of linear orders, one for each voter. We write abc as shorthand for a ≻ b ≻ c. Let ∆(X) = {p : X → [0, 1] : ∑x∈Xpx = 1} be the set of (probability) distributions over X. We use notation like 12 x1 + 1 2 x2 to specify a distribution, and write xj for the distribution with pxj = 1. We say that z : X → [0, 1] is a partial distribution if ∑x∈Xzx ⩽ 1. A social decision scheme (SDS) is a function F assigning to each P ∈ L(X)n a nonempty subset of ∆(X), usually a singleton. A scoring vector for m alternatives is a vector s = (s1, . . . , sm) of numbers with s1 ⩾ s2 . . . ⩾ sm and s1 > sm. We usually assume sm = 0. A scoring vector s is strictly decreasing if sj > sj+1 for all j < m. The Borda vector is bor = (m- 1,m- 2, . . . , 0); the plurality vector is plu = (1, 0, . . . , 0); the veto vector is vet = (1, . . . , 1, 0). For a fixed profile P, we write s[i, j] = sr(≻i,xj) for the s-score that voter i ∈ N assigns to alternative xj ∈ X. These scores can be lifted to distributions in a natural way; the sscore of p ∈ ∆(X) for i is s[i, p] = ∑mj=1 pjs[i, j]. Finally, define the utility vector s[p] = (s[1, p], . . . , s[n, p]). A welfare ordering is a weak order ⩾W ordering utility vectors (α1, . . . , αn) ∈ Rn⩾0 . The main examples are utilitarianism which orders vectors by their sum, egalitarianism which uses the minimum, the Nash product which uses multiplication, and leximin which sorts the components of the utility vector and then orders sorted vectors lexicographically. By combining a scoring vector and a welfare ordering, we can define a positional social decision scheme. Definition 1. For scoring vector s and a welfare ordering ⩾W , define the social decision scheme Fs,⩾W so that for all P, For the specific ⩾W mentioned, we usually call these rules s-utilitarianism, s-egalitarianism, s-leximin, and s-Nash. Example 1. Consider the profile P = (ab, ab, ba) over two alternatives, with s = (1, 0). Then s-utilitarianism selects a, s-egalitarianism selects 12 a+ 12 b, and s-Nash selects 23 a+ 13 b. For normative analysis, it is useful to extend voters' rankings of the alternatives to (partial) preferences over distributions. We assume linear preferences: there is an unknown utility function ui : X → R consistent with ≻i such that i prefers those distributions p with higher average utility ∑x∈X ui(x)px. A classical way of ranking distributions despite not knowing ui uses stochastic dominance (SD). If p and q are (possibly partial) distributions, we write This definition is justified by the following standard equivalence: We have p ≽SD i q if and only if ∑x∈X ui(x)px ⩾ ∑x∈X ui(x)qx for all utility functions ui : X → R satisfying minx∈X ui(x) = 0 and ui(xk) > ui(xj) iff xk ≻i xj. The condition that the utility of the worst alternative is 0 is necessary to allow SD-comparisons of partial distributions: we assume that voters are indifferent between not spending part of the budget or spending it on their worst alternative. This is crucial for the definition of the SD-core in Section 4. ## 3 Computation and Basic Properties In this section, we look at elementary properties of the family of rules we have defined. We will note that several of the rules are familiar from the probabilistic context. We also study the computational complexity of finding an optimal distribution. ## 3.1 Utilitarianism From a utilitarian perspective, it never pays to spend part of the budget on alternatives whose total s-score is not maximal: shifting that spending to an s-maximal alternative increases utilitarian welfare. Thus, up to ties, s-utilitarianism never mixes and spends all resources on the s-winner. Formally, sutilitarianism selects those distributions p for which pxj > 0 only if the score ∑i∈N s[i, j] is maximum. Since the behavior of s-utilitarianism is familiar from work on scoring rules in voting, we will not study it in much detail. ## 3.2 Egalitarianism Plurality-egalitarianism is easy to understand: it returns the uniform distribution over all alternatives that are ranked top by at least one voter. In the probabilistic context, this rule is known as egalitarian simultaneous reservation [Aziz and Stursberg, 2014]. For other scoring vectors, s-egalitarianism is less simple, and it need not return a uniform distribution (see the example of Section 1). However, one can easily evaluate s-egalitarianism using linear programming: Now, s-egalitarianism is not very decisive, and may select Pareto-inferior outcomes. When P = (abcd, acbd, bdac), and s = (1, 1, 0, 0), it selects all distributions of the form where 0 ⩽ p, q ⩽ 1 and 12 ⩽ p + q ⩽ 1. Note that d can get a positive fraction even though every voter prefers b to d (so that d is Pareto-dominated). A standard way of making egalitarianism more decisive and more efficient is by using leximin instead. In the above example, s-leximin uniquely selects 12 a+ 12 b. It is easy to see that s-leximin will never give a positive fraction to a Pareto-dominated alternative. It is still possible to evaluate s-leximin in polynomial time, by solving O(n2 ) linear programs successively. Our algorithm uses the convexity of ∆(X), which allows it to greedily fix the identity of the agent who is worst-off in the current iteration. Theorem 1. For every s, one can compute a distribution selected by s-leximin in polynomial time. Proof. The algorithm is specified as Algorithm 1 that requires running at most n(n + 1)/2 linear programs. Relabel the voters in N as i1, . . . , in in the order that they were added to N ′ by the algorithm. We argue by induction on k that every distribution p selected by s-leximin satisfies ## Algorithm 1 Computing an s-leximin distribution Set N ′ ← ∅. For i ∈ N, we will set ti once i is added to N ′ . while N ′ ̸= N do Using linear programming, find the maximum value t∗ such that there exists a distribution (p1, . . . , pm) satisfying for each i′ ∈ N \ N ′ do Using linear programming, find the maximum ε such that there exists a distribution (p1, . . . , pm) satisfying If ε = 0, add i′ to N ′ and set ti′ ← t∗ . return the solution (p1, . . . , pm) of the last LP solved ∑mj=1 s[ik, j]pj = tik . Suppose k ⩾ 1, and we have shown this holds for i1, . . . , ik-1. Let p be a distribution selected by s-leximin. In the iteration before ik is added to N ′ , because p satisfies the inductive hypothesis, from the upper LP, we know that the least s-score obtained by a voter in N \ N ′ under p is t∗ . But which voter? The lower LP tests, for each i′ ∈ N \ N ′ , whether i′ obtains s-score exactly t∗ in all leximin distributions. Such a voter must exist: suppose not, and for each i′ ∈ N \ N ′ , let p(i′ ) be a leximin distribution where i′ obtains s-score strictly higher than t∗ . Write p′ = ∑i′∈N\N ′ 1 |N\N ′ | p(i′ ). Then p′ satisfies the inductive hypothesis (because each p(i′ ) does), but the least s-score obtained by a voter in N \ N ′ under p′ is strictly higher than t∗ , contradicting the choice of t∗ . Thus, there is a voter i∗ ∈ N \N ′ who obtains s-score t∗ in all leximin distributions. This voter is named ik and tik is set to t∗ , establishing the inductive step. ## 3.3 Nash product The defining optimization problem of s-Nash is a convex program which can be efficiently solved using standard solvers. Formally, one can approximate optimum Nash welfare within an additive factor of ε in time polynomial in n, m, and 1/ε. Thus, all the usual decision problems associated with computing s-Nash are easy. However, writing down the precise output in decimal expansion is impossible, as there are instances where s-Nash uniquely returns a distribution with irrational fractions. For instance, for P = (abc, acb, cab, cab) and s = (2, 1, 0), s-Nash uniquely returns 1+√33 8 a+ 7-√33 8 c. To further understand s-Nash, let us analyze the first-order conditions of the convex program. Write down the Lagrangian At an optimal solution p, we have This implies λpj = ∑i∈N s[i,j] s[i,p] pj. Summing over all j, thus since s[i, p] = ∑mj=1 s[i, j] · pj by definition. It follows that For example, using (1), we can characterize plurality-Nash [see also Moulin, 2003, Example 3.6]: Theorem 2. Plurality-Nash selects p with pj = pl(xj)/n for all j, where pl(xj) is the number of voters placing xj top. Proof. Let p be optimal for plurality-Nash. If some voter i puts xj top then pj > 0, or else s[i, p] = 0 and the Nash product equals 0. By (1), we get n = ∑i∈N s[i,j] s[i,p] = pl(xj)/pj, and so pj = pl(xj)/n. It follows that pj = 0 whenever no voter places xj top. Thus, we see that plurality-Nash is the same rule as random dictatorship, familiar from the probabilistic context. The veto-Nash rule seems sensible when alternatives are nuisances, where each agent wants to minimize the amount spent on the worst option. In some sense, veto-Nash for nuisances is as relevant as plurality-Nash for goods, in the portioning context. Mathematically, veto-Nash is also well-behaved. While we do not provide a closed formula, the following result shows that an exact optimum for veto-Nash can be found in polynomial time (and that it is rational). It gives a collection of at most m different explicit rational distributions, and guarantees that the veto-Nash optimum is among them. Theorem 3. Let P be a profile, and let vt(xj) be the number of voters placing xj bottom. Relabel alternatives so that vt(x1) ⩽ · · · ⩽ vt(xm). If vt(xj) = 0 for some xj, vetoNash selects all distributions over such alternatives. Otherwise, there is k ∈ [m] with (k - 1)vt(xk) < ∑kj=1 vt(xj), such that veto-Nash selects the distribution p with Proof. If vt(xj) = 0 for some xj, then the best-possible Nash product of 1 can be achieved, and is achieved precisely by distributions whose support consists of never-vetoed alternatives. Now suppose that vt(xj) > 0 for all xj. Let p be a distribution selected by veto-Nash, and take k maximal such that pk > 0. Then we must also have pj > 0 for all j = 1, . . . , k - 1. (If not, and pj = 0 for some j, consider the distribution q with ql = pl for all l, except that qj = qk = 12 pk. Then, since vt(xj) ⩽ vt(xk), q has strictly higher Nash product than p, contradiction.) Thus, for i = 1, . . . , k, equation (1) applies and can be written as Summing the equations (2) for i = 1, . . . , k, we get Using n = ∑kj=1 vt(xj) + ∑mj=k+1 vt(xj), rearrange this as From the symmetry of the equations (2), the values vt(xi) 1-pi must be equal for all i ∈ [k]. Since we know their sum, we get Rearranging, we arrive at the conclusion that These values sum to 1, and are non-negative provided that (k1)vt(xk) < ∑kj=1 vt(xj). If this condition is not satisfied, the choice of k cannot lead to a veto-Nash optimum. This gives an algorithm for computing veto-Nash exactly: if some alternatives are never vetoed, return any distribution over these. Otherwise iterate over all k ∈ [m] satisfying the condition of the theorem and calculate the corresponding distribution, and return the one with highest Nash product. Example 2. If 2, 3, 3 and 5 voters rank x1, x2, x3 and x4 last, respectively, then k = 2 and 3 satisfy the condition of Thm. 3. Thus, either p = 35 x1 + 25 x2 or p′ = 12 x1 + 14 x2 + 14 x3 is optimal. The former has higher Nash product, so p is optimal. Theorems 2 and 3 show that both plurality-Nash and vetoNash are rational. Are there any other score vectors s such that s-Nash is guaranteed to be rational? The answer is no: for every s other than plurality and veto, we can construct a profile where s-Nash uniquely returns an irrational distribution. This result suggests that a convex programming solver is the best way of computing s-Nash for s other than plurality and veto. Theorem 4. Let m ⩾ 3, and let s = (s1, . . . , sm) ∈ Qm be a score vector with sm = 0 and normalized so that s1 = 1. Unless s = (1, 0, . . . , 0) or s = (1, . . . , 1, 0), there exists a profile P ∈ L(X)n for some n ∈ N such that s-Nash returns a unique distribution p with p ̸∈ Qm. Proof. We construct four infinite families of examples, for different shapes of score vectors s. Due to space constraints, we only consider the case m = 3 here, and only sketch the algebra required. The other families require a more involved construction, but work using similar calculus. Suppose m = 3, and let s = (1, rs , 0), where 0 < rs < 1 and rs is in lowest terms. Let c be a large-enough integer. Consider the following profile: c voters with abc, one voter bac, one voter with bca. Note that b Pareto-dominates c, so that pc = 0. Let (x, 1 - x, 0) be the distribution selected by s-Nash. One can show that 0 < x < 1 if c is large enough. Now, the Nash product obtained by this distribution is (x+ rs(1-x))c · ((1-x) + rsx) · (1-x). By optimality, x must make the derivative d/dx vanish. After a calculation, cancelling non-zero factors, this implies that This is a quadratic equation with integer coefficients. Solutions to the equation ax2 +bx+c = 0 involve the term √b2 - 4ac; thus, they are rational if and only if b2 -4ac is a perfect square. In our case, the term under the square root simplifies to The first summand is a large perfect square, and the second summand is a constant. Since the distance between consecutive perfect squares is large (in the sense that (z + 1)2 - z2 = 2z + 1 = Θ(z)), the discriminant cannot be a perfect square for large enough c. Hence, x is irrational. ## 4 Fairness, Proportionality, and the SD-core Usually, s-utilitarianism spends 100% on a single alternative. Some agents might rank this alternative in a very low position, or even in last place. In some contexts, this is unfair and might rule out s-utilitarianism. In this section, we formalize several notions of fairness, and show that s-egalitarianism satisfies individual fairness, and that s-Nash satisfies group fairness. A minimal fairness axiom is positive share [adapted from Bogomolnaia et al., 2005] which requires that if voter i ranks x in last position, then px < 1. Hence, for every voter, a positive amount is spent on alternatives not ranked in last position. As suggested above, s-utilitarianism fails positive share for any s. However, provided that sm = 0, positive share is satisfied by s-egalitarianism, s-leximin, and s-Nash. To see this, note that the uniform distribution has positive egalitarian and Nash welfare, whereas a distribution violating positive share has zero egalitarian and Nash welfare. We can strengthen positive share to individual fair share, requiring that if voter i ranks x in last position, then px ⩽ 1- 1n . Thus, for each voter, at least 1n is spent on alternatives not ranked last. Note that the distribution identified by random dictatorship satisfies this condition and has egalitarian welfare at least 1n , normalizing s1 = 1. Thus, the optimum s-egalitarian welfare is at least 1n , and hence s-egalitarianism and s-leximin satisfy individual fair share (recalling that sm = 0). Below, we show that s-Nash also satisfies it. Consider X = {a, b}, with 9 voters ab and 1 voter ba. Then s-egalitarianism returns 12 a + 12 b. While this is individually fair, the group of 9 voters is underrepresented. If we desire fairness to groups, we need a stronger axiom. One option is this: if k out of n voters rank x last, then px ⩽ 1 - kn , so at least kn is spent on alternatives other than x. This condition is failed by s-egalitarianism and s-leximin, but s-Nash satisfies it. In our example, s-Nash picks 9 10 a+ 1 10 b. All the notions above focus on avoiding voters' last-ranked alternative. Despite working in an ordinal setting, using the SD-extension, we can define a group fairness notion that uses more than just the last-ranked alternative. An important underlying intuition is that agents are "entitled" to 1/n of the budget, and this share should be spent in accordance to their preferences. Similarly, a group S ⊆ N of k agents could pool together and be entitled to k/n of the budget. The intuitive notion of entitlement can be formalized using a core-style concept. A coalition S ⊆ N of voters is supposed to be able to 'control' a fraction of |S|/n of the entire budget. The notion of control is ambiguous since coalitions may overlap and each share of the budget is simultaneously controlled by several coalitions. However, the entitlement of S is certainly violated under p if S can come up with a way of using only its entitlement |S|/n which all members prefer to the way that p uses the entire budget. Figure 1: The SD-core of the profile (abc, acb, bca) within the simplex of all distributions. The shaded area shows the distributions that are in the SD-core. The blue line shows the output of s-Nash for all s = (1, q, 0) with q ∈ [0, 1]. Plurality-Nash selects 23 a + 1 3 b, BordaNash selects 0.58a + 0.42b, and veto-Nash selects 1 3 a + 13 b + 1 3 c. ![Image](https://ijcai.org/proceedings/2019/fulltext/2/image_000005_fc39ebee89e7fe6f6291b0c1e2cacdcacb1cc2f53f0a6b5611d3991a273e84e0.png) Definition 2. A coalition S ⊆ N SD-blocks a distribution p if there exists a partial distribution z with ∑x∈X zx = |S|/n such that z ≽SD i p for all i ∈ S, and z ≻SD j p for some j ∈ S. A distribution p is in the SD-core if no coalition SD-blocks p. If a distribution p lies in the SD-core, then it also satisfies our other properties: Suppose not, and there is a coalition S of voters that rank x last, where px > 1-|S|/n. Then S can SDblock p: Write ε = px-(1-|S|/n) > 0 and define a deviation z with zy = py + ε/(m- 1) for all y ∈ A \ {x}, and zx = 0. Then ∑a∈A za = ε+ ∑y∈A\{x} py = ε+(1-px) = |S|/n, so that z has the required total weight. It is easy to check that z ≻SD i p for all i ∈ S. Thus, p is not in the SD-core. For an example, take the profile with voters abc, acb, bca. Which distributions p are in the SD-core? First, singleton coalitions {i} block p if px > 2 3 for i's bottom alternative x, using z = 1 3 y where y is i's top alternative. The coalition of abc and acb blocks all p with pa+pb ⩽ 2 3 and pa+pc ⩽ 23 (one inequality strict), using z = 23 a. All other distributions are in the SD-core. Figure 1 shows the simplex of all distributions, with the SD-core shaded (non-convex in this example). Figure 1 shows the outputs of s-Nash for all s as a blue line. The blue line is entirely contained in the SD-core. In fact, s-Nash is always in the SD-core. We give a direct argument using equation (1). The result can also be obtained via the theory of Lindahl equilibrium [Fain et al., 2016; Foley, 1970]. Theorem 5. For any s with sm = 0, any distribution selected by s-Nash is in the SD-core. Proof. Suppose p is selected by s-Nash. For a contradiction, assume that S ⊆ N is a blocking coalition of agents, deviating using (z1, . . . , zm) ∈ [0, 1]m with ∑mj=1 zj = |S|/n, such that z ≽SD i p for all i ∈ S, and z ≻SD j p for some j ∈ S. Now, s defines utilities compatible with the voters' ordinal preferences, and thus s[i, z] ⩾ s[i, p] for all i ∈ S, and s[j, z] > s[j, p] for some j ∈ S. Then The last inequality follows because the sum contains only nonnegative terms, |S| of which are at least 1, and one of which is strictly larger than 1. This is a contradiction. Thus, the s-Nash rules are particularly fair to groups. The SD-core can also be seen as a proportionality requirement: the common resource should be divided so that the share of an alternative is proportional to its support. For example, this is of interest in politics, to divide parliament seats among parties. ## 5 Axiomatic Properties We now briefly study other axiomatic properties of our rules. A more careful treatment appears in the full version; here we ignore ties when defining strategyproofness and monotonicity. Pareto-efficiency. Adistribution q SD-dominates p if q ≽SD i p for all i ∈ N, and q ≻SD j p for some j ∈ N. A distribution p is SD-efficient if no distribution dominates it. Note that SDcore implies SD-efficiency (with S = N), and so s-Nash rules are SD-efficient when sm = 0. More generally, one can show that s-utilitarianism, s-leximin, and s-Nash are SD-efficient provided that s is strictly decreasing. Strategyproofness. A social decision scheme is (strongly) SD-strategyproof if, when a voter misreports their ranking, the SDS selects a distribution that the voter believes is weakly SD-worse than the distribution resulting from a truthful report. Plurality-Nash (i.e., random dictatorship) is strategyproof in this sense. A well-known result of Gibbard [1977] shows that this is the only SDS that is strategyproof and also anonymous and Pareto-efficient. Hence, all other SD-efficient rules we have considered are manipulable. Monotonicity. An SDS F is monotone if, when we change a profile P into P ′ by moving up an alternative x in a voters' ranking (by swapping), then the share of x weakly increases, i.e., F(P ′ )x ⩾ F(P)x. This is clearly satisfied by s-utilitarianism, and also by plurality-Nash. However, other sNash rules (and also s-leximin) may fail it. If s = (2, 1, 0) and P = (abc, abc, abc, acb, bac, cba), then s-Nash selects an irrational distribution which rounds to 0.642a + 0.333b + 0.024c. If the bac voter moves c up one place (to get bca), then s-Nash selects 0.5a + 0.5b. Thus, c's share has strictly decreased. Monotonicity is a kind of fairness to alternatives (x gets more if it performs better), while our rules aim for fairness to voters. ## 6 Conclusions We have introduced a class of aggregation rules which can be used to make budget decisions. We have found that our rules are attractive on efficiency and fairness grounds. We have introduced concepts such as the SD-core, a group fairness and proportionality notion, satisfied by Nash-based rules. Egalitarian rules satisfy individual fairness, which may be particularly desirable in small electorates. ## References 1. [Aziz and Stursberg, 2014] H. Aziz and P. Stursberg. A gen- eralization of probabilistic serial to randomized social choice. In Proceedings of the 28th AAAI Conference on Artificial Intelligence (AAAI), pages 559-565. AAAI Press, 2014. 2. [Aziz et al., 2017] H. Aziz, M. Brill, V. Conitzer, E. Elkind, R. Freeman, and T. Walsh. Justified representation in approval-based committee voting. Social Choice and Wel- fare, 48(2):461-485, 2017. 3. [Aziz et al., 2018a] H. Aziz, B. E. Lee, and N. Talmon. Pro- portionally representative participatory budgeting: Axioms and algorithms. In Proceedings of the 17th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 23-31. IFAAMAS, 2018. 4. [Aziz et al., 2018b] H. Aziz, P. Luo, and C. Rizkallah. Rank maximal equal contribution: A probabilistic social choice function. In Proceedings of the 32nd AAAI Conference on Artificial Intelligence (AAAI), pages 910-916, 2018. 5. [Aziz et al., 2019] H. Aziz, A. Bogomolnaia, and H. Moulin. Fair mixing: the case of dichotomous preferences. In Pro- ceedings of the 20th ACM Conference on Economics and Computation (ACM-EC), 2019. 6. [Bade and Segal-Halevi, 2018] S. Bade and E. Segal- Halevi. Fair and efficient division among families. arXiv:1811.06684, 2018. 7. [Baumeister et al., 2016] D. Baumeister, S. Bouveret, J. Lang, N.-T. Nguyen, T. T. Nguyen, J. Rothe, and A. Saffidine. Positional scoring-based allocation of indivisible goods. Autonomous Agents and Multi-Agent Systems, pages 1-28, 2016. 8. [Benade et al., 2017] G. Benade, S. Nath, A. D. Procaccia, and N. Shah. Preference elicitation for participatory bud- geting. In Proceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI), pages 376-382. AAAI Press, 2017. 9. [Bogomolnaia et al., 2005] A. Bogomolnaia, H. Moulin, and R. Stong. Collective choice under dichotomous preferences. Journal of Economic Theory, 122(2):165-184, 2005. 10. [Brams and King, 2005] S. J. Brams and D. L. King. Efficient fair division: Help the worst off or avoid envy? Rationality and Society, 17(4):387-421, 2005. 11. [Brandl et al., 2016] F. Brandl, F. Brandt, and H. G. Seedig. Consistent probabilistic social choice. Econometrica, 84(5):1839-1880, 2016. 12. [Brandl et al., 2019] F. Brandl, F. Brandt, D. Peters, C. Stricker, and W. Suksompong. Donor coordination: Collective distribution of individual contributions. 2019. Working paper. 13. [Brandt, 2018] F. Brandt. Collective choice lotteries: Dealing with randomization in economic design. In J.-F. Laslier, H. Moulin, R. Sanver, and W. S. Zwicker, editors, The Future of Economic Design. Springer-Verlag, 2018. Forth- coming. [Cabannes, 2004] 14. Y. Cabannes. Participatory budgeting: a significant contribution to participatory democracy. Envi- ronment and Urbanization, 16(1):27-46, 2004. 15. [Conitzer et al., 2017] V. Conitzer, R. Freeman, and N. Shah. Fair public decision making. In Proceedings of the 18th ACM Conference on Economics and Computation (ACM- EC), pages 629-646, 2017. 16. [Darmann and Schauer, 2015] A. Darmann and J. Schauer. Maximizing Nash product social welfare in allocating indi- visible goods. European Journal of Operational Research, 247(2):548-559, 2015. 17. [Duddy, 2015] C. Duddy. Fair sharing under dichotomous preferences. Mathematical Social Sciences, 73:1-5, 2015. 18. [Fain et al., 2016] B. Fain, A. Goel, and K. Munagala. The core of the participatory budgeting problem. In Proceedings of the 12th International Workshop on Internet and Network Economics (WINE), Lecture Notes in Computer Science (LNCS), pages 384-399, 2016. 19. [Fain et al., 2018] B. Fain, K. Munagala, and N. Shah. Fair allocation of indivisible public goods. In Proceedings of the 19th ACM Conference on Economics and Computation (ACM-EC), pages 575-592, 2018. 20. [Faliszewski et al., 2017] P. Faliszewski, P. Skowron, A. Slinko, and N. Talmon. Multiwinner voting: A new challenge for social choice theory. In U. Endriss, editor, Trends in Computational Social Choice, chapter 2. 2017. 21. [Foley, 1970] D. K. Foley. Lindahl's solution and the core of an economy with public goods. Econometrica, 38(1):66- 72, 1970. 22. [Gibbard, 1977] A. Gibbard. Manipulation of schemes that mix voting with chance. Econometrica, 45(3):665-681, 1977. 23. [Goel et al., 2016] A. Goel, A. K. Krishnaswamy, S. Sakshu- wong, and T. Aitamurto. Knapsack voting: Voting mecha- nisms for participatory budgeting. Unpublished manuscript, 2016. 24. [Kreweras, 1965] G. Kreweras. Aggregation of preference orderings. In Mathematics and Social Sciences I: Proceed- ings of the seminars of Menthon-Saint-Bernard, France (1-27 July 1960) and of Gösing, Austria (3-27 July 1962), pages 73-79, 1965. 25. [Manurangsi and Suksompong, 2019] P. Manurangsi and W. Suksompong. Computing a small agreeable set of indi- visible items. Artificial Intelligence, 268:96-114, 2019. 26. [Moulin, 2003] H. Moulin. Fair division and collective wel- fare. MIT Press, 2003. 27. [Papadimitriou et al., 2008] C. Papadimitriou, M. Schapira, and Y. Singer. On the hardness of being truthful. In Pro- ceedings of the 49th Symposium on Foundations of Com- puter Science (FOCS), pages 250-259. IEEE, 2008.