This articlemay be too technical for most readers to understand. Pleasehelp improve it tomake it understandable to non-experts, without removing the technical details.(February 2024) (Learn how and when to remove this message)

A jointPolitics andEconomics series
Social choice andelectoral systems
Social choice Mechanism design Comparative politics Comparison List (By country)
Single-winner methods Single vote –plurality methods First preference plurality (FPP) Two-round (US:Jungle primary) Partisan primary Instant-runoff UK: Alternative vote (AV) US: Ranked-choice (RCV) Party block voting Plurality block voting Condorcet methods Condorcet-IRV Round-robin voting Minimax Kemeny Schulze Ranked pairs Maximal lottery Positional voting Plurality (el.IRV) Borda count (el.Baldwin,Mdn.Bucklin) Antiplurality (el.Coombs) Cardinal voting Score voting Approval voting Majority judgment STAR voting
Proportional representation Party-list Apportionment Highest averages Largest remainders National remnant Biproportional List type Closed list Open list Panachage List-free PR Localized list Quota-remainder methods Single transferable vote (Hare,Droop) Schulze STV CPO-STV Quota Borda Approval-based committees Thiele's method Phragmen's method Expanding approvals rule Method of equal shares Fractional social choice Direct representation Interactive representation Liquid democracy Fractional approval voting Maximal lottery Random ballot Semi-proportional representation Cumulative SNTV Limited voting
Mixed systems By results of combination Mixed-member majoritarian Mixed-member proportional By mechanism of combination Non-compensatory Parallel (superposition) Coexistence Conditional Fusion (majority bonus) Compensatory Seat linkage system UK:'AMS' NZ:'MMP' Vote linkage system Negative vote transfer Mixed ballot Supermixed systems Dual-member proportional Rural–urban proportional Majority jackpot By ballot type Single vote Double simultaneous vote Dual-vote
Paradoxes and pathologies Spoiler effects Spoiler effect Cloning paradox Frustrated majorities paradox Center squeeze Pathological response Perverse response Best-is-worst paradox No-show paradox Multiple districts paradox Strategic voting Lesser evil voting Exaggeration Truncation Turkey-raising Wasted vote Paradoxes ofmajority rule Tyranny of the majority Discursive dilemma Conflicting majorities paradox
Social and collective choice Impossibility theorems Arrow's theorem Majority impossibility Moulin's impossibility theorem McKelvey–Schofield chaos theorem Gibbard's theorem Positive results Median voter theorem Condorcet's jury theorem May's theorem Condorcet dominance theorems Harsanyi's utilitarian theorem VCG mechanism Quadratic voting
Politics portal Economics portal Mathematics portal
v t e

Infractional social choice,fractional approval voting refers to a class ofelectoral systems usingapproval ballots (each voter selects one or more candidate alternatives), in which the outcome isfractional: for each alternativej there is a fractionp_j between 0 and 1, such that the sum ofp_j is 1. It can be seen as a generalization ofapproval voting: in the latter, one candidate wins (p_j = 1) and the other candidates lose (p_j = 0). The fractionsp_j can be interpreted in various ways, depending on the setting. Examples are:

• Time sharing: each alternativej is implemented a fractionp_j of the time (e.g. each candidatej serves in office a fractionp_j of the term).^[1]
• Budgetdistribution: each alternativej receives a fractionp_j of the total budget.^[2]
• Probabilities: after the fractional results are computed, there is a lottery for selecting a single candidate, where each candidatej is elected with probabilityp_j.^[1]
• Entitlements: the fractional results are used as entitlements (also calledweights) in rules ofapportionment,^[3] or in algorithms offair division with different entitlements.

Fractional approval voting is a special case offractional social choice in which all voters havedichotomous preferences. It appears in the literature under many different terms: lottery,^[1] sharing,^[4] portioning,^[3] mixing^[5] and distribution.^[2]

There is a finite setC ofcandidates (also called:outcomes oralternatives), and a finite setN ofn voters (also called:agents). Each voteri specifies a subsetA_i ofC, which represents the set of candidates that the voterapproves.

Afractional approval voting rule takes as input the set of setsA_i, and returns as output amixture (also called:distribution orlottery) - a vectorp of real numbers in [0,1], one number for each candidate, such that the sum of numbers is 1.

It is assumed that each agenti gains a utility of 1 from each candidate in his approval setA_i, and a utility of 0 from each candidate not inA_i. Hence, agenti gains from each mixturep, a utility of${\displaystyle \sum _{j\in A_i}{p}_j}$. For example, if the mixturep is interpreted as a budget distribution, then the utility ofi is the total budget allocated to outcomes he likes.

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.^{[4]: Lem.1, 2}
• When the candidates can be ordered on a line such that each approval set is an interval (analogously tosingle peaked preferences).^{[5]: Lemma 1}

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

Individual-FS^[5] (also calledFair Welfare Share^[1]) means that the utility of each voteri is at least 1/n, that is, at least 1/n of the budget is allocated to candidates approved byi.

Individual-Outcome-FS^[1] means that the utility of each voteri is at least his utility in a lottery that selects a candidate randomly, that is, at leastk/|C|, wherek is the number of candidates approved byi.

• 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 calledfaithful^[3]) means that, if each voter approves a single candidate, then the fraction assigned to each candidatej equals the number of voters who approvej divided byn.

• 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^[5] means that, for each setS of voters withidentical preferences, the utility of each member inS 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^{[1]: 2002draft} (also calledproportional sharing^[4]) means that, for each voter setS, the total budget allocated to candidates approved byat least one member ofS, is at least |S|/n.

• Group-FS implies unanimous-FS, single-vote-FS and individual-FS.
• Group-FS is equivalent to a property calleddecomposability:^[2] it is possible to decompose the distribution ton distributions of sum 1/n, such that the distribution recommended to agenti is positive only on candidates approved byi.

Average-FS^[5] means that, for each voter setS with at least one approved candidate in common, the average utility of voters inS is at least |S|/n.

Core-FS means that, for each voter setS, there is no other distribution of their |S|/n budget, which gives all members ofS a higher utility.

• Core-FS implies Group-FS.

Several variants ofstrategyproofness (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.

A weaker variant of SP isexcludable 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.^[5]

Rules should encourage voters to participate in the voting process. Severalparticipation 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 theno show paradox).
• Strict participation:^[5] 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 inparticipatory budgeting settings in which the budget to distribute is donated by the voters themselves:

• Pooling participation:^[6] 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.

Theutilitarian 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-winnerapproval voting. If there are somek 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:^{[1]: Prop.1} 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 fortyranny 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 asingle 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, iftwo 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 isbetter for both insincere voters.

TheNash-optimal rule maximizes the sum oflogarithms of utilities. It is anonymous and neutral, and satisfies the following additional properties:

• PE;
• Group-FS (decomposability), Average-FS, Core-FS;^[5][7]
• Pooling participation (and strict participation);^[6]
• No other strategyproofness property (fails even excludable-SP);

The Nash-optimal rule can be computed by solving aconvex program. There is another rule, calledfair utilitarian, which satisfies similar properties (PE and group-FS) but is easier to compute.^{[1]: Thm.3 in 2002 draft}

Theegalitarian (leximin) rule maximizes the smallest utility, then the next-smallest, etc. It is anonymous and neutral, and satisfies the following additional properties:^[5]

• 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).

For any monotonically increasing functionf, one can maximize the sum off(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). Everyf-maximizing rule is PE, and has the following additional properties:^{[1]: Prop.5, 6, 7}

• Iff is anyconcave 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.

Apriority rule (also calledserial dictatorhip) is parametrized by apermutation 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-priorty 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.

Therandom priority rule selects apermutation 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:^{[1]: Prop.5}

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

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

In theconditional utilitarian rule,^[5] 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;
• 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.^[2]

Themajoritarian rule^[8] 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 candidatec who is approved by the largest set of active voters,N_c. Then, the rule "assigns" these votersN_c toc, that is, it assumes that voters inN_c votedonly forc, and assigns c the fraction|N_c|/n. Then, the candidatec and the voters inN_c become inactive, and the rule proceeds to the next round. Note that the conditional-utilitarian rule is similar, except that the voters inN_c do not become inactive.

The majoritarian rule is anonymous, neutral, guarantees individual-FS and single-vote-FS.^{[clarification needed]}

Some combinations of properties cannot be attained simultaneously.

• Ex-post PE and group-SP are incompatible (for ≥3 voters and ≥3 candidates).^{[1]: Prop.2}
• Anonymity, neutrality, ex-post PE and weakly-group-SP are incompatible (for ≥4 voters and ≥6 candidates).^{[1]: Prop.3}
  • 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).^{[1]: Prop.4}
  • 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).^{[1]: Prop.6}
  • 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.^[2]
  • In contrast, in the analogue ofsingle-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.^[5]
• PE, preference-monotonicity and positive-share (a property weaker than individual-FS) are incompatible (for ≥6 voters and ≥6 candidates).^{[1]: Prop.7}
• Anonymity, neutrality, PE, individual-SP and group-FS are incompatible (for ≥5 voters and ≥4 candidates).^[4]
  • 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.^[2]
  • 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 aSAT Solver using 386 different profiles.^[2]
  • With anonymity and neutrality as additional properties, the incompatibility holds already for ≥5 voters and ≥4 candidates, and the proof is much simpler.

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.

• Justified representation - a property similar to fair-share, but for discrete outcomes.
• Party-approval voting - the candidates are parties, and the fraction allocated to each party corresponds to the fraction of seats it should get in the parliament.
• Participatory budgeting algorithms - other approaches for distributing a budget fairly.
• Some authors studied theprice of fairness of various distribution rules.^[9][10]
• The distribution problem has been studied also in the more challenging setting in which agents haveadditive utilities.^[11]

• Social choice theory
• Approval voting

• Wikipedia articles that are too technical from February 2024
• All articles that are too technical
• Wikipedia articles needing clarification from August 2021