[EM] Trying to get at the Condorcification proof

[Kristofer Munsterhjelm]

On 6/27/23 05:30, Kevin Venzke wrote:
> Hi Kristofer,
> 
> Le lundi 26 juin 2023 à 11:44:39 UTC−5, Kristofer Munsterhjelm <km_elmet at t-online.de> a écrit :

>> 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?

The strategy model I had in mind is like this:

Suppose that election E is honest, i.e. is the result of sincere 
preferences. If one or more voters can change the outcome according to 
election M to something they prefer, then E is manipulable under M.

So we just assume that E is the result of sincere preferences, then see 
if anyone can benefit from deviating from their hypothetical sincere 
preferences.

When method M is used to call elections, if E is manipulable, the method 
might never see E at all, just the manipulated ballot (if E is 
manipulable under M and the strategy is actually possible to pull off). 
The idea is that if we minimize the number of elections where some kind 
of strategy can work, that would discourage people from trying that 
strategy as there would be little to gain.

If the sincere preferences don't have a cycle but the cast ballots do, 
then (if the method is Condorcet) whatever strategy the manipulators 
made use of to create a cycle was probably not compromising. That's all 
that I was saying here, really :-)

"If the manipulated election has a cycle then either there was no 
compromising strategy or the corresponding election before any strategy 
was done had a cycle too" would be another way to put it.

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

That's surprising. When the methods have no ties, I tend to get similar 
results even with a higher number of candidates. Here's an example with 
5 candidates and 97 voters, impartial culture, and 50 000 honest 
elections tested for each method:

Smith,IRV:

Ties: 0 (0)
Of the non-ties:

(Fraction of elections with incentive for...)
Burial, no compromise: 0.06968
Compromise, no burial: 0.24974
Burial and compromise: 0.00062	(either strategy works)
Two-sided: 6e-05		(neither alone, but doing both works)
Other coalitional strategy: 0.03006

I.e. the total fraction with compromise incentive is 0.25036; 25% of the 
elections tested. I'm roughly guessing the c.i. is around 1%.

Ranked pairs(wv):

Ties: 0 (0)
Of the non-ties:

Burial, no compromise: 0.55816
Compromise, no burial: 0.05254
Burial and compromise: 0.19468
Two-sided: 0.18942
Other coalitional strategy: 0.00072

(i.e. total compromise incentive: 0.24722; rounding off to 1% gives 25% 
again.)

Strictly speaking, the tiebreakers I use are not anonymous, but I don't 
think that it should have an effect. But when ties exist, they can cause 
a non-uniform sampling effect, e.g. here is Schulze:

Ties: 0.0774 (3870)
Of the non-ties:

Burial, no compromise: 0.388251
Compromise, no burial: 0.0898764
Burial and compromise: 0.0943421
Two-sided: 0.423369
Other coalitional strategy: 2.16779e-05

Here it seems like the total is 18%. However, this is, as far as I 
understand from my program, due to the vast majority of Schulze's ties 
happening when there's a cycle, thus depressing the numbers.

Suppose that every tie is a cycle, and that cycles are subject to 
compromise. There are 3870 of them. In addition there are (0.0898764 + 
0.0943421)*(50000-3870) = 8498 elections we already know are vulnerable 
to compromise. The total is 12368, and 12368/50000 = 0.247, which is 
again 25% when rounding off to 1%. There may be some true ties that are 
actual true ties, not cycles, but this rough calculation seems to get us 
in the right ballpark.

(A simple way of checking this is to add some code to print out if 
there's both compromise incentive and a CW, or neither. It should never 
print anything if the assumption above holds.)

Maybe this isn't really fair. I discard ties because I first wrote the 
strategy code to find methods that weren't susceptible to strategy, and 
it would otherwise just find the trivial method that ties all the time. 
But one could argue that I can't just assume what I'm trying to prove 
and say "it seems right" when assuming all ties are cycles and cycles 
are all subject to compromise. So to do this properly I probably should 
update my code to handle ties, but what educated guesses I could make 
seem to already point in the right direction.

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

That makes sense. I think I recall Warren saying that wv is more 
strategy resistant than margins.

There are three possible ways to explore this further; any for which it 
would be pretty nice to get some systematic results:

- Try to find a general pattern for methods that pass absolute Condorcet 
but pass e.g. weak FBC when truncation and equal rank are allowed 
(things like MMPO, but without its bad-example). A /cce based on 
absolute Condorcet instead of just plain Condorcet, sort of. This might 
require some property about when equal-first compromising works for 
methods (similar to what InfMC does wrt absolute Condorcet), and then 
similarly extending the Condorcet relation to do a DSV-like automatic 
election like in the InfMC proof.

- Generalize InfMC, e.g. something like "If all voters not in set V are 
indifferent to A and B, and the method elects one of them, then a 
majority of the voters in V can decide which one it will be by modifying 
their ballots". (I think fractional IRV passes this?? At least Range 
does) Then perhaps an analogous proof could construct a condition that's 
sufficient for minimal compromising incentive among all methods passing 
this criterion.

- Find out if such an endeavor is bound to fail (e.g. cyclical 
compromising that you mentioned).

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

That's a good point. Maybe requiring that the method passes (absolute) 
Condorcet when everybody fully ranks would keep strong FBC violations in 
check, as we'd then be building on a foundation we know works.

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

I've kind of been hoping that the optimal for full rank would give some 
hints to what shape the optimal with truncation and equal rank would 
have. Kind of how looking at part of a picture lets you find out what 
the rest is. But it's definitely possible that you can't have it both 
ways and that something that's good at dealing with equal-rank and 
truncation has to sacrifice some full-rank resistance to do so ... in 
which case it's the best method with equal rank and truncation that we'd 
want to find. Or at least a good one.

-km