Arrow Theorem is a very classical result in social choice theory, stating very roughly that any reasonable voting procedure is either dictatorial or subject to tactical voting. More precisely, there is a set of voters, and a set of at least 3 candidates; each voter ranks the candidates from best to worst, and a voting system extracts a collective ordering of the candidates from individual preferences. The reasonability criteria are:
- Independence of Irrelevant Alternatives (IIA) --- if you fix to candidates A and B, and alter ratings of some other candidate C, then the relative position of A and B should not change.
- Monotonicity --- if you move a candidate A up at some voter's list of preference, then A will not go down in the collective preference.
- Non-imposition --- if everybody has the same preferences, then the collective preference is the same.
The claim is that if all of these criteria are satisfied, then there exists a dictator, i.e. a voter such that the collective preference is simply his preference.
Gibbard–Satterthwaite Theorem is a similar theorem, with the major difference being that the voting system now produces just one winner, rather than an order. Similarly, if one assumes a non-imposition criterion (each candidate can win) and lack of tactical voting (discussed below), then the rule is dictatorial. Tactical voting is said to take place, if a voter who knows the votes of all other people has the incentive to vote not according to his true preferences. This appears to be closely related to monotonicity.
What puzzles me is: are these theorems equivalent, in the sense that one can derive one from the other by a simple argument?
It would seem that given a voting system as in Arrow theorem, one can get a voting system as in Gibbard–Satterthwaite theorem, simply by selecting the candidate at the top of the ranking.
Conversely, given a voting system as in Gibbard–Satterthwaite theorem, one can construct a voting system for Arrow theorem as follows: To select the candidate at the top of the order, just define him to be the winner of the election (using the system from G-S theorem). Next, somehow dispose of this candidate (move him to the bottom of all preference lists? run election with one less candidate?), and the define the second-to-top candidate to be the winner of the election now. And so on, inductively construct the full ordering of the candidates.
I can't quite see if the procedure works (the problem under considerations feels somewhat vague), but it feels as if it should. Does it work, is there some reference for that, and is there a simpler/more elegant way?
Disclaimer: I have a rather limited expertise in game theory, voting theory, etc. My interests in Arrow Theorem arise from somewhat random circumstances, including the elegant proof via ultrafilters.
