[EM] Trying to get at the Condorcification proof

[Kevin Venzke]

Hi Kristofer,

Le lundi 26 juin 2023 à 11:44:39 UTC−5, Kristofer Munsterhjelm <km_elmet at t-online.de> a écrit :
> Suppose that honest election E (without truncation or equal rank) has a
> CW and the method elects him. Then there shouldn't be any compromise
> incentive, right?

Right, if the sincere CW was also voted CW and that's why the method elects him.

> Argue like this: Suppose some manipulators want to make X instead of the
> CW, W, win. By the definition of a CW, a majority prefers W to X. Even
> if the people remaining who prefer X to W were to raise X, this wouldn't
> affect the magnitude of W>A for any A: not A != X because only X is
> being raised, and not W>X because they all vote for X>W already.
> 
> So if compromising consists of raising someone you prefer to the current
> winner to make that someone win, then when there's a CW, Condorcet
> methods are immune to compromising.
> 
> We already know that every InfMC method is vulnerable to compromising
> when there's a cycle.
> 
> So this means that, ties and equal-rank/truncation notwithstanding,
> Condorcet methods are vulnerable to compromising iff the honest election
> is a cycle.

By "honest election" you mean the sincere preferences? What about the scenario where only
the cast ballots have a cycle?

> And that would explain why the compromise vulnerability rate for all
> Condorcet methods seem to be so similar! I'm still getting somewhat
> different results for different Condorcet methods in my simulator, but
> after a more thorough investigation, I found out that's due to different
> methods tying in different scenarios, and I don't yet handle ties.

To my surprise, I can mostly confirm this result in this setting, that all the rankings are
complete. Condorcet methods have similar compromise performance and beat all methods that
aren't identical to a Condorcet method. With three candidates, Condorcet methods hardly
differ at all.

With four candidates, I see a few tiers. Repeatedly excluding the candidates with the most
last preferences (on the original ballots) until there is a CW, seems to be the best by a
small amount. MinMax-likes come second. Then there's everything else, with the Stensholt
generalizations placing last. (The best non-Condorcet method is my CdlA method, but we can't
call it competitive here.)

> Let's take that a bit further. As usual, I'm considering only full
> ranked methods; allowing equal-rank and truncation may make matters more
> complex:

Understood, though I would say that the latter definitely seems true. If the defeats in a
Condorcet cycle aren't all backed by a full majority, it's not clear whether it's actually
possible to have an unending process of voters using compromise strategy to make each
candidate win in turn. There may be resolutions to scenarios that don't open up any new
compromise opportunity. (This is the idea behind my /cce calculator, basically.)

Consequently, with truncation allowed, I don't see that all Condorcet methods do just as
well, or are better than all other methods, in regard to compromise incentive.

> Every InfMC method is susceptible to strategy (namely compromising) when
> there's a Condorcet cycle. If the InfMC method doesn't pass Condorcet,
> it's also susceptible to compromising when it fails to elect the CW. A
> method that passes Condorcet may still be vulnerable to some strategy
> when it elects the CW, but that strategy isn't compromising.
> 
> Thus, among InfMC methods, Condorcet methods minimize the susceptibility
> to compromising strategy.

Sounds right.

> Weak FBC methods seem to do better than this by explicitly failing
> Condorcet (since Condorcet and FBC are incompatible). However, these use
> equal rank and truncation (MMPO, implicit approval methods), go beyond
> universal domain (Range) or fail InfMC (Antiplurality and other methods
> considering the first two ranks equal).
>
> Strong FBC methods fail InfMC. This seems to square with Alex Small's
> results (https://arxiv.org/abs/1008.4331). (Following this line of
> thought may suggest ideas of something that implies Absolute Condorcet,
> but that allows for FBC with equal rank etc.)

I didn't know that paper was there. I think I'll link to it given the MDDA discussion.

I would note in passing that methods that satisfy weak FBC aren't necessarily great at
strong FBC, which is what I normally understand by compromise incentive. The most egregious
example is MaxMin(PS): it satisfies weak FBC but is one of the worst methods at strong FBC.

> Now consider a designer trying to create an InfMC method minimizing the
> number of strategically manipulable elections. He can't lock himself out
> of a minimal solution by requiring Condorcet, so suppose the method
> always elects CWs.
> 
> Then elections with cycles are already lost - they're manipulable no
> matter what. Hence if all that counts is the number of manipulable
> elections (and not, say, how many ways an election can be manipulated),
> then he only needs to look at the cases where:
> 
> - There was a CW
> - but then after manipulation, there's a cycle, and the strategists'
> preferred candidate wins.
> 
> This because a faction preferring X to the honest Condorcet winner W
> can't unliaterally make X a new CW; and elections with honest cycles are
> already manipulable.
> 
> This might make designing a >3 candidate strategy resistant method
> easier, as we only need to consider the faces separating the CW regions
> from the cycle regions, not the internal behavior in the cycle regions
> or the faces between them.

It's an interesting question. I start to feel that the challenge is completely different
based on whether or not truncation is allowed.

Kevin
votingmethods.net