[EM] Trying to get at the Condorcification proof

[Kristofer Munsterhjelm]

On 6/26/23 01:33, Forest Simmons wrote:
> Thanks for your thought provoking insights!

Here are a few more:

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?

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.

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.

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:

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.

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

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.

> I think the analysis is based on all rational voters with complete 
> information, but the reality in public elections is near complete 
> disinformation ... along with high levels of irrationality.
> 
> Which makes DSV design more of an art than a science.
> 
> We're talking of DSV in a general sense that is broad enough to treat 
> Instant Runoff as a DSV method for transferring votes in a  runoff, 
> which is already a DSV system for deciding where their one and only 
> Plurality vote will go, for example.
> 
> One takeaway for me is that Condorcet, M is a mild constraint on method 
> M manipulators, because under complete information, they supposedly 
> already know all of the sincere preferences including who the sincere CW 
> is if there is one. The constrained system pins them down to some 
> deterministic CW that (under game theoretic omniscience) is known to all 
> of the sophisticated players ... taking away from the advantage of 
> stochastic strategies with  less constrained entropy ... strategies that 
> would otherwise be open to them to get a little more advantage over 
> their unsophisticated compatriots.

I agree. The DSV interpretation of Condorcet,M is essentially "in the 
very worst case, the strategists know how everybody else will vote; how 
can the method make it pointless for them to strategize?"

Chess engines don't do opponent modeling since they can beat players 
even without it. Similarly, this maximally pessimal type of DSV idea 
says that if we can make something immune to a particular strategy even 
under omniscience, then we don't need to care about imperfect 
information, game dynamics, etc.

A more realistic way of looking at omniscience strategy might be regret 
after the election. If everybody votes, then X wins, then the voting 
data is published and people who preferred Y find out they could've won 
if they had all compromised for Y instead... they might feel like they 
were cheated out of the result. Or they might defensively compromise all 
the time, leading to Duverger-type dynamics.

-km