Fractional social choice

Last updated

Fractional social choice [1] is a branch of social choice theory 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, while in fractional social choice, it is possible to choose (for example) "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. Due to this interpretation, fractional social choice is also called random social choice, [2] probabilistic social choice, [3] or stochastic social choice. [4] But it can also be interpreted as a recipe for sharing, for example:

Contents

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:

A random social choice function (RSCF) takes as input the set of voters' preference relations. It returns as output a "mixture" - a vector p of real numbers in [0,1], one number for each candidate, such that the sum of numbers is 1. This mixture can be interpreted as a random variable (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. [3] : 1 

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. [5] [6] [7]

Population consistency - if the function returns a mixture p for two disjoint sets of voters, then it returns the same p for their union. [8] [9] [10]

Independence of clones (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. [10]

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 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 stochastic ordering 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 - 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: [3]

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 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 Borda count. 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 - 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 Mxy be the difference. The resulting matrix M is called the majority margin matrix. A mixture p is called maximal iff . 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. However, while a Condorcet winner might not exist, a maximal lottery always exists. This follows from applying the Minimax theorem to an appropriate symmetric two-player zero-sum game. It satisfies PC-efficiency, DD-strategyproofness, PC-participation, and all consistency properties - particularly, Condorcet consistency.

See also

Related Research Articles

<span class="mw-page-title-main">Approval voting</span> Single-winner electoral system

Approval voting is an electoral system in which voters can select many candidates instead of selecting only one candidate.

<span class="mw-page-title-main">Condorcet method</span> Pairwise-comparison electoral system

A Condorcet method is an election method that elects the candidate who wins a majority of the vote in every head-to-head election against each of the other candidates, that is, a candidate preferred by more voters than any others, whenever there is such a candidate. A candidate with this property, the pairwise champion or beats-all winner, is formally called the Condorcet winner. The head-to-head elections need not be done separately; a voter's choice within any given pair can be determined from the ranking.

The random ballot, single stochastic vote, or lottery voting is an electoral system in which an election is decided on the basis of a single randomly selected ballot.

Strategic nomination refers to the entry of a candidate into an election with the intention of changing the ranking of other candidates. The name is an echo of ‘tactical voting’ and is intended to imply that it is the candidates rather than the voters who are seeking to manipulate the result in a manner unfaithful to voters’ true preferences.

Ranked pairs or the Tideman method is an electoral system developed in 1987 by Nicolaus Tideman that selects a single winner using votes that express preferences. The ranked-pairs procedure can also be used to create a sorted list of winners.

An electoral system satisfies the Condorcet winner criterion if it always chooses the Condorcet winner when one exists. The candidate who wins a majority of the vote in every head-to-head election against each of the other candidates – that is, a candidate preferred by more voters than any others – is the Condorcet winner, although Condorcet winners do not exist in all cases. It is sometimes simply referred to as the "Condorcet criterion", though it is very different from the "Condorcet loser criterion". Any voting method conforming to the Condorcet winner criterion is known as a Condorcet method. The Condorcet winner is the person who would win a two-candidate election against each of the other candidates in a plurality vote. For a set of candidates, the Condorcet winner is always the same regardless of the voting system in question, and can be discovered by using pairwise counting on voters' ranked preferences.

The Borda count electoral system can be combined with an instant-runoff procedure to create hybrid election methods that are called Nanson method and Baldwin method. Both methods are designed to satisfy the Condorcet criterion, and allow for incomplete ballots and equal rankings.

The Kemeny–Young method is an electoral system that uses preferential ballots and pairwise comparison counts to identify the most popular choices in an election. It is a Condorcet method because if there is a Condorcet winner, it will always be ranked as the most popular choice.

The Borda count is a family of positional voting rules which gives each candidate, for each ballot, a number of points corresponding to the number of candidates ranked lower. In the original variant, the lowest-ranked candidate gets 0 points, the next-lowest gets 1 point, etc., and the highest-ranked candidate gets n − 1 points, where n is the number of candidates. Once all votes have been counted, the option or candidate with the most points is the winner. The Borda count is intended to elect broadly acceptable options or candidates, rather than those preferred by a majority, and so is often described as a consensus-based voting system rather than a majoritarian one.

In social choice theory, a dictatorship mechanism is a rule by which, among all possible alternatives, the results of voting mirror a single pre-determined person's preferences, without consideration of the other voters. Dictatorship by itself is not considered a good mechanism in practice, but it is theoretically important: by Arrow's impossibility theorem, when there are at least three alternatives, dictatorship is the only ranked voting electoral system that satisfies unrestricted domain, Pareto efficiency, and independence of irrelevant alternatives. Similarly, by Gibbard's theorem, when there are at least three alternatives, dictatorship is the only strategyproof rule.

<span class="mw-page-title-main">Ranked voting</span> Family of electoral systems

The term ranked voting, also known as preferential voting or ranked choice voting, pertains to any voting system where voters use a rank to order candidates or options—in a sequence from first, second, third, and onwards—on their ballots. Ranked voting systems vary based on the ballot marking process, how preferences are tabulated and counted, the number of seats available for election, and whether voters are allowed to rank candidates equally. An electoral system that utilizes ranked voting employs one of numerous counting methods to determine the winning candidate or candidates. Additionally, in some ranked voting systems, officials mandate voters to rank a specific number of candidates, sometimes all; while in others, voters may rank as many candidates as they desire.

Maximal lotteries refers to a probabilistic voting system first considered by the French mathematician and social scientist Germain Kreweras in 1965. The method uses preferential ballots and returns so-called maximal lotteries, i.e., probability distributions over the alternatives that are weakly preferred to any other probability distribution. Maximal lotteries satisfy the Condorcet criterion, the Smith criterion, polynomial runtime, and probabilistic versions of reinforcement, participation, and independence of clones.

Fair random assignment is a kind of a fair division problem.

Random priority (RP), also called Random serial dictatorship (RSD), is a procedure for fair random assignment - dividing indivisible items fairly among people.

A simultaneous eating algorithm(SE) is an algorithm for allocating divisible objects among agents with ordinal preferences. "Ordinal preferences" means that each agent can rank the items from best to worst, but cannot (or does not want to) specify a numeric value for each item. The SE allocation satisfies SD-efficiency - a weak ordinal variant of Pareto-efficiency (it means that the allocation is Pareto-efficient for at least one vector of additive utility functions consistent with the agents' item rankings).

Comparison of electoral systems is the result of comparative politics for electoral systems. Electoral systems are the rules for conducting elections, a main component of which is the algorithm for determining the winner from the ballots cast. This article discusses methods and results of comparing different electoral systems, both those that elect a unique candidate in a 'single-winner' election and those that elect a group of representatives in a multiwinner election.

In the fields of mechanism design and social choice theory, Gibbard's theorem is a result proven by philosopher Allan Gibbard in 1973. It states that for any deterministic process of collective decision, at least one of the following three properties must hold:

  1. The process is dictatorial, i.e. there exists a distinguished agent who can impose the outcome;
  2. The process limits the possible outcomes to two options only;
  3. The process is open to strategic voting: once an agent has identified their preferences, it is possible that they have no action at their disposal that best defends these preferences irrespective of the other agents' actions.

Fractional approval voting is an electoral system using approval ballots, 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 and the other candidates lose. The fractions pj can be interpreted in various ways, depending on the setting. Examples are:

Lexicographic dominance is a total order between random variables. It is a form of stochastic ordering. It is defined as follows. Random variable A has lexicographic dominance over random variable B if one of the following holds:

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 problem is how to aggregate the different opinions into a single budget-distribution program.

References

  1. ↑ Aziz, Haris (2015-03-28). "Condorcet's Paradox and the Median Voter Theorem for Randomized Social Choice". Economics Bulletin. 35 (1): 745–749. ISSN   1545-2921.
  2. ↑ Chatterji, Shurojit; Zeng, Huaxia (2018-05-01). "On random social choice functions with the tops-only property". Games and Economic Behavior. 109: 413–435. doi:10.1016/j.geb.2017.11.011. ISSN   0899-8256. S2CID   49677879.
  3. 1 2 3 Felix Brandt (2017-10-26). "Roling the Dice: Recent Results in Probabilistic Social Choice". In Endriss, Ulle (ed.). Trends in Computational Social Choice. Lulu.com. ISBN   978-1-326-91209-3.
  4. ↑ Pattanaik, Prasanta K.; Peleg, Bezalel (1986). "Distribution of Power under Stochastic Social Choice Rules". Econometrica. 54 (4): 909–921. doi:10.2307/1912843. ISSN   0012-9682. JSTOR   1912843.
  5. ↑ Sen, Amartya K. (1971). "Choice Functions and Revealed Preference". The Review of Economic Studies. 38 (3): 307–317. doi:10.2307/2296384. ISSN   0034-6527. JSTOR   2296384.
  6. ↑ Sen, Amartya (1977). "Social Choice Theory: A Re-Examination". Econometrica. 45 (1): 53–89. doi:10.2307/1913287. ISSN   0012-9682. JSTOR   1913287.
  7. ↑ Sen, Amartya (1986-01-01). "Chapter 22 Social choice theory". Handbook of Mathematical Economics. 3: 1073–1181. doi:10.1016/S1573-4382(86)03004-7. ISBN   9780444861283. ISSN   1573-4382.
  8. ↑ Smith, John H. (1973). "Aggregation of Preferences with Variable Electorate". Econometrica. 41 (6): 1027–1041. doi:10.2307/1914033. ISSN   0012-9682. JSTOR   1914033.
  9. ↑ Young, H.P (1974-09-01). "An axiomatization of Borda's rule". Journal of Economic Theory. 9 (1): 43–52. doi:10.1016/0022-0531(74)90073-8. ISSN   0022-0531.
  10. 1 2 Fine, B.; Fine, K. (1974). "Social Choice and Individual Ranking I". The Review of Economic Studies. 41 (3): 303–322. doi:10.2307/2296751. ISSN   0034-6527. JSTOR   2296751.
  11. ↑ Aziz, Haris (2016-11-08). "Participation Incentives in Randomized Social Choice". arXiv: 1602.02174 [cs.GT].
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.