Arrow's Impossibility Theorem Notes

Subscribe Send me a message

#arrow #theorem

Related Readings

This post is a reading note of the articles listed in the Related Readings section. We first present the Arrows' impossibility theorem:

Arrow's Theorem. Any election process that respects transitivity, independence of irrelevant alternatives, and unanimity is a dictatorship.

This is a quite shocking result, although we need to be careful about the nuance in the interpretation of the theorem. The Arrow's theorem is built on top of the following five assumptions/conditions:

Another interesting and related topic is Condorcet paradox. It says a society that consists of rational individuals may not be rational if it uses majority voting to make decisions. Here rational means there is no circular preference. For example, a rational individual cannot have preference such as A > B > C > A. Irrational may be a strong word; at least with circular preference, the individual becomes indecisive. If the individual is willing to make additional efforts to exchange a less liked item for a preferred item, then it becomes irrational because the efforts will be wasted and it will get the same results.

Notation and Concepts

Alternatives: The word alternatives in the literature approximately means choice or candidates. It seems that there is a subtle reason why it's called alternatives. According to some articles, alternatives in Arrow's framework are labels used to represent different entities.
Ranking: More specifically, it's the ranking of alternatives. The ranking is complete in the sense that we can always rank two alternatives. Note that ties are allowed in Arrow's framework.
Voter: A voter is characterized by its ranking of alternatives, which is denoted by $R_i$. In the literature, $xR_iy$ is used to indicate voter $i$ prefers $x$ over $y$. In the eye's of a programmer, $R_i$ is just a comparator which means $R_i$ is an instance of Comparator<Alternative> and we can write $R_i(x,y)$.
Society: A society is a collection of voters, which is represented by the collection of rankings.
Profile: A profile is the collection of rankings in society. It's denoted by $\langle R_1, R_2, ..., R_{n} \rangle$
Election/Constitution: This is a function that maps a profile to a social ordering. Let $f$ denote the election, then it has the signature of Comparator<Alternative> f(List<Comparator<Alternative>>

Proof

The first and third proof in the paper are accessible.

A clarification on profile III in the first proof and the last statement in the penultimate paragraph of the first proof:

By independence of irrelevant alternatives, the social preference over ac must agree with $n^*$ whenever $a >_{n^*} c$.

For any profile $\langle R_1, R_2, ..., R_d, ..., R_n \rangle $, we could construct profile III such that

$$ \forall j \,\,\, R_{j}^{III}(a,c) = R_j(a,c) $$

and by independency of irrelevant alternatives, we have

$$ f( \langle R_1, R_2, ..., R_d, ..., R_n \rangle )(a,c) = f( \langle R_1^{III}, R_2^{III}, ..., R_d^{III}, ..., R_n^{III} \rangle )(a,c) $$

----- END -----

Welcome to join reddit self-learning community.

Send me a message Subscribe to blog updates

Want some fun stuff?