In fractional social choice, fractional approval voting refers to a class of electoral systems using approval ballots (each voter selects one or more candidate alternatives), in which the outcome is fractional: for each alternative j there is a fraction pj between 0 and 1, such that the sum of pj is 1. It can be seen as a generalization of approval voting: in the latter, one candidate wins (pj = 1) and the other candidates lose (pj = 0). The fractions pj can be interpreted in various ways, depending on the setting. Examples are:
Time sharing: each alternative j is implemented a fraction pj of the time (e.g. each candidate j serves in office a fraction pj of the term). Budget distribution: each alternative j receives a fraction pj of the total budget.. A video of the EC'21 conference talk Probabilities: after the fractional results are computed, there is a lottery for selecting a single candidate, where each candidate j is elected with probability pj. Entitlements: the fractional results are used as entitlements (also called weights) in rules of apportionment, or in algorithms of fair division with different entitlements.
Fractional approval voting is a special case of fractional social choice in which all voters have dichotomous preferences. It appears in the literature under many different terms: lottery, sharing, portioning, mixing and distribution. The rules of this class are also called distribution rules.
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 [0,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 the candidates 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
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.