Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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:

  1. 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.
  2. 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.
  3. 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.

share|improve this question
add comment

1 Answer

up vote 2 down vote accepted

There is a rather intimate connection between the results.

The origianl proof of Alan Gibbard gave the Gibbard-Satterthwaite theorem as a corollary to Arrow's theorem.

Philip Reny provides parallel proofs of Arrow's theorem and a certain strengthening of the Gibbard-Satterthwaite theorem here.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.