Formal definitions
There is a finite set ''C'' of ''candidates'' (also called: ''outcomes'' or ''alternatives''), and a finite set ''N'' of ''n voters'' (also called: ''agents''). Each voter ''i'' specifies a subset ''Ai'' of ''C'', which represents the set of candidates that the voter ''approves''. A ''fractional approval voting'' rule takes as input the set of sets ''Ai'', and returns as output a ''mixture'' (also called: ''distribution'' or ''lottery'') - a vector ''p'' of real numbers in ,1 one number for each candidate, such that the sum of numbers is 1. It is assumed that each agent ''i'' gains a utility of 1 from each candidate in his approval set ''Ai'', and a utility of 0 from each candidate not in ''Ai''. Hence, agent ''i'' gains from each mixture ''p'', a utility of . For example, if the mixture ''p'' is interpreted as a budget distribution, then the utility of ''i'' is the total budget allocated to outcomes he likes.Desired properties
Basic properties
Two basic properties of voting rules in general, and fractional-approval-voting rules in particular, are: * Anonymity - the names of the voters do not matter; * Neutrality - the names of the candidates do not matter;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 toFairness 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 callde ''proportional sharing'') 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 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. * Core-FS implies Group-FS.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. 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 theRules
Utilitarian rule
TheNash-optimal rule
The Nash-optimal 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; *Pooling participation (and strict participation); * No other strategyproofness property (fails even excludable-SP); The Nash-optimal rule can be computed by solving a convex program. There is another rule, called fair utilitarian, which satisfies similar properties (PE and group-FS) but is easier to compute.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''(''ui''). 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-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. 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; * 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.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, ''Nc''. Then, the rule "assigns" these voters ''Nc'' to ''c'', that is, it assumes that voters in ''Nc'' voted ''only'' for ''c'', and assigns c the fraction '', Nc'', /n. Then, the candidate ''c'' and the voters in ''Nc'' become inactive, and the rule proceeds to the next round. Note that the conditional-utilitarian rule is similar, except that the voters in ''Nc'' do not become inactive. The majoritarian rule is anonymous, neutral, guarantees individual-FS and single-vote-FS.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 aSummary 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.See also
*References