[EM] Election-Methods Digest, Vol 235, Issue 30

[Kristofer Munsterhjelm]

On 2024-02-17 04:47, Closed Limelike Curves wrote:
> 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.

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.

>   * *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.

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".

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

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.