SYMBOLIC SYSTEMS 150:
Computers and Social Decisions (3 units)
Spring Quarter 2001-2002, Stanford University
Instructor:  Todd Davies

Social Choice Theory and Electoral Systems (5/1 and 5/8/02)

The study of noncooperative game theory shows how people can be hampered in reaching the best outcome when they cannot make enforceable agreements.  The prisoner's dilemma illustrates how a Pareto improvement over a dominant strategy equilibrium can be achieved if players can be bound by a side-agreement (prevented from defecting).

Much of game theory for more than two agents concerns what happens when some subset of the players can make binding side-agreements.  Social choice theory is the brance of decision theory concerning agents who all agree to be bound by the outcome of a social choice procedure, such as a vote.

When a Pareto improvement over the status quo is possible, even if it requires kickbacks after the normal form outcome is determined (see Kaldor-Hicks test in the Stevens reading), then unanimity (everyone must agree) will suffice as a social choice procedure.

When people have asymmetric preferences (e.g. some strictly prefer the status quo and others strictly prefer some other alternative), social choice typically involves an aggregation of everyone's preferences.

Assume:
1. a set of voters V={v1,v2,v3,....,vn}, with |V|=n;
2. a set of states or outcomes S={s1,s2,s3,....sm}, with |S|=m; and
3. a set of preference relations P={]1,]2,]3,...]n}, called a preference profile, in which the preference relation ]i for each voter i is  weakly ordered (complete and transitive) over S.

Definition: A social choice function F maps every P into a single outcome s in S.

Theorem (derived from K. May, 1952). For the special case of two alternatives (m=2), the majority rule social choice function uniquely satisfies the criteria of anonymity (not treating any voter differently from any other), monotonicity (the socially chosen outcome s cannot change when reapplied to a profile in which more people favor s than before), and neutrality (not treating any outcome differently from any other). (Note: there are some technical issues regarding tie votes, which are ignored here.)

For m>3 options, problems begin to occur.

Consider the following preference profile:

 Voters Sue Rob Lee 1st a b c Ranks 2nd b c a 3rd c a b

If we apply the pairwise majority rule, then a beats b, b beats c, and c beats a, all by 2-to-1 margins.  But this violates a desirable property of social choice functions, namely transitivity.

For greater than 2 options, a social choice function known as the Borda count chooses an outcome by totaling the ranks that each voter assigns to each outcome, and taking the lowest total.  In this example, the result is a three-way tie, which makes sense.  But the Borda count has another problem, as we shall see.

Example 2 - Violation of pairwise independence

Consider the following profile:

 Voters Sue Rob Lee 1st a b a Ranks 2nd b c b 3rd c d c 4th d a d

If we apply the Borda count to the profile, outcome b is selected.  But now suppose we eliminate c and d from consideration.  Now a wins, even though b is still an available option.  This violates the principle known as the independence of irrelevant alternatives, or pairwise independence.  It states that the socially chosen outcome should not change when unchosen options are eliminated from the preference profile.

These examples are instances of a more general problem, which is that it is impossible to find a social choice function which satisfies all the criteria we would like it to.  A specific result in this regard is the celebrated impossibility theorem for social welfare functionals (SWFLs). An SWFL assigns a unique social rank to each possible outcome (alternative) based on set of individual rankings of the options by voters:

Theorem (derived from K. Arrow, 1951).  For preference profiles P in which each individual voter's preference relation ] is weakly ordered, no social welfare functional F exists which satisfies all five of the following criteria:
(1) Collective rationality: F(P) is complete and transitive.
(2) Weak Paretian-ness: If P is such that there is some outcome, a, that is preferred to another outcome, b, by every voter, then F(P) does not rank b above a.
(3) Unrestricted domain: F(P) is defined for all possible preference profiles P.
(4) Independence of irrelevant alternatives: The relative rankings of two options a and b in F(P) should not change when outcomes other than a and b are eliminated from the profile, and F is reapplied to the modified profile.
(5) Nondictatorship: There is no voter in V such that F(P) always equals that voter's rankings regardless of anyone else's preferences.

A further result, the Gibbard-Satterthwaite theorem (1973) states that no social choice procedure is strategy-proof, meaning that it always rewards truthful reporting of everyone's preferences.

Given these results, it appears that any system for social choice will be imperfect.  Some interesting systems, in addition to those we have discussed (the Borda count and pairwise majority rule), are:

Plurality: Selects the outcome that the greatest number of voters rank first.

Plurality runoff.  Eliminates all but the top two first-rank plurality outcomes from consideration, and applies majority rule to those two outcomes based on the preferences of all voters between only those two outcomes.

Single transferable vote (Hare system).  (Also known as Instant Runoff Voting.) Eliminates the outcome ranked first by the fewest number of voters, reassigns the top rank for those voters to their second choices, and recalculates the first-rank pluralities.  The lowest plurality outcome is eliminated, and the process repeats until a majority winner emerges.

Approval voting.  Each voter designates a subset of the outcomes of which he/she approves.  The winning option is the one that appears on the highest number of approval lists.

Point voting.  Each voter assigns a proportion of their vote to each option, and the winner is the option that receives the most points added across all voters.  Note that this assumes cardinal utilities, as opposed to the purely ordinal preferences assumed for social choice functions until now.

Electoral systems

Ratification democracy  -  Voters ratify a proposition (or not), a.k.a. referenda.

Single representative. - Voters elect one person to hold an office for a set term.

Multi-member district representatives - Voters elect more than one person to represent them; various systems for choosing winners.

Proportional representation - Voters vote for a party, and seats are allocated to candidates from that party proportional to the number of votes each party gets (usually requires some threshold).

Participatory democracy - Voters participate in the drafting of proposals, then choose among them somehow.

Lottery government - Representatives are chosen at random, or by a process similar to jury selection.

Proxy voting - Voters are given the choice of either voting directly on a proposition or else giving their vote to someone whom they trust to make a good choice.