Talk:Gibbard–Satterthwaite theorem

imposing

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

If they are equivalent, does that mean Gibbard-Satterthwaite, like Arrow's, does not apply to systems which provide more than ordinal information, like systems which ask for cardinal rankings? --Gwern (contribs) 23:55 13 September 2011 (GMT)

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)

(If it looks like Taylor came up with the idea as CRGreathouse wrote it, it most likely did happen; Taylor is suspicious of hearing voices and getting all his ideas straight from the thought of others DJB). — Preceding unsigned comment added by 4.35.92.11 (talk) 19:31, 30 May 2016 (UTC)

Hidden assumption: Determinism

It is important to note that the theorem only holds for deterministic systems. This is easiest to see if the following well-known non-deterministic counter-example ("Random Ballot") is considered: Each voter marks her favourite candidate on a ballot, then one of the ballots is drawn at random to determine the winner. This system is neither dictatorial, all candidates can possibly win, and it is always strategically optimal to honestly mark your favourite candidate. User:heitzig-j 04 Nov 2008 —Preceding undated comment was added at 03:28, 5 November 2008 (UTC).

The mentioned method is not susceptible to tactical voting in the sense of the theorem: If your ballot is drawn, it is best when it has your true favourite marked on it. If it is not drawn, it is completely irrelevant what is marked on it. So, regardless of what ballot will be drawn, it is optimal for you to mark your true favourite. In game theoretic terms, voting honestly is always a strictly dominating strategy and hence the only Nash equilibrium is when all voters vote honestly. Heitzig-j (talk) 18:07, 14 November 2008 (UTC)

I agree and added non-random as a qualifier. Otherwise the result might be interpreted too widely. --Xeeron (talk) 12:27, 2 March 2010 (UTC)

Yes but your example would be "dictatorial", albeit with a dictator who had been picked at random. One of the assumptions is that the system is not dictatorial.

George P

NOTE: I have not removed the "non random" word from the article but I strongly suggest that this be removed because, so long as the system is not dictatorial the system will still be subject ot tactical voting.

However I would like to reach a consensus on this before simply making the edit.

Perhaps the edit could mention that picking a single ballot at random would constitute a "dictatorial" system. However any system that involves picking more than two ballots at random (before making a deterministic calculation to determine a winner) would be subject to the result of the theorem.

Furthermore I believe that the "non random" part may be an example of "politically motivated boarding" (see my later comment) as it would suggest that STV is not covered by arrow's theorum (because STV has random reallocations of votes in the system). STV is not on the ballot in the UK referendum but it is the preferred system of the majority of liberal democrat politicians and the AV debate will be used as a platform for asking the voters to give them a mandate for STV.

However STV is still, like all non dictatorial voting systems, subject to tactical voting (indeed it is actually more subject to tactical voting because of the need to prevent "erosion" in the reallocating process. hence the posters in the irish elections asking supporters of the main parties, in different area of the same "constituency" to vote for different candidates.

This, however, demonstrates the pressing need to freeze this article until may 2011 because, otherwise it is likely to turn into a minefield of political point scoring and "blinding with science".

George P

Also: Can I suggest that this article be frozen or heavily monitored for the period up till 5th May 2011. Reasoning: It will be subject to politically motivated "boarding" in the run up to the Alternative Vote referendum in the United Kingdom (in May next year).

 -Supporters of AV will be wanting to show that AV is a "non tactical" voting system ergo they may try to make this article incomprehensible or they may add a section to it trying ot perswead people to vote for AV

 -Meanwhile supporters of FPTP may try to use it to make blunt political points which, valid or otherwise, will detract form the encyclopaedic nature of an article which, when it was written, was written in a spirit of mathematical integrity.

George P —Preceding unsigned comment added by 144.82.84.88 (talk) 14:22, 15 November 2010 (UTC)

Sorry for the slew of comments but it also might be worth mentioning the voting system used to elect the pope which is often given as an example of a "non-tactical" voting system.

However, because it involves potentially infinitely many rounds of voting it is not suitable for a general election.

It is also subject to what I would call "tactical" considerations but it is not mathematically deterministic or probabilistic but involves an ongoing series of human judgements in the mind of each cardinal. It would not be recognised as a "voting system" by a psephologist.

'Dictatorial'

The word 'dictatorial' seems to have a specific, technical meaning in this context- one I'm not familiar with. Could someone knowledgeable put it in the article? -Toptomcat (talk) 07:45, 8 November 2008 (UTC)

I provided a link to Arrow's theorem. Kiefer.Wolfowitz (talk) 13:10, 21 February 2010 (UTC)

UK AV referendum

Can I suggest that this article be frozen or heavily monitored for the period up till 5th May 2011. Reasoning: It will be subject to politically motivated "boarding" in the run up to the Alternative Vote referendum in the United Kingdom (in May next year).

-Supporters of AV will be wanting to show that AV is a "non tactical" voting system ergo they may try to make this article incomprehensible or they may add a section to it trying ot perswead people to vote for AV

-Meanwhile supporters of FPTP may try to use it to make blunt political points which, valid or otherwise, will detract form the encyclopaedic nature of an article which, when it was written, was written in a spirit of mathematical integrity.—Preceding unsigned comment added by 144.82.84.88 (talk • contribs)

Similar theorem about "strategic nomination"

Here's a little theorem with most of the same force as Gibbard-Satterthwaite but expressed in terms of manipulating the set of nominees rather than misrepresenting a voter's preferences. In the context of public elections, where the set of nominated alternatives isn't fixed by nature and many voters are strategically unsophisticated, this may be more relevant than Gibbard-Satterthwaite's framework (which assumes a fixed set of alternatives).

Axiom: Any ordering of alternatives is an admissible vote. (Universal Domain)

Axiom: One of the alternatives must be elected. (Prime Directive)

Theorem: Given any voting method that reduces to majority rule when only two alternatives are ranked, both of the following hold:

1. There is at least one collection of votes such that deleting a losing alternative from everyone's vote can cause another losing alternative to become the winner.

2. There is at least one collection of votes such that inserting an additional nominee into everyone's vote can cause a losing alternative to become the winner.

Proof: Suppose the nominees are {x,y,z}. Suppose about a third of the voters vote "x over y over z," about a third vote "y over z over x" and the rest vote "z over x over y." Without loss of generality, assume x is the winner. (We could swap the alternatives' labels if necessary to make "x" the label of the winner.) Suppose y, a losing alternative, is deleted from every vote. Only two alternatives remain, so majority rule applies, and since about 2/3 vote z over x, the choice from {x,z} is z. That proves the first part of the theorem. Now restore y to the votes; this changes the winner back from z to x, which proves the second part of the theorem.

Significance: When many voters are not strategically sophisticated or will have trouble coordinating their voting strategies with other voters (such as agreeing with other voters on which compromise to vote for or rank on top), the outcome can often be manipulated during the nomination phase by adding or deleting alternatives. This raises important questions: How are the nominees nominated, and by whom, and which (non-dictatorial, non-imposing, usually deterministic) voting method is least manipulable by strategic nomination? (Hint: take a look at the "Maximize Affirmed Majorities" voting method, which finds the order of finish that minimizes the size of the largest unaffirmed majority, in the minlexmax sense. Definition: A majority who ranked x over y is called "affirmed" if the order of finish ranks x over y.)

Example 1: Due to the spoiling problem given plurality rule, many potential candidates choose not to run and each party nominates at most one candidate per office. This kind of manipulation is not necessarily more harmful to society than nominating more alternatives would be (given plurality rule) but the lack of competition can cause many problems: The best candidates might not be nominated; parties (and their supporters) will regret their choice of nominee if negative information about him/her comes to light before election day; voters must accept a nominee's undesired policies along with those desired; issues don't get settled since a small swing of votes can cause many large changes of policies; accountability is undermined since "single issue" minorities can add together to form a winning majority coalition; and accountability on most issues is undermined since most issues (e.g., corrupt government payoffs to rich special interests) are not of paramount importance to voters and thus do not sway elections.

Example 2: (Egregious problem with Borda voting method) Suppose 66% of the voters prefer X over Y. With most voting methods, X would beat Y by a landslide. However, in many contexts it is easy to find an additional alternative Y2 that is very similar to Y, so the minority who prefer Y over X would prefer Y2 over X too, and also slightly inferior to Y, so that nearly all voters would prefer Y over Y2. Given the Borda method, Y would win if the inferior clone is also nominated (assuming the voters' vote sincere preferences): X would receive 2 points from 66% and zero points from 34%, while Y would receive 2 points from 34% plus 1 point from 66%. The greater the number of inferior clones nominated, the larger the landslide that can be overcome. If we assume a few supporters of X are strategically sophisticated too, inferior clones of X would also be nominated. (Sauce for the goose is sauce for the gander.) This means public elections would turn into farces given the Borda method.

(Note: Gibbard-Satterthwaite is more general since it also covers voting methods that do not reduce to majority rule when there are only two alternatives. A theorem similar to the above and as general as Gibbard-Satterthwaite can be proved, but its proof is more complex than the proof below, just as the proof of Gibbard-Satterthwaite is more complex.)

(Note 2: Voting methods that don't accept orders of preference from the voters, such as Approval voting or Range Voting, can also be shown to be manipulable by strategic nomination, given reasonable assumptions about how voters vote. For Approval, assume a significant number of voters will approve their most preferred nominee and disapprove their least preferred nominee. For Range Voting, assume a significant number of voters will vote the maximum score for their most preferred nominee and the minimum score for their least preferred nominee. These assumptions are reasonable because these strategies are optimal--other strategies waste at least part of one's voting weight--and they're obvious or easy to learn, like the strategy of not wasting one's vote on a candidate who appears to have no chance to win is obvious when using the "vote for one; plurality rule" method. Note that if all voters vote optimal strategy when there are only two nominees, then Approval, Range Voting and most other methods reduce to majority rule when there are only two nominees, and if most voters vote optimal strategy, then a slight alteration of the proof shows that Approval, Range Voting and many other methods are manipulable by strategic nomination too. Also, even if different assumptions are made about voters' behavior, it may still be easy to demonstrate strategic nomination.)

(Note 3: A theorem like Arrow's can be fitted to this framework too, unsurprisingly. For instance, Independence of Irrelevant Alternatives becomes Choice Consistency: If x is chosen and y is not chosen when the set of nominees is {x,y}, then y must not be chosen from any set of nominees that contains x. For completeness, here's a simpler yet powerful Arrow-like theorem: Every voting method that always chooses at least one winner, satisfies Universal Domain and reduces to majority rule when only two alternatives are ranked fails Choice Consistency.) SEppley (talk) 22:53, 27 August 2011 (UTC)

The article's comment about Arrow's theorem is misleading.

The article says Arrow's theorem is similar to Gibbard-Satterthwaite except it is for social ordering functions instead of social choice functions. That's not the only difference, and in my opinion it's not the most significant difference, since Arrow's theorem can be rewritten for social choice functions (as a number of writers have done). SEppley (talk) 01:49, 28 August 2011 (UTC)

Sen and others have thought that this was an important distinction. Please improve the article using high quality references, such as a reliable source explaining your point.  Kiefer.Wolfowitz 12:30, 28 August 2011 (UTC)

@SEppley do you have a link to these authors? –Maximum Limelihood Estimator 20:26, 21 April 2024 (UTC)

Tactical voting is a misnomer

At least. The same statement can be made of psychosis (schizophrenia, irrationality): psychotic voter will not vote according to his preferences, even if following his own (? ...) preferences leads to his own well being while the contrary does not (crazy). DJB — Preceding unsigned comment added by 4.35.92.11 (talk) 19:26, 30 May 2016 (UTC)

Duplicate

or not? unclear — Preceding unsigned comment added by 97.113.35.180 (talk)

I propose that Gibbard's theorem be merged into Gibbard–Satterthwaite theorem, as they seem to contain largely duplicate content. See a previous discussion on this topic at Talk:Gibbard's theorem § Merge. Daask (talk) 21:00, 29 November 2023 (UTC)

@François Durand, Erel Segal, CRGreathouse, AxelBoldt, Omegatron, Ocsenave, Decoy, Iota, Iamthinking2202, Kyle Cronan, HudecEmil, and Orbitalbuzzsaw: Thoughts? Note: I compiled this list from editors of this page and some related articles who are still active. Daask (talk) 21:26, 29 November 2023 (UTC)

• The page on Gibbard's theorem explains the differences between the theorems. I support keeping the pages separate. --Erel Segal (talk) 21:33, 29 November 2023 (UTC)
• Technically two different theorems, but they are conceptually similar. Explaining them together would make sense, but unclear what the Lemma would be, since they are separate theorems. If an acceptable Lemma is found, I support merging, otherwise separate. HudecEmil (talk) 08:52, 30 November 2023 (UTC)
• I don't have a strong opinion here. Definitely there are a number of related theorems in the area of strategy-proofedness. If they were combined, I think the best article title would be Gibbard–Satterthwaite theorem because that's what people are most likely to see and search for. Other alternatives would be (2) the current setup, where Gibbard's 1973 theorem has its own article which discusses that and further results, or (3) separate articles for Gibbard 1978 and Hylland 1980. My weak preference at the moment is the current setup. - CRGreathouse (t | c) 14:21, 30 November 2023 (UTC)
• Support - Both are derived from the same paper by Gibbard, and if they are not the same thing, they are related enough that their similarities and differences would best be discussed in the same place (and maybe also the non-existent Gibbard's 1978 theorem and Hylland's theorem could all be described in one article?) — Omegatron (talk) 21:32, 30 November 2023 (UTC)

While I am flattered to be mentioned, I don't know much about either of these. On the surface, they seem to be very similar, along with the 3 points listed in the opening paragraph of each page.

I would be fine if both pages are merged, so a weak support at least. This page, the Gibbard-Satterthwaite theorem page seems to have more detail and seems to make more sense with concrete examples so could be what the merged page is based off iamthinking2202 (please ping on reply if you would be so kind) 01:47, 15 December 2023 (UTC)

• Oppose — Gibbard's original theorem has become a very important theorem in the electoral-reform community, due to the fact that Gibbard showed that both cardinal voting and ordinal voting are subject to impossibility constraints similar to what Arrow's impossibility theorem showed for ordinal voting. From my understanding, Gibbard-Satterthwaite is constrained to ordinal systems (similar to Arrow's theorem). There are cardinal voting advocates that seek to conflate Gibbard's original theorem and Gibbard-Satterthwaite so as to imply that cardinal methods are superior since there are no notable impossibility theorems that apply to cardinal methods. If "Gibbard's theorem" and "Gibbard–Satterthwaite theorem" are combined into a single article, then great care will need to be taken to ensure this distinction is clear. -- RobLa (talk) 07:42, 23 December 2023 (UTC)

  I think if you combine both its less (rather than more) likely to lead to confusion, since you can explain the "full" Gibbard–Satterthwaite theorem (WDS version) in one place. In that case it's much easier to just say "Well, cardinal methods give you an extra candidate's worth of wiggle room before you run into problems with sincerity." Makes it clear that cardinal methods have an advantage here, but it's not exactly massive. Closed Limelike Curves (talk) 22:21, 14 March 2024 (UTC)

  Actually, I think I stand corrected: does Improved Condorcet Approval satisfy semi-sincerity with 3 candidates? –Maximum Limelihood Estimator 20:30, 21 April 2024 (UTC)

Support. The current division into 2 articles causes confusion about whether Gibbard–Satterthwaite applies to rated voting systems. In practice, it does apply, and Satterthwaite just made some unnecessary assumptions in his proof. OTOH, the theorem's statement should be very careful to distinguish between strategy and sincerity. (I'd be especially interested in any results showing the semi-honesty of score and some Condorcet methods.)

I'd also prefer it if we just said Gibbard-Satterthwaite proves there is "no single voting strategy that is always best", and hopefully explain what that means. In particular, always-best is an extremely strong demand, much stronger than I think most people reading the article would realize; it implies:

1. Everyone else's preferences can be arbitrary or even pathological;
2. Other voters may choose strategies that leave them strictly worse-off or are completely nonsensical;
3. We don't know whether other players collude or behave individually;
4. Voters can have any amount of information ranging from "omniscience" to "literally no knowledge about the election".

Plenty of voting systems have strategy-resistant equilibria, e.g. maximal lotteries are the Strong Nash Equilibrium of any Condorcet method. Other methods are honest in other cases. –Maximum Limelihood Estimator 03:49, 25 April 2024 (UTC)

Revelation principle and cardinal voting

The 2006 article by Warren D. Smith does not claim that cardinal voting is strategy-proof, only that there exist cardinal methods with the property that if a voter prefers candidate A to B, then that voter will never rate B higher than A. I.e. the ranking inferred from the rated ballot never needs to contradict the voter's honest ranking. Compare this with the favorite betrayal criterion, which says that the first preference (Plurality-style) ballot inferred from a ranked ballot never needs to contradict the voter's honest evaluation of his or her favorite.

Ranked methods that pass the favorite betrayal criterion aren't necessarily strategy-proof, so rated methods that are ranking-consistent shouldn't be considered to be so either.

For some reason Brams and Fishburn call ranking-consistent voting "sincere" voting, and Warren D. Smith calls it "honest" voting. But this precise term is different from strategy immunity. Wotwotwoot (talk) 17:16, 16 February 2024 (UTC)

You're completely correct on the revelation principle.

I think my edit was unclear, though--I didn't mean to claim cardinal voting systems are perfectly honest or strategyproof. The point was instead to point out that outside the class of ranked-choice voting systems, there are mechanisms that ensure honesty (e.g. the Vickrey–Clarke–Groves mechanism). Closed Limelike Curves (talk) 04:01, 17 February 2024 (UTC)