Send Election-Methods mailing list submissions to
election-methods@lists.electorama.com

To subscribe or unsubscribe via the World Wide Web, visit

http://lists.electorama.com/listinfo.cgi/election-methods-electorama.com

or, via email, send a message with subject or body 'help' to
election-methods-request@lists.electorama.com

You can reach the person managing the list at
election-methods-owner@lists.electorama.com

When replying, please edit your Subject line so it is more specific
than "Re: Contents of Election-Methods digest..."

Today's Topics:

1. Impossibility on Wikipedia: Arrow, Gibbard, and Satterthwaite
   (Rob Lanphier)
2. Re: Impossibility on Wikipedia: Arrow, Gibbard, and
   Satterthwaite (Richard Lung)
3. Re: Impossibility on Wikipedia: Arrow, Gibbard, and
   Satterthwaite (Kristofer Munsterhjelm)

Message: 1
Date: Wed, 14 Feb 2024 23:13:28 -0800
From: Rob Lanphier roblan@gmail.com
To: election-methods@lists.electorama.com
Subject: [EM] Impossibility on Wikipedia: Arrow, Gibbard, and
Satterthwaite
Message-ID:
<CAK9hOY=nJQ1QstfHi-6mh42H=_
42SPS-Mtqx6r+i-NKueYamTw@mail.gmail.com>
Content-Type: text/plain; charset="UTF-8"

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:

(deterministic,

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:

cardinal

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

Message: 2
Date: Thu, 15 Feb 2024 16:02:57 +0000
From: Richard Lung voting@ukscientists.com
To: Rob Lanphier roblan@gmail.com,
election-methods@lists.electorama.com
Subject: Re: [EM] Impossibility on Wikipedia: Arrow, Gibbard, and
Satterthwaite
Message-ID: c84dcd1e-0f80-4f4c-920b-c0cf25b4ebb3@ukscientists.com
Content-Type: text/plain; charset=UTF-8; format=flowed

Whether you are right or no, there is no conensus on the matter. Theorem
Arrow is like a Cold War between electoral systems. It acknowledges
ordinal votes as a basis for elections, in a denigratory sort of way,
but over-looks the count beyond crude plurality. Ever since,
mathematicians have demonstrated it takes more than mathematics to have
a good understanding of elections. Formerly, it was not so, when they
acted freely as enthusiasts, but the institutionalisation of election
studies appears to have robbed them of any independent critical sense.

That understanding, I gather from his parliamentary speeches on "Mr
Hare's system," is what John Stuart Mill had, the greatest philosopher
of science in the 19th century. The Hare-Mill tradition, that has
continued to the present day, has been by-passed. In so doing, social
choice theory reveals its provincialism. A Nobel prize or so, to give
away, is not a proof. A theorem is only as good as the assumptions on
which it is based. And theorem Arrow compares to a critique of a bicycle
on the basis of the short-comings of a unicycle. It does not deal with
the democratic necessity of a proportional count as well as an ordinal
vote. Simple plurality is "maiorocracy" or the tyranny of the majority,
as Mill and Lani Guinier said.

It is not apparent what decisive argument the social choice school have
that they can take to the voters, for whom elections are supposed to be
meant, and has not been so for 70 years. It is not even apparent that,
after 70 years, they have any idea of, or even belief in, a standard
model of democratic election.

Richard Lung.

On 15/02/2024 07:13, Rob Lanphier wrote:

(deterministic,

the

cardinal

info

Message: 3
Date: Thu, 15 Feb 2024 18:48:22 +0100
From: Kristofer Munsterhjelm km_elmet@t-online.de
To: Rob Lanphier roblan@gmail.com,
election-methods@lists.electorama.com
Subject: Re: [EM] Impossibility on Wikipedia: Arrow, Gibbard, and
Satterthwaite
Message-ID: 3a9c9f20-0d6f-0206-bb48-10b5f335ea9d@t-online.de
Content-Type: text/plain; charset=UTF-8; format=flowed

On 2024-02-15 08:13, Rob Lanphier wrote:

My understanding and opinion is this:

You have three different "main" impossibility theorems:

• Arrow's says that no deterministic reasonable ordinal voting method
  can pass IIA. This means that regardless of whether voters are honest or
  strategic, it's possible that A's win over B depends on not just how
  many voters prefer A to B, but also how many prefer X to Y. This is only
  for cardinal methods.

• Gibbard-Satterthwaite says that no deterministic reasonable ordinal
  method is strategy-proof: there always exists at least one election
  where at least one voter has an incentive to adjust his preferences
  based on how others are voting.

• Gibbard's theorem extends this to a much broader class of election
  methods that includes cardinal methods, thus also implying that no
  deterministic cardinal voting method is strategy-proof.

(In particular, both of Gibbard's theorems are about strategy.)

The part about the revelation principle is incorrect and seems to be
using a very specific definition of honesty, inspired by Warren Smith.
To my knowledge, what the revelation principle says is this:

• Say that a participant in a mechanism employs strategy if the
  information he submits to the mechanism depends on the actions of the
  other participants or his belief about them.[1]

• Say that a mechanism only uses honesty if no participant has an
  incentive to employ strategy.

• Then, if there exists a mechanism where people employ strategy to
  drive it to an optimal or equilibrium outcome, then there also exists a
  mechanism that only uses honesty that reaches the same outcome or
  equilibrium.

Consider it like this: suppose you're involved in a court case, and you
hire a lawyer. You tell the lawyer the truth and the lawyer comes up
with whatever strategy that will advance your interests, given the
evidence and information about the other party. That's a system where
you or your lawyer use strategy to drive the system to a particular state.

But consider a hypothetical legal system using an AI judge. This AI has
a lawyer interface to each party; upon hearing the truth from each
party, it then simulates a court case the way it would proceed with
virtual lawyers who employs strategy based on the honest information.
The AI comes with a proof that your virtual lawyer won't incriminate
you. You would then interact honestly with the system, represented by
the judge, and it would strategize internally.

Thus for any system that requires strategy to get an equilibrium, there
exists another system where you can be honest. It just absorbs the
"lawyer component" into itself.

The problem is that there is no such equilibrium for deterministic
voting methods. That's implied by Gibbard, because otherwise, you could
create a strategy-proof method by first creating a method that invites a
particular type of strategy, and then embodying a "lawyer component"
into it to perform that strategy.

If you try to do this, as far as I understand it, you get a
nondeterministic method since the equilibrium is a mixed strategy. And,
as we know, there exist strategy-proof nondeterministic methods, so that
fits.

This would be like: sometimes, your lawyer says "if we do this, then no
matter what the other party does, we win". But other times he says "if
we focus on these elements and the other party focuses on those, then we
win". Like rock-paper-scissors, which strategy you should play depends
on the strategy the other guy is going to use. So you play them at
random in such a way that the other guy can't guess what you're doing.
That gives a nondeterministic method.

Okay.

So now about IIA.

The seeming advantage that cardinal methods have over ordinal ones is
that they pass IIA. In Range, if A has score 100 and B has score 50,
then A will continue to beat B even if we remove every other candidate.

But I've always been of the opinion that this IIA compliance is either
illusory or a distraction, because it doesn't answer what we really care
about. And that is whether the presence of a candidate who doesn't win
changes the outcome.

Some cardinal proponents say that methods like Range have multiple
honest ballots: there are many ways to vote that are all consistent with
your preference ordering. But a voter has to choose which honest ballot
to cast, and there's no externally fixed scale (what exactly does ten
points mean? What does zero mean?).[2] Thus the selection of candidates
who run will affect the scale, which means that some voters would change
their ratings based on who's running - even if those additional
candidates don't win. So these methods fail what we could call "de facto
IIA", for lack of a better term.

For instance, suppose the election starts off with two pro-democracy
candidates. Then a number of authoritarians enter the race. It's likely
that in Approval, some voters who would've approved of one of the
pro-democracy candidates but not the other, would now approve both to
mark their distaste for authoritarianism and keep the authoritarians
from winning.

So in my opinion, ordinal methods are merely honest about their
limitations. Their logic says: "okay, I can't know if his 10/10 is the
same as her 10/10 or her 5/10. I'll accept that this means I must fail
IIA, instead of seeming to pass it by passing the buck to the voters
that they must use a fixed scale that's not affected by who's in the race."

So ordinal methods clearly fail IIA, and aren't strategy-proof (by
Gibbard-Satterthwaite). Cardinal methods pass IIA (but it doesn't mean
what one may think it means) and aren't strategy-proof (by Gibbard's
theorem).

Both ordinal and cardinal methods may pass de facto IIA for subsets of
elections. E.g. Condorcet methods pass IIA as long as there is a CW,
because adding a candidate either makes that candidate the new CW (hence
he's not irrelevant) or the current winner stays a CW. Similarly,
Approval passes de facto IIA with dichotomous preferences where every
voter has a class of OK candidates and a class of not-OK candidates, and
the boundary between OK and not OK doesn't depend on who's in the race.
(Such voters may sometimes approve everybody or nobody.)

But in general: both cardinal and ordinal methods are susceptible to
strategy. And both cardinal and ordinal methods may have the winner
change from A to B as a consequence of C entering the race.

-km

[1] Strictly speaking we would also want "honesty" to have some
connotation of "being the actual information being asked for". Say
you're dealing with a system that asks you what you like the least and
then gives it to you. You would answer its question with a thing that
you want to be given, so that answer stays the same no matter what other
people interacting with it would say. So by my definition that wouldn't
be strategy, but common-sense would say that it is not honest either.

Warren's definition of honesty is somewhat based on this idea, but it
goes too far in the other direction. It doesn't consider ballots where
your ranking stays the same as under honesty but your scores don't, as
being strategic. I think in part that's due to the difficulty in
comparing utilities, but we can hold rated voting to a higher
standard. Ask and I'll elaborate - this post is long enough :-)

[2] As a side note: we probably can make some observations of other
people's utilities even if we don't have a fixed scale. For instance, I
can probably reason that a candidate who would put you in a prison camp
would be a much worse choice from your perspective than one who would
arrange a party; and that the difference in utilities would be much
greater than say, between a candidate who holds a week-long party and
one who holds a two-week long party.

Some cardinal proponents also refer to von Neumann-Morgenstern utilities
as a way of making comparisons between people's strength of preference:
basically using lotteries to determine how much more a voter prefers one
choice to another. But such scales still need to be normalized because
they always have two unknown variables per voter. Methods that do the
normalization so as to give each voter the same strength fail IIA. Not
doing such renormalization can make the method pass IIA but they still
don't pass "de facto IIA".

See e.g.

https://en.wikipedia.org/wiki/Von_Neumann%E2%80%93Morgenstern_utility_theorem#Incomparability_between_agents
for the need for normalization.

Subject: Digest Footer

Election-Methods mailing list
Election-Methods@lists.electorama.com
http://lists.electorama.com/listinfo.cgi/election-methods-electorama.com

End of Election-Methods Digest, Vol 235, Issue 30

First, I'd like to thank Kristofer for his wonderful response+addition
to this discussion. :-)

I made most of the edits on Wikipedia, and I'm happy to talk about how
we could try and make them more neutral. My goal wasn't to be a
cardinal partisan, although I'll admit I'm generally a supporter. I'm
a big fan of some of the newer Condorcet methods (like Ranked Pairs)
as well, and I think the difference between these and cardinal methods
is likely pretty small in practice.

Rather than advocating any particular voting system, my goal was to
nip some common misunderstandings about these theorems in the bud.
Mostly these relate to the applicability of some of these theorems
(especially Arrow's) to cardinal systems. It sounds like in doing so,
I might have introduced a framing that gives the opposite
misimpression (that cardinal systems are somehow immune to /any/ kind
of unpleasant behavior, when they're clearly not).

Here's what I think is important for people to understand on each of
these topics:

• Arrow's theorem: Within the Arrovian paradigm (a function
  aggregates individual preferences to give us social preferences),
  any rule that satisfies IIA (and therefore coherence) is cardinal.
• Gibbard-Satterthwaite: It's impossible to guarantee honesty (no
  preference reversals) for any ordinal voting system with >2
  candidates (original) or any cardinal system with >3 candidates
  (WDS extension).
  o /Comment on semi-honest rankings/: I think honesty in rankings
  and honesty in ratings are both valuable (but distinct)
  notions of honesty, and it's reasonable to separate them.
  Satterthwaite's original theorem focused on ordinal systems,
  however (assuming rankings throughout). Because of that, I
  interpret the theorem as being about ordinal honesty, which
  score voting happens to satisfy for the 3-candidate case.
  o
  /Comment on revelation principle/: You're completely correct.
  I misinterpreted the textbook I've been working from as
  claiming something stronger than it actually was, and I'll fix
  this ASAP.
• *Gibbard's theorem: *Within the game-theoretic paradigm
  (reported individual preferences are the results of a game, not
  the thing we actually care about), perfect guaranteed honesty is
  impossible for any voting system.
  o /Honest mechanisms: /I do think we want to be clear on the
  distinction between social choice mechanisms and
  voting systems. Some mechanisms (like VCG) can be efficient
  and still guarantee honesty if monetary incentives are available.

By the way, I'd be very interested in a source on strategy implying
IIA violations, so I can add it to the article!

On Thu, Feb 15, 2024 at 10:00 AM
election-methods-request@lists.electorama.com wrote:

 Send Election-Methods mailing list submissions to
 election-methods@lists.electorama.com

 To subscribe or unsubscribe via the World Wide Web, visit
 http://lists.electorama.com/listinfo.cgi/election-methods-electorama.com

 or, via email, send a message with subject or body 'help' to
 election-methods-request@lists.electorama.com

 You can reach the person managing the list at
 election-methods-owner@lists.electorama.com

 When replying, please edit your Subject line so it is more specific
 than "Re: Contents of Election-Methods digest..."


 Today's Topics:

    1. Impossibility on Wikipedia: Arrow, Gibbard, and Satterthwaite
       (Rob Lanphier)
    2. Re: Impossibility on Wikipedia: Arrow, Gibbard, and
       Satterthwaite (Richard Lung)
    3. Re: Impossibility on Wikipedia: Arrow, Gibbard, and
       Satterthwaite (Kristofer Munsterhjelm)


 ----------------------------------------------------------------------

 Message: 1
 Date: Wed, 14 Feb 2024 23:13:28 -0800
 From: Rob Lanphier <roblan@gmail.com>
 To: election-methods@lists.electorama.com
 Subject: [EM] Impossibility on Wikipedia: Arrow, Gibbard, and
         Satterthwaite
 Message-ID:
        
 <CAK9hOY=nJQ1QstfHi-6mh42H=_42SPS-Mtqx6r+i-NKueYamTw@mail.gmail.com
 <mailto:42SPS-Mtqx6r%2Bi-NKueYamTw@mail.gmail.com>>
 Content-Type: text/plain; charset="UTF-8"

 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:

 semi-honest)

 theorem,[4] nor

 voting.

 adage

 interpretations are

 (deterministic,

 (outside the

 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:

 evaluations,

 honest cardinal

 cardinal

 dishonest

 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


 ------------------------------

 Message: 2
 Date: Thu, 15 Feb 2024 16:02:57 +0000
 From: Richard Lung <voting@ukscientists.com>
 To: Rob Lanphier <roblan@gmail.com>,
 election-methods@lists.electorama.com
 Subject: Re: [EM] Impossibility on Wikipedia: Arrow, Gibbard, and
         Satterthwaite
 Message-ID: <c84dcd1e-0f80-4f4c-920b-c0cf25b4ebb3@ukscientists.com>
 Content-Type: text/plain; charset=UTF-8; format=flowed


 Whether you are right or no, there is no conensus on the matter.
 Theorem
 Arrow is like a Cold War between electoral systems. It acknowledges
 ordinal votes as a basis for elections, in a denigratory sort of way,
 but over-looks the count beyond crude plurality. Ever since,
 mathematicians have demonstrated it takes more than mathematics to
 have
 a good understanding of elections. Formerly, it was not so, when they
 acted freely as enthusiasts, but the institutionalisation of election
 studies appears to have robbed them of any independent critical sense.

 That understanding, I gather from his parliamentary speeches on "Mr
 Hare's system," is what John Stuart Mill had, the greatest
 philosopher
 of science in the 19th century. The Hare-Mill tradition, that has
 continued to the present day, has been by-passed. In so doing, social
 choice theory reveals its provincialism. A Nobel prize or so, to give
 away, is not a proof. A theorem is only as good as the assumptions on
 which it is based. And theorem Arrow compares to a critique of a
 bicycle
 on the basis of the short-comings of a unicycle. It does not deal
 with
 the democratic necessity of a proportional count as well as an
 ordinal
 vote. Simple plurality is "maiorocracy" or the tyranny of the
 majority,
 as Mill and Lani Guinier said.

 It is not apparent what decisive argument the social choice school
 have
 that they can take to the voters, for whom elections are supposed
 to be
 meant, and has not been so for 70 years. It is not even apparent
 that,
 after 70 years, they have any idea of, or even belief in, a standard
 model of democratic election.

 Richard Lung.


 On 15/02/2024 07:13, Rob Lanphier wrote:

 recently

 think that

 there

 (<https://electionscience.org>)

 the late

 possible to

 trying

 past

 rounds

 applies to

 theorem

 applies to

 <https://en.wikipedia.org/wiki/Gibbard%E2%80%93Satterthwaite_theorem>

 semi-honest)

 theorem,[4] nor

 voting.

 claiming

 adage

 interpretations are

 (deterministic,

 (outside the

 voters to

 ballots" and

 evaluations,

 honest cardinal

 cardinal

 dishonest

 Condorcet-

 attention

 ballot #1234

 ballot #1234

 changes like

 their

 theorem"

 for list info


 ------------------------------

 Message: 3
 Date: Thu, 15 Feb 2024 18:48:22 +0100
 From: Kristofer Munsterhjelm <km_elmet@t-online.de>
 To: Rob Lanphier <roblan@gmail.com>,
 election-methods@lists.electorama.com
 Subject: Re: [EM] Impossibility on Wikipedia: Arrow, Gibbard, and
         Satterthwaite
 Message-ID: <3a9c9f20-0d6f-0206-bb48-10b5f335ea9d@t-online.de>
 Content-Type: text/plain; charset=UTF-8; format=flowed

 On 2024-02-15 08:13, Rob Lanphier wrote:

 their

 theorem"

 My understanding and opinion is this:

 You have three different "main" impossibility theorems:

 - Arrow's says that no deterministic reasonable ordinal voting method
 can pass IIA. This means that regardless of whether voters are
 honest or
 strategic, it's possible that A's win over B depends on not just how
 many voters prefer A to B, but also how many prefer X to Y. This
 is only
 for cardinal methods.

 - Gibbard-Satterthwaite says that no deterministic reasonable ordinal
 method is strategy-proof: there always exists at least one election
 where at least one voter has an incentive to adjust his preferences
 based on how others are voting.

 - Gibbard's theorem extends this to a much broader class of election
 methods that includes cardinal methods, thus also implying that no
 deterministic cardinal voting method is strategy-proof.

 (In particular, both of Gibbard's theorems are about strategy.)

 The part about the revelation principle is incorrect and seems to be
 using a very specific definition of honesty, inspired by Warren
 Smith.
 To my knowledge, what the revelation principle says is this:

 - Say that a participant in a mechanism employs strategy if the
 information he submits to the mechanism depends on the actions of the
 other participants or his belief about them.[1]

 - Say that a mechanism only uses honesty if no participant has an
 incentive to employ strategy.

 - Then, if there exists a mechanism where people employ strategy to
 drive it to an optimal or equilibrium outcome, then there also
 exists a
 mechanism that only uses honesty that reaches the same outcome or
 equilibrium.

 Consider it like this: suppose you're involved in a court case,
 and you
 hire a lawyer. You tell the lawyer the truth and the lawyer comes up
 with whatever strategy that will advance your interests, given the
 evidence and information about the other party. That's a system where
 you or your lawyer use strategy to drive the system to a
 particular state.

 But consider a hypothetical legal system using an AI judge. This
 AI has
 a lawyer interface to each party; upon hearing the truth from each
 party, it then simulates a court case the way it would proceed with
 virtual lawyers who employs strategy based on the honest information.
 The AI comes with a proof that your virtual lawyer won't incriminate
 you. You would then interact honestly with the system, represented by
 the judge, and it would strategize internally.

 Thus for any system that requires strategy to get an equilibrium,
 there
 exists another system where you can be honest. It just absorbs the
 "lawyer component" into itself.

 The problem is that there is no such equilibrium for deterministic
 voting methods. That's implied by Gibbard, because otherwise, you
 could
 create a strategy-proof method by first creating a method that
 invites a
 particular type of strategy, and then embodying a "lawyer component"
 into it to perform that strategy.

 If you try to do this, as far as I understand it, you get a
 nondeterministic method since the equilibrium is a mixed strategy.
 And,
 as we know, there exist strategy-proof nondeterministic methods,
 so that
 fits.

 This would be like: sometimes, your lawyer says "if we do this,
 then no
 matter what the other party does, we win". But other times he says
 "if
 we focus on these elements and the other party focuses on those,
 then we
 win". Like rock-paper-scissors, which strategy you should play
 depends
 on the strategy the other guy is going to use. So you play them at
 random in such a way that the other guy can't guess what you're
 doing.
 That gives a nondeterministic method.

 Okay.

 So now about IIA.

 The seeming advantage that cardinal methods have over ordinal ones is
 that they pass IIA. In Range, if A has score 100 and B has score 50,
 then A will continue to beat B even if we remove every other
 candidate.

 But I've always been of the opinion that this IIA compliance is
 either
 illusory or a distraction, because it doesn't answer what we
 really care
 about. And that is whether the presence of a candidate who doesn't
 win
 changes the outcome.

 Some cardinal proponents say that methods like Range have multiple
 honest ballots: there are many ways to vote that are all
 consistent with
 your preference ordering. But a voter has to choose which honest
 ballot
 to cast, and there's no externally fixed scale (what exactly does ten
 points mean? What does zero mean?).[2] Thus the selection of
 candidates
 who run will affect the scale, which means that some voters would
 change
 their ratings based on who's running - even if those additional
 candidates don't win. So these methods fail what we could call "de
 facto
 IIA", for lack of a better term.

 For instance, suppose the election starts off with two pro-democracy
 candidates. Then a number of authoritarians enter the race. It's
 likely
 that in Approval, some voters who would've approved of one of the
 pro-democracy candidates but not the other, would now approve both to
 mark their distaste for authoritarianism and keep the authoritarians
 from winning.

 So in my opinion, ordinal methods are merely honest about their
 limitations. Their logic says: "okay, I can't know if his 10/10 is
 the
 same as her 10/10 or her 5/10. I'll accept that this means I must
 fail
 IIA, instead of seeming to pass it by passing the buck to the voters
 that they must use a fixed scale that's not affected by who's in
 the race."

 So ordinal methods clearly fail IIA, and aren't strategy-proof (by
 Gibbard-Satterthwaite). Cardinal methods pass IIA (but it doesn't
 mean
 what one may think it means) and aren't strategy-proof (by Gibbard's
 theorem).

 Both ordinal and cardinal methods may pass de facto IIA for
 subsets of
 elections. E.g. Condorcet methods pass IIA as long as there is a CW,
 because adding a candidate either makes that candidate the new CW
 (hence
 he's not irrelevant) or the current winner stays a CW. Similarly,
 Approval passes de facto IIA with dichotomous preferences where every
 voter has a class of OK candidates and a class of not-OK
 candidates, and
 the boundary between OK and not OK doesn't depend on who's in the
 race.
 (Such voters may sometimes approve everybody or nobody.)

 But in general: both cardinal and ordinal methods are susceptible to
 strategy. And both cardinal and ordinal methods may have the winner
 change from A to B as a consequence of C entering the race.

 -km

 [1] Strictly speaking we would also want "honesty" to have some
 connotation of "being the actual information being asked for". Say
 you're dealing with a system that asks you what you like the least
 and
 then gives it to you. You would answer its question with a thing that
 you want to be given, so that answer stays the same no matter what
 other
 people interacting with it would say. So by my definition that
 wouldn't
 be strategy, but common-sense would say that it is not honest either.

 Warren's definition of honesty is somewhat based on this idea, but it
 goes too far in the other direction. It doesn't consider ballots
 where
 your ranking stays the same as under honesty but your scores
 don't, as
 being strategic. I think in part that's due to the difficulty in
 comparing utilities, but we *can* hold rated voting to a higher
 standard. Ask and I'll elaborate - this post is long enough :-)

 [2] As a side note: we probably can make *some* observations of other
 people's utilities even if we don't have a fixed scale. For
 instance, I
 can probably reason that a candidate who would put you in a prison
 camp
 would be a much worse choice from your perspective than one who would
 arrange a party; and that the difference in utilities would be much
 greater than say, between a candidate who holds a week-long party and
 one who holds a two-week long party.

 Some cardinal proponents also refer to von Neumann-Morgenstern
 utilities
 as a way of making comparisons between people's strength of
 preference:
 basically using lotteries to determine how much more a voter
 prefers one
 choice to another. But such scales still need to be normalized
 because
 they always have two unknown variables per voter. Methods that do the
 normalization so as to give each voter the same strength fail IIA.
 Not
 doing such renormalization can make the method pass IIA but they
 still
 don't pass "de facto IIA".

 See e.g.
 https://en.wikipedia.org/wiki/Von_Neumann%E2%80%93Morgenstern_utility_theorem#Incomparability_between_agents

 for the need for normalization.


 ------------------------------

 Subject: Digest Footer

 _______________________________________________
 Election-Methods mailing list
 Election-Methods@lists.electorama.com
 http://lists.electorama.com/listinfo.cgi/election-methods-electorama.com


 ------------------------------

 End of Election-Methods Digest, Vol 235, Issue 30
 *************************************************

Election-Methods mailing list - seehttps://electorama.com/em  for list info

On 2024-02-17 04:47, Closed Limelike Curves wrote:

To be more precise, anything (deterministic, passing unanimity, etc)
that satisfies IIA is non-ordinal.[1]

You can't really speak of "the Arrovian paradigm" because Arrow only
deals with ranked methods. You could define a broader paradigm of "what
we mean by election methods and voting", but it's possible that that
domain would cover methods that we don't know about yet, that use ballot
formats that are not cardinal as such, but that we don't know about
either. Arrow's theorem tells us nothing about non-ranked methods,
however they may work.

I'd like to use the favorite betrayal criterion analogy again.

Suppose there were a theorem that stated that in any voting method that
used single-mark ballots, sometimes voters would have an incentive to
vote dishonestly. Call it "Theorem X". In the context of single-mark
ballots, "dishonestly" would be someone stating that candidate X, not Y,
is his favorite, since "who's your favorite" is the honest expression
that the single-mark ballot asks for.

Suppose now that someone adds, to the Wikipedia article about this
theorem, that it doesn't apply to ranked voting because some ranked
voting methods pass the FBC and therefore allow voters to honestly state
who their favorite is.[2]

In my opinion, this leads to confusion about what honesty means and what
the theorems actually say. For each type of voting method, "honesty" is
naturally defined in the context of the statements that can be
expressed. Therefore they coincide with strategy immunity: a first
preference-only method is strategyproof iff it's strongly honest (in
first preferences). A ranked method is strategyproof iff it's strongly
honest (in ranks). A rated method is strategyproof iff it's strongly
honest (in ratings), etc.

Comparing a method with a broader domain (ranked vs first preferences)
introduces ambiguity into just what's meant by "honesty". Is it strategy
immunity or is it just "honesty in first preferences"?

There's a risk that cardinal proponents would use a sort of bait and
switch to talk about honesty in ranks while imparting the connotation
that rated methods are closer to strategy-proof than ranked ones. But we
can't say that rated methods are closer to strategy-proof than ranked
ones are, any more than we can say that ranked methods are closer to
strategy-proof than first preference only ones are due to the FBC,
because the very extension of the domain introduces new ways to be
strategic.

Even if cardinal proponents aren't that malicious, switching from
honesty within a domain to saying "methods working outside the domain
can be honest as defined within the domain" can lead to misunderstanding.

That's why I prefer to just say "the GS theorem doesn't apply to
cardinal methods" -- because it doesn't -- and then just say "Gibbard's
more general theorem does". That way there's no ambiguity about what the
kind of honesty that each theorem makes use of, actually means.

In each domain (first preference, ranked, rated) the Gibbardian honesty
in its own context just means "the expression or expressions that you
can make in this domain that is consistent with your honest opinion".

It doesn't imply IIA as such. But it is related to what I called "de
facto IIA" in my other post. My general idea would be something like this:

Suppose that candidate A is in the running. Then since your strategy
depends on how other voters vote, then it's possible that it depends on
what opinion the other voters express (how they rate, rank, etc) A. If A
has no chance of winning, and drops out, then it's possible that your
optimal strategy changes. You altering your optimal strategy can then
lead to someone else winning, which would be a de facto IIA violation.

For instance, suppose the method is approval voting. There are two
pro-democracy candidates (A and B) and an authoritarian (W). Lots of
people vote for both pro-democracy candidates to make sure the
authoritarian doesn't win, and some strategic voters vote for A alone,
reasoning that the {A, B} bloc is sufficiently in the lead that W has no
chance. As a result, A wins. Then W drops out. This leads the voters to
be more picky about whether they support A or B, and they vote for only
one of the two. As a result, B wins.

The "de facto IIA" failure is a consequence of the method leaving open
an opportunity for strategy: that the pro-democracy voters adjust their
vote depending on how many voters are voting for the authoritarian, or
how many of them they perceive to be so.

To boil it down: if the voters' strategy depend on how other voters are
rating/ranking/etc. a candidate who can't win, then the removal of that
candidate can change their strategy, and thus change who does win.

This is kind of a quick and dirty idea; it would need considerable
honing to be made rigorous. I don't know of any sources that have done
so, but they may exist.

For ranked methods, there exist proofs that go in the other direction,
proving Gibbard-Satterthwaite using IIA.

-km

[1] Either it restricts the voters from making some valid ordinal
expressions, or it asks for more information than just ordinal
preferences. That a Condorcet method passes IIA as long as a CW exists
is an example of the former; cardinal methods (and potentially other
things like auctions) are examples of the latter.

[2] The analogy is even more accurate than I first thought, because the
"weak FBC" (the FBC everybody talks about) is analogous to semi-honesty,
while the "strong FBC" is analogous to actual honesty, i.e. never rating
B over or equal to A when one's honest preference is A>B.

I suppose this is where we'd disagree; I'd say that adding this line to
the article is more likely to clear up confusion than create it. Every
time I bring up score voting's sincerity in the 3-candidate (or perfect
information, or zero-information) cases, I get people claiming that's
obviously impossible, because Gibbard-Satterthwaite says so.

The problem is if someone says "Here's Gibbard-Satterthwaite; by the
way, it doesn't apply to cardinal methods, but Gibbard does," it gives
the mistaken impression that Gibbard-Satterthwaite and Gibbard's theorem
are proving the same result, just in two different domains. (Thus why
there was a lot of confusion about merging the two articles in earlier
discussions, and people mistaking the two.) In reality the concept of
honesty in Gibbard is different (and stricter) than the concept of
honesty in Gibbard-Satterthwaite.

A counterexample would be nice instead, then, since I'd conjectured any
system that isn't strategyproof would have a "de facto IIA" failure.