Fractional, stochastic, or weighted social choice is a branch of

social choice theory Social choice theory is a branch of welfare economics that extends the Decision theory, theory of rational choice to collective decision-making. Social choice studies the behavior of different mathematical procedures (social welfare function, soc ...

in which the collective decision is not a single alternative, but rather a weighted sum of two or more alternatives. For example, if society has to choose between three candidates (A, B, or C), then in standard social choice exactly one of these candidates is chosen. By contrast, in fractional social choice it is possible to choose any

linear combination In mathematics, a linear combination or superposition is an Expression (mathematics), expression constructed from a Set (mathematics), set of terms by multiplying each term by a constant and adding the results (e.g. a linear combination of ''x'' a ...

of these, e.g. "2/3 of A and 1/3 of B". A common interpretation of the weighted sum is as a lottery, in which candidate A is chosen with probability 2/3 and candidate B is chosen with probability 1/3. The rule can also be interpreted as a recipe for sharing, for example: * Time-sharing: candidate A is (deterministically) chosen for 2/3 of the time while candidate B is chosen for 1/3 of the time. * Budget-distribution: candidate A receives 2/3 of the budget while candidate B receives 1/3 of the budget. * Fair division with different entitlements can also be used to divide a heterogeneous resource between candidates A and B, with their entitlements being 2/3 and 1/3.

Formal definitions

There is a finite set of ''alternatives'' (also called: ''candidates''), and a finite set of ''voters'' (also called: ''agents''). Voters may have different preferences over the alternatives. The agents' preferences can be expressed in several ways: *

Dichotomous preferences In economics, dichotomous preferences (DP) are preference relations that divide the set of alternatives to two subsets, "Good" and "Bad". From ordinal utility perspective, DP means that for every two alternatives X,Y: : X \preceq Y \iff X \in Ba ...

- each voter has a set of "approved candidates" who are all equivalent in his eyes. ''This model is elaborated in the page on

fractional approval voting 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'' th ...

.'' * Preference relations - each voter has a ranking of the candidates. The relation can be ''strict'' or ''weak''. ''Strict'' means that there are no "ties" - the agent always prefers one candidate or another. ''Weak'' means that there may be ties - the agent might be indifferent between two or more candidates. * Ideal distributions - each voter has in mind an ideal distribution of the probability/time/budget among the candidates. ''This model is elaborated in the page on

Budget-proposal aggregation Budget-proposal aggregation (BPA) is a problem in social choice theory. A group has to decide on how to distribute its budget among several issues. Each group-member has a different idea about what the ideal budget-distribution should be. The probl ...

.'' A ''random social choice function'' (RSCF) takes as input the set of voters' preference relations. It returns as output a "

mixture In chemistry, a mixture is a material made up of two or more different chemical substances which can be separated by physical method. It is an impure substance made up of 2 or more elements or compounds mechanically mixed together in any proporti ...

" - a vector ''p'' of real numbers in ,1 one number for each candidate, such that the sum of numbers is 1. This mixture can be interpreted as a

random variable A random variable (also called random quantity, aleatory variable, or stochastic variable) is a Mathematics, mathematical formalization of a quantity or object which depends on randomness, random events. The term 'random variable' in its mathema ...

(a lottery), whose value equals each candidate ''x'' with probability ''p''(''x''). It can also be interpreted as a deterministic assignment of a fractional share to each candidate. Since the voters express preferences over single candidates only, in order to evaluate RSCFs one needs to "lift" these preferences to preferences over mixtures. This lifting process is often called a ''lottery extension'', and it results in one of several stochastic orderings.

Properties

Basic properties

Two basic desired properties of RSCFs are anonymity - the names of the voters do not matter, and neutrality - the names of the outcomes do not matter. Anonymity and neutrality cannot always be satisfied by a deterministic social choice function. For example, if there are two voters and two alternatives A and B, and each voter wants a different alternative, then the only anonymous and neutral mixture is 1/2*A+1/2*B. Therefore, the use of mixtures is essential to guarantee the basic fairness properties.

Consistency properties

The following properties involve changes in the set of voters or the set of alternatives. Condorcet consistency - if there exists a Condorcet winner, then the function returns a degenerate mixture in which this winner gets 1 and the other alternatives get 0 (that is, the Condorcet winner is chosen with probability 1). Agenda consistency - let ''p'' be a mixture, and let A,B be sets of alternatives that contain the support of ''p''. Then, the function returns ''p'' for A union B, iff it returns ''p'' for A and for B. This property was called expansion/contraction by Sen. Population consistency - if the function returns a mixture ''p'' for two disjoint sets of voters, then it returns the same ''p'' for their union.

Independence of clones In social choice theory, the independence of (irrelevant) clones criterion says that adding a ''clone'', i.e. a new candidate very similar to an already-existing candidate, should not spoil the results. It can be considered a weak form of the in ...

(also called cloning consistency) - if an alternative is "cloned", such that all voters rank all its clones one near the other, then the weight (=probability) of all the other alternatives in the returned mixture is not affected. * A stronger variant of it is composition consistency - it also requires that, in each component, the weight of each alternative is proportional to its weight when the component is considered in isolation. These properties guarantee that a central planner cannot perform simple manipulations such as splitting alternatives, cloning alternatives, or splitting the population. Note that consistency properties depend only on the rankings of individual alternatives - they do not require ranking of mixtures.

Mixture-comparison properties

The following properties involve comparisons of mixtures. To define them exactly, one needs an assumption on how voters rank mixtures. This requires a

stochastic ordering In probability theory and statistics, a stochastic order quantifies the concept of one random variable being "bigger" than another. These are usually partial orders, so that one random variable A may be neither stochastically greater than, less t ...

on the lotteries. Several such orderings exist; the most common in social choice theory, in order of strength, are DD (deterministic dominance), BD (bilinear dominance), SD (stochastic dominance) and PC (pairwise-comparison dominance). See

for definitions and examples. Efficiency - no mixture is better for at least one voter and at least as good for all voters. One can define DD-efficiency, BD-efficiency, SD-efficiency, PC-efficiency, and ex-post efficiency (the final outcome is always efficient).

Strategyproofness In mechanism design, a strategyproof (SP) mechanism is a game form in which each player has a weakly- dominant strategy, so that no player can gain by "spying" over the other players to know what they are going to play. When the players have privat ...

- reporting false preferences does not lead to a mixture that is better for the voter. Again, one can define DD-strategyproofness, BD-strategyproofness, SD-strategyproofness and PC-strategyproofness. Participation - abstaining from participation does not lead to a mixture that is better for the voter. Again, one can define DD-participation, BD-participation, SD-participation and PC-participation.

Common functions

Some commonly used rules for random social choice are: Random dictatorship - a voter is selected at random, and determines the outcome. If the preferences are strict, this yields a mixture in which the weight of each alternative is exactly proportional to the number of voters who rank it first. If the preferences are weak, and the chosen voter is indifferent between two or more best options, then a second voter is selected at random to choose among them, and so on. This extension is called random serial dictatorship. It satisfies ex-post efficiency, strong SD-strategyproofness, very-strong-SD-participation, agenda-consistency, and cloning-consistency. It fails Condorcet consistency, composition consistency, and (with weak preferences) population consistency. Max Borda - returns a mixture in which all alternatives with the highest

Borda count The Borda method or order of merit is a positional voting rule that gives each candidate a number of points equal to the number of candidates ranked below them: the lowest-ranked candidate gets 0 points, the second-lowest gets 1 point, and so on ...

have an equal weight, and all other alternatives have a weight of 0. In other words, it picks randomly one of the Borde winners (other score functions can be used instead of Borda). It satisfies SD-efficiency, strong-SD participation, and population-consistency, but does not satisfy any form of strategyproofness, or any other consistency. Proportional Borda - returns a mixture in which the weight of each alternative is proportional to its

. In other words, it randomizes between ''all'' alternatives, where the probability of each alternative is proportional to its score (other score functions can be used instead of Borda). It satisfies strong SD-strategyproofness, strong SD-participation, and population consistency, but not any form of efficiency, or any other consistency.

Maximal lotteries Maximal lotteries are a probabilistic voting rule that use ranked ballots and returns a lottery over candidates that a majority of voters will prefer, on average, to any other.P. C. Fishburn. ''Probabilistic social choice based on simple voting ...

- a rule based on pairwise comparisons of alternatives. For any two alternatives ''x,y'', we compute how many voters prefer ''x'' to y, and how many voters prefer ''y'' to ''x'', and let ''M_xy'' be the difference. The resulting matrix ''M'' is called the ''majority margin matrix''. A mixture ''p'' is called ''maximal'' iff

p^T M \geq 0

. When interpreted as a lottery, it means that ''p'' is weakly preferred to any other lottery by an expected majority of voters (the expected number of agents who prefer the alternative returned by ''p'' to that returned by any other lottery ''q'', is at least as large as the expected number of agents who prefer the alternative returned by ''q'' to that returned by ''p''). A maximal lottery is the continuous analogue of a

Condorcet winner A Condorcet winner (, ) is a candidate who would receive the support of more than half of the electorate in a one-on-one race against any one of their opponents. Voting systems where a majority winner will always win are said to satisfy the Condo ...

. However, while a Condorcet winner might not exist, a maximal lottery always exists. This follows from applying the

Minimax theorem In the mathematical area of game theory and of convex optimization, a minimax theorem is a theorem that claims that : \max_ \min_ f(x,y) = \min_ \max_f(x,y) under certain conditions on the sets X and Y and on the function f. It is always true that ...

to an appropriate symmetric two-player

zero-sum game Zero-sum game is a Mathematical model, mathematical representation in game theory and economic theory of a situation that involves two competition, competing entities, where the result is an advantage for one side and an equivalent loss for the o ...

. It satisfies PC-efficiency, DD-strategyproofness, PC-participation, and all consistency properties - particularly, Condorcet consistency.

References

Social choice theory