Fractional approval voting

In fractional social choice, fractional approval voting refers to a class of electoral systems using approval ballots, in which the outcome is fractional: for each alternative j there is a fraction p_j between 0 and 1, such that the sum of p_j is 1. It can be seen as a generalization of approval voting: in the latter, one candidate wins and the other candidates lose. The fractions p_j can be interpreted in various ways, depending on the setting. Examples are:

Time sharing: each alternative j is implemented a fraction p_j of the time.
Budget ''distribution: each alternative j'' receives a fraction p_j of the total budget.
Probabilities: after the fractional results are computed, there is a lottery for selecting a single candidate, where each candidate j is elected with probability p_j.
Entitlements: the fractional results are used as entitlements 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.

Formal definitions

There is a finite set C of candidates, and a finite set N of n voters. Each voter i specifies a subset A_i of C, which represents the set of candidates that the voter approves.
A fractional approval voting rule takes as input the set of sets A_i, and returns as output a mixture - a vector p of real numbers in , 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 A_i, and a utility of 0 from each candidate not in A_i. 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 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. For example, suppose there are 5 candidates and 6 voters with approval sets. 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.
Fairness properties

Fairness requirements are captured by variants of the notion of fair share .
Individual-FS 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 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 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 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.
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.
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 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. 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. For example, suppose there are 3 candidates and 3 voters, each of them approves a single candidate. If they vote sincerely, then the utilitarian mixture is so each agent's utility is 1/3. If a single voter votes insincerely, then the mixture is, which is worse for the insincere voter. However, if two voters collude and vote insincerely, then the utilitarian mixture is, which is better for both insincere voters.

Nash-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, Average-FS, Core-FS;
Pooling participation ;
No other strategyproofness property ;

The Nash-optimal rule can be computed by solving a convex program. There is another rule, called fair utilitarian, which satisfies similar properties but is easier to compute.''''''

Egalitarian rule

The egalitarian 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.