Fractional approval voting

Desired properties

Efficiency properties

Pareto-efficiency (PE) means no mixture gives a higher utility to one agent and at least as high utility to all others.

Ex-post PE is a weaker property, relevant only for the interpretation of a mixture as a lottery. It means that, after the lottery, no outcome gives a higher utility to one agent and at least as high utility to all others (in other words, it is a mixture over PE outcomes). For example, suppose there are 5 candidates (a,b,c,d,e) and 6 voters with approval sets (ac, ad, ae, bc, bd, be). Selecting any single candidate is PE, so every lottery is ex-post PE. But the lottery selecting c,d,e with probability 1/3 each is not PE, since it gives an expected utility of 1/3 to each voter, while the lottery selecting a,b with probability 1/2 each gives an expected utility of 1/2 to each voter.

PE always implies ex-post PE. The opposite is also true in the following cases:

• When there are at most 4 voters, or at most 3 candidates.
• When the candidates can be ordered on a line such that each approval set is an interval (analogously to single peaked preferences).

A weak efficiency requirement is unanimity: if some candidate is approved by all voters, and it is the only such candidate, it should receive the whole budget.

Fairness properties

Fairness requirements are captured by variants of the notion of fair share (FS).

Individual-FS (also called Fair Welfare Share) means that the utility of each voter i is at least 1/n, that is, at least 1/n of the budget is allocated to candidates approved by i.

Individual-Outcome-FS means that the utility of each voter i is at least his utility in a lottery that selects a candidate randomly, that is, at least k/|C|, where k is the number of candidates approved by i.

• Individual-FS and individual-outcome-FS are insufficient since they ignore groups of voters. For example, if 99% of the voters approve X and 1% approve Y, then both properties allow to give 1/2 of the budget to X and 1/2 to Y. This is arguably unfair for the group of Y supporters.

Single-vote-FS (also called faithful) means that, if each voter approves a single candidate, then the fraction assigned to each candidate j equals the number of voters who approve j divided by n.

• Single-vote-FS is a basic requirement, but it is insufficient since it does not say anything about the case in which voters may approve two or more candidates.

Unanimous-FS means that, for each set S of voters with identical preferences, the utility of each member in S is at least |S|/n.

• Unanimous-FS implies single-vote-FS, but it is still insufficient since it does not say anything about groups of agents whose approval-sets overlap.

Group-FS (also called proportional sharing or GFS) means that, for each voter set S, the total budget allocated to candidates approved by at least one member of S, is at least |S|/n.

• Group-FS implies unanimous-FS, single-vote-FS and individual-FS.
• Group-FS is equivalent to a property called decomposability: it is possible to decompose the distribution to n distributions of sum 1/n, such that the distribution recommended to agent i is positive only on candidates approved by i.

Average-FS (also called AFS) means that, for each voter set S with at least one approved candidate in common, the average utility of voters in S is at least |S|/n.

Core-FS means that, for each voter set S, there is no other distribution of their |S|/n budget, which gives all members of S a higher utility. The notion is an adaptation of the core of a cooperative game.

• Core-FS implies Group-FS.
• Average-FS and core-FS are logically incomparable: a distribution may satisfy one of them and violate the other.

Approximate fairness

Average-FS and core-FS are demanding requirements, so they are often studied in a relaxed form, in which the lower bounds they impose are weakened by a multiplicative factor α ≥ 1.

• α-AFS means that, for each voter set S with a commonly approved candidate, α times the average utility of the voters in S is at least |S|/n.
• α-core means that no voter set S can find a distribution of its |S|/n budget that gives every member of S at least α times its current utility, and some member strictly more.

The case α = 1 corresponds to average-FS and to core-FS, and the guarantee becomes weaker as α grows. Every decomposable rule trivially satisfies n-AFS and n-core, since each voter is guaranteed a utility of at least 1/n.

The two approximations are related to each other: α-AFS implies α(1 + log n)-core, and α-core implies 2α-AFS; both implications are asymptotically tight. The first implication is proved through an auxiliary notion of proportional fairness, using a result of Ebadian, Kahng, Peters and Shah stating that a β-proportionally-fair distribution is also in the β-core.

Strategic properties

Several variants of strategyproofness (SP) have been studied for voting rules:

• Individual-SP means that an individual voter, who reports insincere preferences, cannot get a higher utility.
• Weak-group-SP means that a group of voters, who report insincere preferences in coordination, cannot get a higher utility for all of them.
• Group-SP means that a group of voters, who report insincere preferences in coordination, cannot get a higher utility for at least one of them, and at least as high utility for all of them.
• Preference-monotonicity means that if a voter, who previously did not support a certain candidate X, starts supporting X, then the shares of the other candidates do not increase. This implies individual-SP.
• Candidate-monotonicity (called simply monotonicity in the budget-division literature) means that if a voter starts supporting a candidate X, then the share of X itself does not decrease. It can be seen as an incentive for candidates to gather as much support as possible. Since the shares always sum to 1, preference-monotonicity implies candidate-monotonicity; the converse fails, as the majoritarian rule is candidate-monotone but not individual-SP, hence not preference-monotone.

A weaker variant of SP is excludable SP. It is relevant in situations where it is possible to exclude voters from using some candidate alternatives. For example, if the candidates are meeting times, then it is possible to exclude voters from participating in the meeting in times which they did not approve. This makes it harder to manipulate, and therefore, the requirement is weaker.

Participation properties

Rules should encourage voters to participate in the voting process. Several participation criteria have been studied:

• Weak participation: the utility of a voter when he participates is at least as high as his utility when he does not participate (this is the negation of the no show paradox).
• Strict participation: the utility of a voter when he participates is strictly higher than his utility when he does not participate. Particularly, a voter gains from participating even if he has "clones" - voters with identical preferences.

A stronger property is required in participatory budgeting settings in which the budget to distribute is donated by the voters themselves:

• Pooling participation: the utility of a voter when he donates through the mechanism is at least as high as his utility when he donates on his own.

Population consistency

Population consistency conditions require that the outcome chosen for a large election be consistent with the outcomes that would be chosen for disjoint subelections; for example, that a city-wide budget division agree with the divisions that would be selected in separate district-level elections. Two motivations are usually given for such conditions: they justify holding the election at the larger scale, since districts have no reason to insist on running their own elections, and they make outcomes easier to explain, since a candidate's share can be accounted for by the shares it obtains in the individual districts. Writing P + P′ for the profile that combines two profiles with disjoint voter sets, three conditions of increasing strength have been studied:

• Weak population consistency (WPC): if a rule chooses the same distribution for P and for P′, then it chooses that distribution for P + P′ as well. This is the standard consistency condition of social choice theory, but it is weak here, since it imposes no constraint at all when the two distributions differ even slightly.
• Strong population consistency (SPC): for every candidate x, the share of x in P + P′ is between its shares in P and in P′.
• Ranked population consistency (RPC): the bound of SPC is required only for candidates on which the two subelections "agree". Formally, order the candidates in decreasing order of their shares; the SPC bound is imposed on a candidate x whenever the two orderings, restricted to the candidates whose share is at least the share of x, coincide. Informally, one goes through the two rankings from the top and applies SPC as long as they agree.

SPC implies RPC, and RPC implies WPC. SPC is too strong to be useful: it entails a high degree of independence between the shares of different candidates, and no unanimous rule satisfies it (see below). RPC avoids this impossibility while retaining the appeal of SPC for structurally similar subelections.

A related condition was studied by Guerdjikova and Nehring for rules that return a set of distributions: if the sets chosen for two disjoint profiles intersect, then exactly the distributions in the intersection should be chosen for the combined profile. This is the set-valued counterpart of WPC. Together with a mild proportionality condition, continuity, efficiency, and independence of candidates that obtain a share of 0, it characterizes the rule that returns the set of all Nash-optimal distributions.

Rules

Utilitarian rule

The utilitarian rule aims to maximize the sum of utilities, and therefore it distributes the entire budget among the candidates approved by the largest number of voters. In particular, if there is one candidate with the largest number of votes, then this candidate gets 1 (that is, all the budget) and the others get 0, as in single-winner approval voting. If there are some k candidates with the same largest number of votes, then the budget is distributed equally among them, giving 1/k to each such candidate and 0 to all others. The utilitarian rule has several desirable properties: it is anonymous, neutral, PE, individual-SP, and preference-monotone. It is also easy to compute.

However, it is not fair towards minorities - it violates Individual-FS (as well as all stronger variants of FS). For example, if 51% of the voters approve X and 49% of the voters approve Y, then the utilitarian rule gives all the budget to X and no budget at all to Y, so the 49% who vote for Y get a utility of 0. In other words, it allows for tyranny of the majority.

The utilitarian rule is also not weak-group-SP (and hence not group-SP). For example, suppose there are 3 candidates (a,b,c) and 3 voters, each of them approves a single candidate. If they vote sincerely, then the utilitarian mixture is (1/3,1/3,1/3) so each agent's utility is 1/3. If a single voter votes insincerely (say, the first one votes for both a and b), then the mixture is (0,1,0), which is worse for the insincere voter. However, if two voters collude and vote insincerely (say, the first two voters vote for the first two outcomes), then the utilitarian mixture is (1/2, 1/2, 0), which is better for both insincere voters.

Nash-optimal rule

The Nash welfare rule maximizes the sum of logarithms of utilities. It is anonymous and neutral, and satisfies the following additional properties:

• PE;
• Group-FS (decomposability), Average-FS, Core-FS. In fact, it is the only rule known to satisfy average-FS and core-FS, that is, 1-AFS and 1-core.
• Pooling participation (and strict participation);
• No other strategyproofness property (fails even excludable-SP);
• Weak population consistency, but not ranked population consistency. That is, there are two disjoint profiles for which the rule returns distributions with the same ranking of the candidates, and the candidate with the largest share in both of them receives a strictly smaller share in the combined profile; conversely, a candidate that receives a share of 0 in both profiles may receive a large share in the combined profile.
• Not candidate-monotone: a candidate's share may decrease when an additional voter approves it.

The Nash-optimal rule can be computed by solving a convex program. However, the distribution it returns may contain irrational values, as shown by Airiau, Aziz, Caragiannis, Kruger, Lang and Peters, so in practice it can only be approximated, and it is difficult even for experts to verify by hand that a given distribution is the one selected by the rule.

An alternative, dynamic way of computing it was presented by Brandl, Brandt, Greger, Peters, Stricker and Suksompong: if the voters repeatedly update their spending so that it is proportional to the restriction of the current distribution to their approved candidates, the process converges to the Nash-optimal distribution. The same dynamics were first suggested by Cover for portfolio selection in stock markets.

There is another rule, called fair utilitarian, which satisfies similar properties (PE and group-FS) but is easier to compute (see below).

Egalitarian rule

The egalitarian (leximin) rule maximizes the smallest utility, then the next-smallest, etc. It is anonymous and neutral, and satisfies the following additional properties:

• PE;
• Individual-FS, but not unanimous-FS;
• Excludable-individual-SP, but not individual-SP;
• Weak-participation, but not strict-participation (since "clones" - voters with identical preferences - are treated as a single voter).

Other welfarist rules

For any monotonically increasing function f, one can maximize the sum of f(u_i). The utilitarian rule is a special case where f(x)=x, and the Nash rule is a special case where f(x)=log(x). Every f-maximizing rule is PE, and has the following additional properties:

• If f is any concave function of log, then it guarantees Individual-FS.
• If-and-only-if f is the log function itself, then it guarantees group-FS and unanimous-FS (this corresponds to the Nash-optimal rule).
• If-and-only-if f is a linear function, then it is individual-SP (this corresponds to the utilitarian rule).
• If-and-only-if it is the utilitarian or the egalitarian rule, it satisfies excludable-SP;
• If-and-only-if it is NOT the utilitarian nor the egalitarian rule, it satisfies strict-participation.

Priority rules

A priority rule (also called serial dictatorhip) is parametrized by a permutation of the voters, representing a priority ordering. It selects an outcome that maximizes the utility of the highest-priority agent; subject to that, maximizes the utility of the second-highest-priority agent; and so on. Every priority rule is neutral, PE, weak-group-SP, and preference-monotone. However, it is not anonymous and does not satisfy any fairness notion.

The random priority rule selects a permutation of the voters uniformly at random, and then implements the priority rule for that permutation. It is anonymous, neutral, and satisfies the following additional properties:

• Ex-post PE, but not (ex-ante) PE.
  • With the analogue of single-peaked preferences (candidates are ordered on a line and each voter approves an interval), random-priority is PE.
• Weak-group-SP.
• Group-FS.

A disadvantage of this rule is that it is computationally-hard to find the exact probabilities (see Dictatorship mechanism#Computation).

Conditional utilitarian rule

In the conditional utilitarian rule, each agent receives 1/n of the total budget. Each agent finds, among the candidates that he approves, those that are supported by the largest number of other agents, and splits his budget equally among them. It is anonymous and neutral, and satisfies the following additional properties:

• Individual-SP, and hence also candidate-monotonicity;
• Group-FS;
• Ex-post PE but not (ex-ante) PE.
  • It is more efficient than random-priority, both in theory and in simulations.
  • It always finds a distribution that is PE among the subset of group-FS distributions.
• It fails even weak population consistency: there are two profiles for which it chooses the same distribution, but a different one for their combination.
• Beyond group-FS it is not fair: it fails α-AFS and α-core for every α < n/2 − 1, so its approximation ratio to both axioms is in Θ(n).

Fair utilitarian rule

The fair utilitarian rule was introduced by Bogomolnaia, Moulin and Stong and later rediscovered by Brandl, Brandt, Peters and Stricker. It constructs weights for the voters dynamically and returns a distribution maximizing the resulting weighted utilitarian welfare. All voters start with a weight of 1. The rule identifies the candidates of maximal total weight; every voter who approves one of them splits his 1/n share equally among those he approves, and his weight is then fixed. The weights of the remaining voters increase at a common rate until some further candidate reaches the same total weight, these voters spend their shares in the same way, and the process repeats until all voters have spent their budget.

The rule is PE, group-FS, candidate-monotone, and easy to compute. Like the conditional utilitarian rule, however, it fails weak population consistency, and fails α-AFS and α-core for every α < n/3 − 1, so its approximation ratio to both axioms is in Θ(n).

Uncoordinated equal shares rule

In the uncoordinated equal shares rule, studied by Michorzewski, Peters and Skowron, every voter simply splits his 1/n share equally among all the candidates he approves, without any coordination: the share of candidate x is the sum of 1/(n·|A_i|) over all voters i who approve x. It is anonymous, neutral, decomposable (hence group-FS) and trivial to compute, and it satisfies strong population consistency as well as candidate-monotonicity. Its drawback is fairness towards groups: it fails α-AFS and α-core for every α < n/2, so its approximation ratio to both axioms is in Θ(n).

Majoritarian rule

The majoritarian rule aims to concentrate as much power as possible in the hands of few candidates, while still guaranteeing fairness. It proceeds in rounds. Initially, all candidates and voters are active. In each round, the rule selects an active candidate c who is approved by the largest set of active voters, N_c. Then, the rule "assigns" these voters N_c to c, that is, it assumes that voters in N_c voted only for c, and assigns c the fraction |N_c|/n. Then, the candidate c and the voters in N_c become inactive, and the rule proceeds to the next round. Note that the conditional-utilitarian rule is similar, except that the voters in N_c do not become inactive.

The rule has been proposed several times under different names. Speroni di Fenizio and Gewurz and Brill, Gölz, Peters, Schmidt-Kraepelin and Wilker call it majoritarian portioning and use it as an auxiliary tool, turning an approval profile into a vote count over parties to which apportionment methods are then applied.

Aziz, Lederer, Lu, Suzuki and Vollen study it in its own right under the name maximum payment rule (MP), described equivalently as follows: the budget is first divided uniformly among the voters, and in each round the candidate approved by the largest number of voters who have not yet spent their budget receives the entire budget of exactly those voters. They prove that it satisfies the following properties:

• Decomposable, and hence group-FS (it also guarantees individual-FS and single-vote-FS);
• Candidate-monotonicity;
• Ranked population consistency (it is therefore an example showing that RPC, unlike SPC, is compatible with unanimity);
• 2-AFS, and this factor is tight: the rule fails (2 − ε)-AFS for every ε > 0;
• Θ(log n)-core;
• Not PE: there are profiles in which the utility of every voter can be increased by a factor of Ω(log n). These profiles need many candidates, however: with m candidates the utility of every voter can be improved by a factor of at most ${\displaystyle \sqrt{m}/(2-2/\sqrt{m})}$, which follows from the price-of-fairness analysis of Michorzewski, Peters and Skowron. The rule can be inefficient already with three candidates.
• Not individual-SP, and hence not preference-monotone: a voter may gain by removing an approved candidate from his ballot.

Sequential payment rules

Sequential payment rules generalize the majoritarian rule. As in that rule, the budget is first divided uniformly among the voters, who then spend it on the candidates; but a voter need not spend his whole share in one shot. Each rule in the class is defined by a payment willingness function π, where π(|A_i|, t) is the amount voter i is willing to pay for the t-th of his approved candidates to be processed. Payment willingness functions must be weakly decreasing in t, and must sum to 1 over t, so that every voter spends exactly his 1/n share. Starting from the empty set of processed candidates, the rule repeatedly selects the candidate maximizing the total payment willingness of the voters who approve it (with ties broken lexicographically), assigns it the corresponding total payment, and removes it from consideration.

The majoritarian rule is the sequential payment rule with π(x,1) = 1 and π(x,y) = 0 for y > 1, and the uncoordinated equal shares rule is the one with π(x,y) = 1/x (when the payment willingness does not depend on y, the order in which candidates are processed does not matter). The class is the budget-division counterpart of sequential Thiele rules for approval-based committee elections. Within this class:

• All sequential payment rules satisfy ranked population consistency;
• All of them except the majoritarian rule and the uncoordinated equal shares rule fail candidate-monotonicity;
• The majoritarian rule is the only one that satisfies unanimity;
• None of them satisfies α-AFS for α < 3/2, so they can improve only slightly on the factor 2 of the majoritarian rule;
• This bound is attained by the 1/3-multiplicative sequential payment rule, in which the payment willingness of a voter is discounted by a factor of 1/3 whenever he pays for a candidate, that is, ${\displaystyle \pi (x,y)=3^{-y}/\sum _{i\in [x]}{3}^{-i}}$. In a finer analysis that fixes the maximal ballot size t, no sequential payment rule satisfies α-AFS for ${\displaystyle \alpha <\frac{3}{2}(1-3^{-t})}$, and the 1/3-multiplicative rule is the only rule in the class matching this bound for every t - which makes it the fairest sequential payment rule.
• The 1/3-additive rule, in which the payment willingness decreases by 1/3 with every payment, also satisfies 3/2-AFS, and it is candidate-monotone on profiles in which every voter approves at least two candidates.

Impossibility results

Some combinations of properties cannot be attained simultaneously.

• Ex-post PE and group-SP are incompatible (for ≥3 voters and ≥3 candidates).
• Anonymity, neutrality, ex-post PE and weakly-group-SP are incompatible (for ≥4 voters and ≥6 candidates).
  • If we remove one of these properties, then the remaining three can be attained.
• Ex-post PE, individual-SP and individual-outcome-FS are incompatible (for ≥3 voters and ≥3 candidates).
  • If we remove one of these properties, then the remaining two can be attained.
  • However, if we weaken individual-outcome-FS by allowing to give each agent only ε times his fair-outcome-share, for some ε>0, the impossibility remains.
• Anonymity, neutrality, PE, individual-SP and individual-FS are incompatible (for ≥5 voters and ≥17 candidates).
  • If we remove either PE or individual-SP or individual-FS, then the remaining four properties can be attained.
  • If we remove anonymity and neutrality, the impossibility still holds, but is much harder to prove.
  • In contrast, in the analogue of single-peaked preferences (candidates are ordered on a line and each voter approves an interval), all properties are attained by random-priority.
  • If we weaken individual-SP to excludable-SP, the properties are satisfied by the egalitarian rule.
  • It is open whether PE and excludable-SP are compatible with strict-participation and/or unanimous-FS.
• PE, preference-monotonicity and positive-share (a property weaker than individual-FS) are incompatible (for ≥6 voters and ≥6 candidates).
• Anonymity, neutrality, PE, individual-SP and group-FS are incompatible (for ≥5 voters and ≥4 candidates).
  • If we remove either PE or individual-SP or group-FS, then the remaining four properties can be attained.
  • If we remove anonymity and neutrality, the impossibility still holds, but is much harder to prove.
  • When there are at most 4 voters or at most 3 candidates, a simple variant of random dictatorship attains all 5 properties: a dictator is selected at random, and the most popular outcome he likes is selected. This rule is anonymous, neutral, ex-post PE, individual-SP, Group-FS, and ex-post PE; but with at most 4 voters or at most 3 candidates, ex-post PE implies PE.
• PE, individual-SP and positive-share are incompatible (for ≥6 voters and ≥4 candidates). This was proved with the help of a SAT Solver using 386 different profiles.
  • With anonymity and neutrality as additional properties, the incompatibility holds already for ≥5 voters and ≥4 candidates, and the proof is much simpler.
• Unanimity and strong population consistency are incompatible (for ≥4 voters and ≥4 candidates). This is why ranked population consistency, rather than SPC, is the strongest consistency notion that has been attained so far.
• No sequential payment rule - and in particular no rule in which each voter spends a fixed 1/n share candidate by candidate - satisfies α-AFS for α < 3/2.

Price of fairness

Michorzewsk, Peters and Skowron study the price of fairness in fractional approval voting: how much utilitarian social welfare is lost in rules that guarantee fairness, with respect to the utilitarian-optimal allocation attained by simply giving all budget to the candidate with the highest number of votes. They prove that the price is in ${\displaystyle \mathrm{\Theta }(\sqrt{m})}$ both for weak axioms such as individual fair share, and for stronger axioms such as the core. They also present a family of rules that interpolate between the utilitarian rule (which is efficient but not fair) and the Nash welfare rule (which is fair but not efficient).

Summary table

In the table below, the number in each cell represents the "strength" of the property: 0 means none (the property is not satisfied); 1 corresponds to the weak variant of the property; 2 corresponds to a stronger variant; etc.

Consistency and approximate fairness

The following table compares the rules that have been analyzed with respect to candidate-monotonicity, the population consistency conditions, and the approximation ratios to average fair share and to the core. A smaller value of α means a fairer rule, and α = 1 means that the axiom is fully satisfied.