[EM] Impossibility on Wikipedia: Arrow, Gibbard, and Satterthwaite

[Rob Lanphier]

Hi folks,

I'm going to send a similar email here to the EM list that I recently
sent to several folks who hang out in academic circles.  The answer I
received from the academic circles was valuable, but I also think that
folks on this mailing list can provide a different (and useful)
perspective.

I've long taken it for granted that impossibility theorems like
Arrow's theorem and Gibbard's theorem mathematically prove that there
are always going to be important electoral criteria that will be
mutually exclusive in ANY credible electoral system.  I've been at
peace with that for a long time, much in the same way that I'm at
peace with mutually exclusive criteria for my transportation needs
(e.g. I should take something with more carrying capacity than a
bicycle to go shopping for large furniture, no matter how good the
bike is).  The physics of electoral systems and the physics of the
real world have certain mathematical rules that are tough to get
around.

Since the Center for Election Science (<https://electionscience.org>)
started getting momentum and having some electoral success in the late
2010s, there's been a push to distinguish between "cardinal voting"
and "ordinal voting" as the top of the hierarchy distinguishing all
voting systems.  Since the ballot is what people see, that's
understandable, I suppose.  However, in my mind, the ballots don't
matter as much as the tallying method, and moreover, it's possible to
use cardinal voting ballots and then tally them using systems that
some folks classify as "ordinal" systems.

In discussions with electoral reform folks over the past few years,
I've been learning about Arrow, Gibbard, and Satterthwaite, and trying
to document what I've learned on Wikipedia and electowiki.

In editing Wikipedia articles related to election methods in the past
few years, it seems there are three theorems that have made the rounds
with regards to impossibility theorems:

1. Arrow's impossibility theorem (published in 1951): basically the
granddaddy of impossibility theorems, which seemingly only applies to
ordinal voting methods.
<https://en.wikipedia.org/wiki/Arrow%27s_impossibility_theorem>
2. Gibbard's theorem (published in 1973): generalizes Arrow's theorem
to apply to pretty much every social choice function
<https://en.wikipedia.org/wiki/Gibbard%27s_theorem>
3. The Gibbard–Satterthwaite theorem (published in 1978): a more
specific version of Gibbard's theorem which apparently only applies to
ordinal systems, and focuses on strategic voting
<https://en.wikipedia.org/wiki/Gibbard%E2%80%93Satterthwaite_theorem>

What bothers me of late is a recent change that's been made to the
Gibbard-Satterthwaite article.  I'll quote the most bothersome
addition/replacement that's in the "Gibbard–Satterthwaite theorem"
article as of this writing:
> The theorem does not apply to cardinal voting systems such as score
> voting or STAR voting, which can often guarantee honest (or semi-honest)
> rankings in cases covered by the Gibbard-Satterthwaite theorem,[4] nor
> does it apply to decision mechanisms other than ranked-choice voting.
> Gibbard's theorem provides a weaker result that applies to such
> mechanisms.
>
> The Gibbard-Satterthwaite theorem is often misunderstood as claiming
> that "every voting system encourages dishonesty" or the related adage
> that "there is no best voting system." However, such interpretations are
> not correct; by the revelation principle, there exist many (deterministic,
> non-trivial) voting systems that allow for honest disclosure (outside the
> class of ranked-choice voting systems).

It seems disingenuous to say that all of these voting systems don't
apply to cardinal systems if there is some way to vote "honestly"
(whatever that means).  Strategy and honesty are not mutually
exclusive, and cardinal systems like "score voting" require voters to
be very strategic as part of their voting calculus.  As noted above,
Condorcet tallying methods can be used to tally "cardinal ballots" and
"ordinal ballots", since both express the preferences.

I'll quote what one of the folks in the academic circles stated:
> Since it seems implausible to suppose that one person’s cardinal
> evaluations have meaning in comparison to another person’s evaluations,
> it is implausible to suppose that there is such a thing as an honest cardinal
> evaluation of candidates. If there is such a thing as an honest cardinal
> evaluation of candidates, then opportunities to benefit from dishonest
> evaluations of candidates are rife in systems based on cardinal
> evaluations, while they are likely to be quite rare under Condorcet-
> consistent ranking-based voting systems.

This assertion more-or-less comports with my opinion.  While I don't
think that systems that insist on ranking-based ballots (ordinal
ballots) are ALWAYS superior to systems that rely on simple addition
of rating-based ballots (cardinal ballots), I think the implicit
rankings are at least as important as the explicit ratings.  I
generally think of STAR voting as "Condorcet lite", because, for two
finalists "candA" and "candB", the final runoff doesn't pay attention
to whether:
scenario 1 ) "candA" has 5 stars and "candB" has 4 stars on ballot #1234
or
scenario 2) "candA" has 1 star, and "candB" has 0 stars on ballot #1234

In the end, in both scenarios, ballot #1234 counts in full for
"candA", which seems fair to me.  Regardless, I've frequently found
myself distrusting hardcore cardinal advocates when I see changes like
the one made to English Wikipedia's "Gibbard–Satterthwaite theorem"
article.

Are cardinal voting advocates correct to continually claim that
Arrow's, Gibbard's, and Satterthwaite's theorems don't apply to their
favorite voting methods?  Is there a useful distinction to be drawn
between Gibbard's 1973 theorem and the "Gibbard-Satterthwaite theorem"
published in 1978?  Is the distinction I draw above correct?

Rob