Talk:Gibbard-Satterthwaite theorem
From Wikipedia, the free encyclopedia
 |
|||||
| Mathematics grading: | Stub Class | Importance unassessed. | Field unassessed. | ||
A link or a definition for what 'imposing' in this case means would be very helpful.
- I adapted the relevent part of the linked Arrow's impossibility theorem article to explain imposing voting systems. Maybe it still isn't clear. Worse, voting methods usually choose winners rather than preference orders, but I can't think of suitable words. Hopefully you or someone else will do better. Tim Ivorson 11:10, 17 Jul 2004 (UTC)
I would not characterize the Gibbard-Satterthwaite theorem as following from Arrow's theorem. No obvious connection, except perhaps in technique of combinatorial analysis, is apparent in the original proofs. And the modern approach (cf. Nehring or Barbara's function space approach or Saari's geometric one) tend to be to prove both theorems are trivial corollaries of much more general statements about the admissibility of scfs. Amcfreely 04:14, 4 August 2005 (UTC)
Wrong. The Gibbard-Satterthwaite and Arrow's theorems are equivalent. It is very easy to prove each using the other. For example, let's review how to prove GS from Arrow's: Suppose GS theorem isn't true. Then you have a non-manipulatble voting scheme that only supplies you with a winning alternative. Apply it itteratively, each time dropping the previous winning alternative from the list. You end up with a full linear order on the alternatives. So you get a voting mechanism that gives you a full ordering of the alternatives. Now, from Arrow's theorem you know that this mechanism is not-IIA, hence you could get a setup where a voter i can change the outcome between a and b by playing with the position of alternative c. Now get rid of all the other alternatives but a, b and c. Voter i can now change the winner (a or b) by playing with his report on the rating he gives c. Hence the voting scheme is manipulatable. If this isn't formal enough for you, sit down with pen and paper and try to write an example. I'm sure you could handle it. mousomer 5 August 2005
[edit] Weak vs. linear orders
The Gibbard-Satterthwaite theorem, as written, is about linear orders mapping to linear orders. The result holds for weak orders mapping to linear orders as well (ties in the ballots don't change things). I explained this briefly in the entry, but I think we should have a reference for this. I cited an overview work of Taylor, but if someone else has a reference to an older paper stating this (ideally for the first time), please replace my reference. It almost makes it look like Taylor came up with the idea as I wrote it.
If anyone would like to look into this but has trouble getting started, I'd be happy to give you the list of references from the Taylor paper. I'm looking through that and a number of other sources, but it could take some time. CRGreathouse (t | c) 05:17, 28 August 2006 (UTC)
