Arrow's Theorem

The time seems apt for me to write my first “proper” blog-post. Two days back I happened to stumble-upon (using the excellent firefox add-on) a very interesting theorem in socio-economic theory, called Arrow’s theorem. I read it, clicked “I Like It!” and closed it. That was not enough to make me write a blog post on it. Before I describe more about it, I would just like to add one of my strong beliefs: The more you read, the more things start reappearing before you in different contexts. Arrow’s theorem similarly seems to have no superficial connection to either CS or mathematics. But when I saw it in a Discrete Math book I was going through, I once again realised that my opinion was getting stronger day by day.

Arrow’s (Impossibility) Theorem:

[I feel it is easier for me to describe it in terms of elections, so I am using this approach]

Suppose there is an election being held. Let represent the set containing all the candidates and let be the no. of voters in the community. Also assume that voting means that each person writes down the names of the candidates in a self-preferential order ( is a linear ordering of A). Now, our aim is to find a welfare-function which transforms this set of preferences into a global preference order,i.e. basically we want the function to predict the outcome of the election:

which aggregates voters’ preferences into a single preference order on . The -tuple of voter’s preferences is called a preference profile. In its strongest and most simple form, Arrow’s impossibility theorem states that whenever the set of possible alternatives has more than 2 elements and , then the following four conditions(which are reasonable for a voting-system to be fair) become incompatible, i.e. No social-welfare choice function exists which satisfies all the following 4 conditions:

1. Non-dictatorship

One single person should not be able to completely influence the outcome.

2. Unrestricted domain(or universality)

The social welfare function should account for all preferences among all voters to yield a unique and complete ranking of societal choices. Thus:

* The voting mechanism must account for all individual preferences.

* It must do so in a manner that results in a complete ranking of preferences for society.

* It must deterministically provide the same ranking each time voters’ preferences are presented the same way.

3. Independence of irrelevant alternatives (IIA)

The social welfare function should provide the same ranking of preferences among a subset of options as it would for a complete set of options. Changes in individuals’ rankings of irrelevant alternatives (ones outside the subset) should have no impact on the societal ranking of the relevant subset.

4 a. Positive association of social and individual values (or monotonicity)

If any individual modifies his or her preference order by promoting a certain option, then the societal preference order should respond only by promoting that same option or not changing, never by placing it lower than before. An individual should not be able to hurt an option by ranking it higher.

4 b. Non-imposition(or citizen sovereignty)

Every possible societal preference order should be achievable by some set of individual preference orders. This means that the social welfare function is surjective: It has an unrestricted target space.

I am running out of time here. So shall give the proof of the theorem using the theory of Posets in a subsequent post.

Suggestions & Comments awaited.

A.K.B.

About these ads