Social choice

Social choice theory concerns the design and analysis of procedures that aggregate expressed preferences of $n \geq 2$ voters (electors, legislators, committee members, jurors) for the purpose of making decisions that affect the well-being of a group they represent. Voting procedures for decisions between two alternatives focus on simple majority and various special majority and weighted majority rules. Important milestones for choices among three or more alternatives include Borda's 1781 method of ranked voting [a3], Condorcet's 1785 defense of majority choice [a6], Hare's method of proportional representation by preferential voting in 1861 [a13], and Arrow's startling discovery around 1950 of the collective inconsistency of a few desirable restrictions on social choice rules [a1] (cf. also Voting paradoxes). Arrow's celebrated "impossibility theorem" (cf. also Arrow impossibility theorem) set off an avalanche of research, which continues unabated. Prominent areas of mathematics involved in social choice theory include axiomatic analysis, set theory, combinatorics and graph theory, linear algebra, topology, and probability theory.

A central concept of the subject is a social choice function $F : \mathcal{X} \times D \rightarrow 2 ^ { X } \backslash \{ \emptyset \}$, in which $X$ is a set of alternatives, $\mathcal{X}$ is a non-empty set of non-empty subsets of $X$, $D$ is a non-empty set of voter response profiles, and $2 ^ { X }$ is the power set of $X$. One requires $F ( A , d ) \subseteq A$ when $A \in \mathcal{X}$ is the set of feasible alternatives and $d$ is the voter response profile, and interprets $F ( A , d )$ as the set of best feasible alternatives at $( A , d )$ according to $F$. When $F ( A , d )$ is always a singleton in $A$, $F$ is decisive. Then $\{ F ( A , d ) : A \in \mathcal X \}$ is a system of representatives for every $d \in D$ (cf. System of common representatives; System of different representatives).

For the two-alternative case of $X = \{ a , b \}$ and $\mathcal{X} = \{ X \}$, let $D = \{ 1,0 , - 1 \} ^ { n }$ with $d _ { i } = 1,0 , - 1$ in $d = ( d _ { 1 } , \dots , d _ { n } )$ according to whether voter $i$ votes for $a$, abstains, and votes for $b$, respectively. Then $F$ can be described by the ternary system $f : D \rightarrow \mathbf{R}$, where $f ( d ) > 0$ means that $a$ wins, $f ( d ) = 0$ means that $a$ and $b$ tie, or that $a$ wins when $F$ is decisive, and $f ( d ) < 0$ means that $b$ wins. The simple majority rule, which was axiomatized by K.O. May [a15] with conditions of strong monotonicity, duality and anonymity, has $f ( d ) = \sum d _ { i }$. More generally, $f$ is a weighted majority rule if there is a weight $w _ { i } \geq 0$ for voter $i$, $i = 1 , \dots , n$, and $f ( d ) = \sum w _ { i } d _ { i }$ for all $d \in D$. The $2 / 3$-majority rule for $a$'s passage takes $f ( d ) = 3 | \{ i : d _ { i } = 1 \} | - 2 n$. A study of nested hierarchies of aggregation, in which vote outcomes at lower levels become votes at higher levels, was initiated by Y. Murakami [a17]. A general discussion of two-alternative rules is included in [a8].

Discussions of elections involving three or more candidates or alternatives commonly assume that voter $i$ has a preference weak order $\succsim_{i}$ on $X$ that is transitive ($x \underset{ \sim i }{\succ} y$ and $y \underset{ \sim}{\succ}_{i} z$ imply $x \succsim_{i} z$; cf. also Transitivity) and complete ($x \underset{ \sim i }{\succ} y$ or $y \succsim _{i} x $, for all $x , y \in X$) with asymmetric part $\succ_{i}$ for strict preference and symmetric part $\sim_i$ for indifference. An $n$-tuple $v = ( \succsim _ { 1 } , \dots , \succsim _ { n } )$ is a voter preference profile, and $V$ denotes a feasible set of voter preference profiles that might occur. It is often assumed that $x \sim_{ i} y \Leftrightarrow x = y$, in which case every $\succsim_{i}$ is a linear order (cf. also Order (on a set)) and every $\succ_{i}$ is a strict best-to-worst ranking of $X$. When voters are asked to preferentially order the alternatives, $D$ may be the same as $V$. But $D$ may be different from $V$, as in plurality voting when each voter is to vote for exactly one alternative.

Social choice functions for multiple-alternative elections depend on the number $k$ of candidates to be elected, or the number of issues or motions to be decided. When one person is to be elected or one budget is to be adopted, $k = 1$. Larger values of $k$ arise when a committee is to be elected or when several seats on a board or in a legislature are to be filled. Given $k$, one requires $| A | \geq k$ for each $A \in \mathcal{X}$, and $| F ( A , d ) | \geq k$ (or $= { k }$ for decisiveness) for all $( A , d )$.

Another distinguishing feature is the type of voter input presumed for $d \in D$. Non-ranked voting procedures ask voters to vote for (or perhaps against) one or more alternatives without ranking their choices. The most common non-ranked procedures for $k = 1$ are the plurality rule (vote for one; candidate with most votes is elected) and plurality with a runoff, in which a simple majority vote is held between the top two candidates from the initial plurality ballot. Another procedure, called approval voting [a5], [a16], allows voters to vote for any number of candidates: the winner is the candidate with the most votes. Popular non-ranked procedures for $k \geq 2$ ask voters to vote for exactly $k$, or no more than $k$ candidates. The winners are the $k$ people with the most votes.

A point-distribution procedure known as cumulative voting [a4] is sometimes used to elect $k$ people to a corporate board or other body. Each voter has complete freedom to distribute a fixed number of points or votes over the candidates, and the $k$ with the most points are elected.

Ranked voting procedures ask voters to rank order some or all of the alternatives, without specific point assignments, as their inputs to $d$. When there are $m$ alternatives and each $d_{i}$ in $d$ is a linear order, the positional scoring rule $s = ( s _ { 1 } , \ldots , s _ { m } )$ with $s _ { 1 } \geq \ldots \geq s _ { m } \geq 0$ computes the score of candidate $x$ as $\sum s _ { j } x _ { j }$, where $x _ { j }$ is the number of voters who rank $x$ in $j$th place [a21]. The Borda method (cf. also Arrow impossibility theorem), which is the most common and perhaps most satisfactory positional scoring procedure [a19], uses $s = ( m - 1 , m - 2 , \dots , 1,0 )$. Another class of ranked procedures are referred to as Condorcet social choice functions [a9] because they require election of a Condorcet candidate (one who would beat or tie every other candidate by simple majority pairwise comparisons based on $d$) whenever such a candidate exists. The simplest example of no Condorcet candidate is $d = ( a b c , c a b , b c a )$, where $a$ has a $2$-to-$1$ majority over $b$, and similarly for $b$ over $c$, and $c$ over $a$. The cyclical-majorities phenomenon is reviewed in detail in [a11]. A third class of ranked procedures, which is used extensively for parliamentary elections, involves election quotas and vote transferals. Such systems, initiated by T. Hare [a13] and others, are often returned to as Hare systems and methods of single transferable vote. They were designed in part to ensure representation of significant minorities.

Arrow's impossibility theorem, which is based on ranked voting with three or more candidates, is the most important advance in social choice theory in the 20th century. Its essential idea is that aggregation problems that arise from cyclical majorities cannot be avoided by any reasonable generalization of majority comparisons. The proof of his theorem exploits interrelationships among preference profiles for fixed $n$ and $m > 3$ to conclude that a few basic conditions on $F$ are collectively incompatible. This conclusion can be avoided when admissible profiles are restricted [a1], [a2], [a8], but the impact of his theorem has been profound.

Variations on Arrow's theme have led to a few dozen related impossibility theorems [a10], [a14], including results by A. Gibbard [a12] and M.A. Satterthwaite [a20] which say that every method for electing one of $m > 3$ candidates which satisfies a few elementary restrictions is manipulable. This means that there will be voter preference profiles at which some voter, by falsifying his or her true preferences for submission to the response profile $d$, can help elect a candidate strictly preferred to the one that would have been elected under the "true" profile. Further discussions of voter strategy are included in [a4], [a5], [a7], [a18], [a19].

References

[a1]	K.J. Arrow, "Social choice and individual values" , Wiley (1963) (Edition: Second)
[a2]	D. Black, "The theory of committees and elections" , Cambridge Univ. Press (1958)
[a3]	J.-Ch. de Borda, "Mémoire sur les élections au scrutin" Histoire Acad. R. des Sci. (1781)
[a4]	S.J. Brams, "Rational politics: decisions, games, and strategy" , CQ Press (1985)
[a5]	S.J. Brams, P.C. Fishburn, "Approval voting" , Birkhäuser (1983)
[a6]	Marquis de Condorcet, "Essai sur l'application de l'analyse à la probabilité des décisions rendues à la pluralité des voix" , Paris (1785)
[a7]	R. Farquarhson, "Theory of voting" , Yale Univ. Press (1969)
[a8]	P.C. Fishburn, "The theory of social choice" , Princeton Univ. Press (1973)
[a9]	P.C. Fishburn, "Condorcet social choice functions" SIAM J. Appl. Math. , 33 (1977) pp. 469–489
[a10]	P.C. Fishburn, "Interprofile conditions and impossibility" , Horwood (1987)
[a11]	W.V. Gehrlein, "Condorcet's paradox" Theory and Decision , 15 (1983) pp. 161–197
[a12]	A. Gibbard, "Manipulation of voting schemes: a general result" Econometrica , 41 (1973) pp. 587–601
[a13]	T. Hare, "The election of representatives, parliamentary and municipal: a treatise" , Longman (1861)
[a14]	J.S. Kelly, "Arrow impossibility theorems" , Acad. Press (1978)
[a15]	K.O. May, "A set of independent necessary and sufficient conditions for simple majority decisions" Econometrica , 20 (1952) pp. 680–684
[a16]	S. Merrill, "Making multicandidate elections more democratic" , Princeton Univ. Press (1988)
[a17]	Y. Murakami, "Logic and social choice" , Routledge and Kegan Paul (1968)
[a18]	B. Peleg, "Game-theoretical analysis of voting in committees" , Cambridge Univ. Press (1984)
[a19]	D.G. Saari, "Geometry of voting" , Springer (1994)
[a20]	M.A. Satterthwaite, "Strategy-proofness and Arrow's conditions: existence and correspondence theorems for voting procedures and social welfare functions" J. Econom. Th. , 10 (1975) pp. 187–218
[a21]	H.P. Young, "Social choice scoring functions" SIAM J. Appl. Math. , 28 (1975) pp. 824–838