Social:Independence of irrelevant alternatives

From HandWiki
Short description: Axiom of decision theory and social sciences

The independence of irrelevant alternatives (IIA), also known as binary independence[1] or the independence axiom, is an axiom of decision theory and the social sciences that describes a necessary condition for rational behavior. The axiom says that adding "pointless" (rejected) options should not affect behavior. This is sometimes explained with a short story by philosopher Sidney Morgenbesser:

Morgenbesser, ordering dessert, is told by a waitress that he can choose between blueberry or apple pie. He orders apple. Soon the waitress comes back and explains cherry pie is also an option. Morgenbesser replies "In that case, I'll have blueberry."

Independence of irrelevant alternatives rules out this kind of arbitrary behavior, by stating that:

If A(pple) is chosen over B(lueberry) in the choice set {A, B}, introducing a third option C(herry) must not result in B being chosen over A.

The axiom is deeply connected to several of the most important results in social choice theory, welfare economics, ethics, and rational choice theory; among these are Arrow's Impossibility theorem, the Von Neumann–Morgenstern utility theorem, Harsanyi's utilitarian theorem, and the Dutch book theorems.


In different fields

Social choice theory

In social choice theory and the theory of electoral systems, IIA is defined by Arrow as the assumption that "The social preferences between alternatives x and y depend only on the individual preferences between x and y."[2]

Concretely, suppose Charlie (an irrelevant alternative) enters a race between Alice and Bob, where Alice (leader) is set to defeat Bob. IIA says that in a rational system of voting, if Charlie joins the race but loses, Alice should not suddenly lose the election to Bob. In this context, violating IIA is commonly referred to as the "spoiler effect": support for Charlie "spoils" the election for Alice.

In this form, IIA is one of the conditions in Arrow's impossibility theorem, which shows that it is impossible for any ranked-choice electoral system (including the commonly-used plurality) to behave rationally (i.e. satisfy both IIA and Pareto efficiency).

In rational choice theory and economics

In rational choice theory and economics, IIA is one of the von Neumann-Morgenstern axioms, four axioms that together characterize rational choice under uncertainty (and establish that it can be represented as maximizing expected utility). One of the axioms generalizes IIA to random events:

If [math]\displaystyle{ \,L\prec M }[/math], then for any [math]\displaystyle{ \,N }[/math] and [math]\displaystyle{ \,p\in(0,1] }[/math],
[math]\displaystyle{ \,pL+(1-p)N \prec pM+(1-p)N, }[/math]

where p is a probability, pL+(1-p)N means a gamble with probability p of yielding L and probability (1-p) of yielding N, and [math]\displaystyle{ \,L\prec M }[/math] means that M is preferred over L. This axiom says that if an outcome (or lottery ticket) L is worse than M, then adding with probability p of receiving L rather than N is considered to be not as good as having a chance with probability p of receiving M rather than N.

In economics, the axiom is further connected to the theory of revealed preferences. Economists often invoke IIA when building descriptive models of behavior to ensure agents have well-defined preferences that can be used for making testable predictions. If agents' behavior can change depending on irrelevant circumstances, economic models could be made unfalsifiable by claiming some irrelevant circumstance must have changed when repeating the experiment. Often, the axiom is justified by arguing that irrational agents will be money pumped until they are bankrupt, at which point their preferences become unobservable or irrelevant to the rest of the economy.

In prescriptive (or normative) models, independence of irrelevant alternatives is used together with the other VNM axioms to develop a theory of how rational agents should behave, often by reference to the Dutch Book arguments.

Behavioral economics introduces models that weaken or remove the assumption of IIA, providing greater accuracy at the cost of greater complexity. Behavioral economics has shown the axiom is commonly violated in human decisions; for example, inserting a $5 medium soda between a $3 small and $6 large can make customers perceive the large as a better deal (because it's "only $1 more than the medium").

IIA is a direct consequence of the multinomial logit and conditional logit[clarification needed] models in econometrics[citation needed], meaning such models cannot precisely describe situations where consumers violate IIA.

Voting theory

In voting systems, independence from irrelevant alternatives is often stated as saying if one candidate (X) would win an election without a new candidate (Y), and Y is added to the ballot, then either X or Y should win the election.

Arrow's impossibility theorem shows that no reasonable (non-dictatorial[note 1], Pareto-efficient[note 2]) ranked-choice voting voting system can satisfy IIA, even if voters are perfectly honest.

However, cardinal voting systems are not affected by Arrow's theorem. Approval voting, range voting, median voting, and random dictatorship all satisfy the IIA criterion and Pareto efficiency. Note that if new candidates are added to ballots without changing any of the ratings for existing ballots, the score of existing candidates remains unchanged.

Despite being a cardinal system (and therefore not subject to Arrow's theorem), cumulative voting does not satisfy IIA[citation needed].

Local independence

A criterion weaker than IIA proposed by H. Peyton Young and A. Levenglick is called local independence from irrelevant alternatives (LIIA).[3] LIIA requires that both of the following conditions always hold:

  • If the option that finished in last place is deleted from all the votes, then the order of finish of the remaining options must not change. (The winner must not change.)
  • If the winning option is deleted from all the votes, the order of finish of the remaining options must not change. (The option that finished in second place must become the winner.)

An equivalent way to express LIIA is that if a subset of the options are in consecutive positions in the order of finish, then their relative order of finish must not change if all other options are deleted from the votes. For example, if all options except those in 3rd, 4th and 5th place are deleted, the option that finished 3rd must win, the 4th must finish second, and 5th must finish 3rd.

Another equivalent way to express LIIA is that if two options are consecutive in the order of finish, the one that finished higher must win if all options except those two are deleted from the votes.

LIIA is weaker than IIA because satisfaction of IIA implies satisfaction of LIIA, but not vice versa.

Despite being a weaker criterion (i.e. easier to satisfy) than IIA, LIIA is satisfied by very few voting methods. These include Kemeny-Young and ranked pairs, but not Schulze. Just as with IIA, LIIA compliance for rating methods such as approval voting, range voting, and majority judgment require the assumption that voters rate each alternative individually and independently of knowing any other alternatives, on an absolute scale (calibrated prior to the election), even when this assumption implies that voters having meaningful preferences in a two candidate election will necessarily abstain.

In social choice

From Kenneth Arrow,[4] each "voter" i in the society has an ordering Ri that ranks the (conceivable) objects of social choicex, y, and z in simplest case—from high to low. An aggregation rule (voting rule) in turn maps each profile or tuple (R1, ...,Rn) of voter preferences (orderings) to a social ordering R that determines the social preference (ranking) of x, y, and z.

Arrow's IIA requires that whenever a pair of alternatives is ranked the same way in two preference profiles (over the same choice set), then the aggregation rule must order these alternatives identically across the two profiles.[5] For example, suppose an aggregation rule ranks a above b at the profile given by

  • (acbd, dbac),

(i.e., the first individual prefers a first, c second, b third, d last; the second individual prefers d first, ..., and c last). Then, if it satisfies IIA, it must rank a above b at the following three profiles:

  • (abcd, )
  • (abcd, )
  • (acdb, ).

The last two forms of profiles (placing the two at the top; and placing the two at the top and bottom) are especially useful in the proofs of theorems involving IIA.

Arrow's IIA does not imply an IIA similar to those different from this at the top of this article nor conversely.[6]

In the first edition of his book, Arrow misinterpreted IIA by considering the removal of a choice from the consideration set. Among the objects of choice, he distinguished those that by hypothesis are specified as feasible and infeasible. Consider two possible sets of voter orderings ([math]\displaystyle{ R_1 }[/math], ...,[math]\displaystyle{ R_n }[/math] ) and ([math]\displaystyle{ R_1' }[/math], ...,[math]\displaystyle{ R_n' }[/math]) such that the ranking of X and Y for each voter i is the same for [math]\displaystyle{ R_i }[/math] and [math]\displaystyle{ R_i' }[/math]. The voting rule generates corresponding social orderings R and R'. Now suppose that X and Y are feasible but Z is infeasible (say, the candidate is not on the ballot or the social state is outside the production possibility curve). Arrow required that the voting rule that R and R' select the same (top-ranked) social choice from the feasible set (X, Y), and that this requirement holds no matter what the ranking is of infeasible Z relative to X and Y in the two sets of orderings. IIA does not allow "removing" an alternative from the available set (a candidate from the ballot), and it says nothing about what would happen in such a case: all options are assumed to be "feasible."

Examples

Borda count

In a Borda count election, 5 voters rank 5 alternatives [A, B, C, D, E].

3 voters rank [A>B>C>D>E]. 1 voter ranks [C>D>E>B>A]. 1 voter ranks [E>C>D>B>A].

Borda count (a=0, b=1): C=13, A=12, B=11, D=8, E=6. C wins.

Now, the voter who ranks [C>D>E>B>A] instead ranks [C>B>E>D>A]; and the voter who ranks [E>C>D>B>A] instead ranks [E>C>B>D>A]. They change their preferences only over the pairs [B, D], [B, E] and [D, E].

The new Borda count: B=14, C=13, A=12, E=6, D=5. B wins.

The social choice has changed the ranking of [B, A] and [B, C]. The changes in the social choice ranking are dependent on irrelevant changes in the preference profile. In particular, B now wins instead of C, even though no voter changed their preference over [B, C].

Borda count and strategic voting

Consider an election in which there are three candidates, A, B, and C, and only two voters. Each voter ranks the candidates in order of preference. The highest ranked candidate in a voter's preference is given 2 points, the second highest 1, and the lowest ranked 0; the overall ranking of a candidate is determined by the total score it gets; the highest ranked candidate wins.

Considering two profiles:

  • In profiles 1 and 2, the first voter casts his votes in the order BAC, so B receives 2 points, A receives 1, and C receives 0 from this voter.
  • In profile 1, the second voter votes ACB, so A will win outright (the total scores: A 3, B 2, C 1).
  • In profile 2, the second voter votes ABC, so A and B will tie (the total scores: A 3, B 3, C 0).

Thus, if the second voter wishes A to be elected, he had better vote ACB regardless of his actual opinion of C and B. This violates the idea of "independence from irrelevant alternatives" because the voter's comparative opinion of C and B affects whether A is elected or not. In both profiles, the rankings of A relative to B are the same for each voter, but the social rankings of A relative to B are different.

Copeland

This example shows that Copeland's method violates IIA. Assume four candidates A, B, C and D with 6 voters with the following preferences:

# of voters Preferences
1 A > B > C > D
1 A > C > B > D
2 B > D > A > C
2 C > D > A > B

The results would be tabulated as follows:

Pairwise Preferences
X
A B C D
Y A [X] 2
[Y] 4
[X] 2
[Y] 4
[X] 4
[Y] 2
B [X] 4
[Y] 2
[X] 3
[Y] 3
[X] 2
[Y] 4
C [X] 4
[Y] 2
[X] 3
[Y] 3
[X] 2
[Y] 4
D [X] 2
[Y] 4
[X] 4
[Y] 2
[X] 4
[Y] 2
Pairwise election results (won-tied-lost): 2-0-1 1-1-1 1-1-1 1-0-2
  • [X] indicates voters who preferred the candidate in the column caption to the one in the row caption
  • [Y] indicates voters who preferred the candidate in the row caption to the one in the column caption

Result: A has two wins and one defeat, while no other candidate has more wins than defeats. Thus, A is elected Copeland winner.

Change of irrelevant preferences

Now, assume all voters would raise D over B and C without changing the order of A and D. The preferences of the voters would now be:

# of voters Preferences
1 A > D > B > C
1 A > D > C > B
2 D > B > A > C
2 D > C > A > B

The results would be tabulated as follows:

Pairwise Preferences
X
A B C D
Y A [X] 2
[Y] 4
[X] 2
[Y] 4
[X] 4
[Y] 2
B [X] 4
[Y] 2
[X] 3
[Y] 3
[X] 6
[Y] 0
C [X] 4
[Y] 2
[X] 3
[Y] 3
[X] 6
[Y] 0
D [X] 2
[Y] 4
[X] 0
[Y] 6
[X] 0
[Y] 6
Pairwise election results (won-tied-lost): 2-0-1 0-1-2 0-1-2 3-0-0

Result: D wins against all three opponents. Thus, D is elected Copeland winner.

Conclusion

The voters changed only their preference orders over B, C and D. As a result, the outcome order of D and A changed. A turned from winner to loser without any change of the voters' preferences regarding A. Thus, Copeland's method fails the IIA criterion.

Instant-runoff voting

In an instant-runoff election, 5 voters rank 3 alternatives [A, B, C].

2 voters rank [A>B>C]. 2 voters rank [C>B>A]. 1 voter ranks [B>A>C].

Round 1: A=2, B=1, C=2; B eliminated. Round 2: A=3, C=2; A wins.

Now, the two voters who rank [C>B>A] instead rank [B>C>A]. They change only their preferences over B and C.

Round 1: A=2, B=3, C=0; B wins with a majority of the vote.

The social choice ranking of [A, B] is dependent on preferences over the irrelevant alternatives [B, C].

Kemeny–Young method

Main page: Social:Kemeny–Young method

This example shows that the Kemeny–Young method violates the IIA criterion. Assume three candidates A, B and C with 7 voters and the following preferences:

# of voters Preferences
3 A > B > C
2 B > C > A
2 C > A > B

The Kemeny–Young method arranges the pairwise comparison counts in the following tally table:

All possible pairs
of choice names
Number of votes with indicated preference
Prefer X over Y Equal preference Prefer Y over X
X = A Y = B 5 0 2
X = A Y = C 3 0 4
X = B Y = C 5 0 2

The ranking scores of all possible rankings are:

Preferences 1. vs 2. 1. vs 3. 2. vs 3. Total
A > B > C 5 3 5 13
A > C > B 3 5 2 10
B > A > C 2 5 3 10
B > C > A 5 2 4 11
C > A > B 4 2 5 11
C > B > A 2 4 2 8

Result: The ranking A > B > C has the highest ranking score. Thus, A wins ahead of B and C.

Change of irrelevant preferences

Now, assume the two voters (marked bold) with preferences B > C > A would change their preferences over the pair B and C. The preferences of the voters would then be in total:

# of voters Preferences
3 A > B > C
2 C > B > A
2 C > A > B

The Kemeny–Young method arranges the pairwise comparison counts in the following tally table:

All possible pairs
of choice names
Number of votes with indicated preference
Prefer X over Y Equal preference Prefer Y over X
X = A Y = B 5 0 2
X = A Y = C 3 0 4
X = B Y = C 3 0 4

The ranking scores of all possible rankings are:

Preferences 1. vs 2. 1. vs 3. 2. vs 3. Total
A > B > C 5 3 3 11
A > C > B 3 5 4 12
B > A > C 2 3 3 8
B > C > A 3 2 4 9
C > A > B 4 4 5 13
C > B > A 4 4 2 10

Result: The ranking C > A > B has the highest ranking score. Thus, C wins ahead of A and B.

Conclusion

The two voters changed only their preferences over B and C, but this resulted in a change of the order of A and C in the result, turning A from winner to loser without any change of the voters' preferences regarding A. Thus, the Kemeny-Young method fails the IIA criterion.

Minimax

This example shows that the Minimax method violates the IIA criterion. Assume four candidates A, B and C and 13 voters with the following preferences:

# of voters Preferences
2 B > A > C
4 A > B > C
3 B > C > A
4 C > A > B

Since all preferences are strict rankings (no equals are present), all three Minimax methods (winning votes, margins and pairwise opposite) elect the same winners.

The results would be tabulated as follows:

Pairwise election results
X
A B C
Y A [X] 5
[Y] 8
[X] 7
[Y] 6
B [X] 8
[Y] 5
[X] 4
[Y] 9
C [X] 6
[Y] 7
[X] 9
[Y] 4
Pairwise election results (won-tied-lost): 1-0-1 1-0-1 1-0-1
worst pairwise defeat (winning votes): 7 8 9
worst pairwise defeat (margins): 1 3 5
worst pairwise opposition: 7 8 9
  • [X] indicates voters who preferred the candidate in the column caption to the one in the row caption
  • [Y] indicates voters who preferred the candidate in the row caption to the one in the column caption

Result: A has the closest biggest defeat. Thus, A is elected Minimax winner.

Change of irrelevant preferences

Now, assume the two voters (marked bold) with preferences B > A > C change the preferences over the pair A and C. The preferences of the voters would then be in total:

# of voters Preferences
4 A > B > C
5 B > C > A
4 C > A > B

The results would be tabulated as follows:

Pairwise election results
X
A B C
Y A [X] 5
[Y] 8
[X] 9
[Y] 4
B [X] 8
[Y] 5
[X] 4
[Y] 9
C [X] 4
[Y] 9
[X] 9
[Y] 4
Pairwise election results (won-tied-lost): 1-0-1 1-0-1 1-0-1
worst pairwise defeat (winning votes): 9 8 9
worst pairwise defeat (margins): 5 3 5
worst pairwise opposition: 9 8 9

Result: Now, B has the closest biggest defeat. Thus, B is elected Minimax winner.

Conclusion

So, by changing the order of A and C in the preferences of some voters, the order of A and B in the result changed. B is turned from loser to winner without any change of the voters' preferences regarding B. Thus, the Minimax method fails the IIA criterion.

Plurality voting system

In a plurality voting system 7 voters rank 3 alternatives (A, B, C).

  • 3 voters rank (A>B>C)
  • 2 voters rank (B>A>C)
  • 2 voters rank (C>B>A)

In an election, initially only A and B run: B wins with 4 votes to A's 3, but the entry of C into the race makes A the new winner.

The relative positions of A and B are reversed by the introduction of C, an "irrelevant" alternative.

Ranked pairs

Main page: Social:Ranked pairs

This example shows that the Ranked pairs method violates the IIA criterion. Assume three candidates A, B and C and 7 voters with the following preferences:

# of voters Preferences
3 A > B > C
2 B > C > A
2 C > A > B

The results would be tabulated as follows:

Pairwise election results
X
A B C
Y A [X] 2
[Y] 5
[X] 4
[Y] 3
B [X] 5
[Y] 2
[X] 2
[Y] 5
C [X] 3
[Y] 4
[X] 5
[Y] 2
Pairwise election results (won-tied-lost): 1-0-1 1-0-1 1-0-1

The sorted list of victories would be:

Pair Winner
A (5) vs. B (2) A 5
B (5) vs. C (2) B 5
A (3) vs. C (4) C 4

Result: A > B and B > C are locked in (and C > A cannot be locked in after that), so the full ranking is A > B > C. Thus, A is elected Ranked pairs winner.

Change of irrelevant preferences

Now, assume the two voters (marked bold) with preferences B > C > A change their preferences over the pair B and C. The preferences of the voters would then be in total:

# of voters Preferences
3 A > B > C
2 C > B > A
2 C > A > B

The results would be tabulated as follows:

Pairwise election results
X
A B C
Y A [X] 2
[Y] 5
[X] 4
[Y] 3
B [X] 5
[Y] 2
[X] 4
[Y] 3
C [X] 3
[Y] 4
[X] 3
[Y] 4
Pairwise election results (won-tied-lost): 1-0-1 0-0-2 2-0-0

The sorted list of victories would be:

Pair Winner
A (5) vs. B (2) A 5
B (3) vs. C (4) C 4
A (3) vs. C (4) C 4

Result: All three duels are locked in, so the full ranking is C > A > B. Thus, the Condorcet winner C is elected Ranked pairs winner.

Conclusion

So, by changing their preferences over B and C, the two voters changed the order of A and C in the result, turning A from winner to loser without any change of the voters' preferences regarding A. Thus, the Ranked pairs method fails the IIA criterion.

Schulze method

Main page: Social:Schulze method

This example shows that the Schulze method violates the IIA criterion. Assume four candidates A, B, C and D and 12 voters with the following preferences:

# of voters Preferences
4 A > B > C > D
2 C > B > D > A
3 C > D > A > B
2 D > A > B > C
1 D > B > C > A

The pairwise preferences would be tabulated as follows:

Matrix of pairwise preferences
d[*,A] d[*,B] d[*,C] d[*,D]
d[A,*] 9 6 4
d[B,*] 3 7 6
d[C,*] 6 5 9
d[D,*] 8 6 3

Now, the strongest paths have to be identified, e.g. the path D > A > B is stronger than the direct path D > B (which is nullified, since it is a tie).

Strengths of the strongest paths
d[*,A] d[*,B] d[*,C] d[*,D]
d[A,*] 9 7 7
d[B,*] 7 7 7
d[C,*] 8 8 9
d[D,*] 8 8 7

Result: The full ranking is C > D > A > B. Thus, C is elected Schulze winner and D is preferred over A.

Change of irrelevant preferences

Now, assume the two voters (marked bold) with preferences C > B > D > A change their preferences over the pair B and C. The preferences of the voters would then be in total:

# of voters Preferences
4 A > B > C > D
2 B > C > D > A
3 C > D > A > B
2 D > A > B > C
1 D > B > C > A

Hence, the pairwise preferences would be tabulated as follows:

Matrix of pairwise preferences
d[*,A] d[*,B] d[*,C] d[*,D]
d[A,*] 9 6 4
d[B,*] 3 9 6
d[C,*] 6 3 9
d[D,*] 8 6 3

Now, the strongest paths have to be identified:

Strengths of the strongest paths
d[*,A] d[*,B] d[*,C] d[*,D]
d[A,*] 9 9 9
d[B,*] 8 9 9
d[C,*] 8 8 9
d[D,*] 8 8 8

Result: Now, the full ranking is A > B > C > D. Thus, A is elected Schulze winner and is preferred over D.

Conclusion

So, by changing their preferences over B and C, the two voters changed the order of A and D in the result, turning A from loser to winner without any change of the voters' preferences regarding A. Thus, the Schulze method fails the IIA criterion.

Two-round system

A probable example of the two-round system failing this criterion was the 2002 French presidential election. Polls leading up to the election have suggested a runoff between centre-right candidate Jacques Chirac and centre-left candidate Lionel Jospin, which Jospin was expected to win by a large margin. However, the first round was contested by an unprecedented 16 candidates, including left-wing candidates who intended to support Jospin in the runoff. This resulted in the far-right candidate, Jean-Marie Le Pen, finishing second and entering the runoff instead of Jospin. Chirac won by a large margin. Thus, the presence of many candidates who did not win the election changed which the result.

See also

Footnotes

  1. A rule is called dictatorial if the social choice depends only on a single voter's preferences.
  2. A rule is called Pareto-efficient (or unanimous) if, when every voter prefers A to B, the social choice rule will always prefer A to B.

References

  1. Saari, Donald G. (2001). Decisions and elections : explaining the unexpected (1. publ. ed.). Cambridge [u.a.]: Cambridge Univ. Press. pp. 39. ISBN 0-521-00404-7. https://archive.org/details/decisionselectio0000saar. 
  2. Arrow 1963, p. 28.
  3. Young, H. Peyton (1995). Equity: In Theory and Practice. Princeton University Press. ISBN 0-691-04464-3. https://books.google.com/books?id=H0IQ0PKZ4WYC. 
  4. Arrow 1951, pp. 15, 23, 27.
  5. More formally, an aggregation rule (social welfare function) f is pairwise independent if for any profiles [math]\displaystyle{ p=(R_1, \ldots, R_n) }[/math], [math]\displaystyle{ p'=(R'_1, \ldots, R'_n) }[/math] of preferences and for any alternatives x, y, if [math]\displaystyle{ R_i\cap\{x,y\}^2=R'_i\cap \{x,y\}^2 }[/math] for all i, then [math]\displaystyle{ f(p)\cap\{x,y\}^2=f(p')\cap \{x,y\}^2 }[/math]. This is the definition of Arrow's IIA adopted in the context of Arrow's theorem in most textbooks and surveys (Austen-Smith and Banks, 1999, page 27; Campbell and Kelly, 2002, in Handbook of SCW, page 43; Feldman and Serrano, 2005, Section 13.3.5; Gaertner, 2009, page 20; Mas-Colell, Whinston, Green, 1995, page 794; Nitzan, 2010, page 40; Tayor, 2005, page 18; see also Arrow, 1963, page 28 and Sen, 1970, page 37). This formulation does not consider addition or deletion of options, since the set of options is fixed, and this is a condition involving two profiles.
  6. Ray 1973.

Bibliography

Further reading