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
and by independency of irrelevant alternatives, we have
----- END -----
©2019 - 2022 all rights reserved