[EM] Trying to get at the Condorcification proof

[Kevin Venzke]

Hi Kristofer,

Le mercredi 28 juin 2023 à 19:42:00 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?

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

Ok, I see.

> >> 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:
[omitting results]
> 
> 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.)

This is an interesting argument. I think my result may be an artifact of the fact
that I require the improvement in the result to be achieved by a single bloc of
like-minded voters. This should mean that the compromise incentive will appear to
be lower if it's less likely that a single bloc can effect the change.

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

In my simulation code, ties are handled by issuing a sort of die roll outcome to
each candidate, and any ties (during the method or at the very end, however
needed) are broken with this. Then, when checking for changes in the winner
resulting from vote changes, the die rolls must stay the same, so that we can be
sure that result changes are due to the vote change.

(This approach isn't clone-proof, and has the implication that no tie rate can be
reported, short of adding debug code to a specific method, or cloning the method
into a copy that uses a different tiebreaker.)

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

I think Warren did express such an opinion, though I don't think it was based on
any simulations.

One can interpret WV as a heuristic to gauge which voters are capable of changing
the outcome if they aren't happy with it.

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

If I understand these requirements:
1. absolute Condorcet = Condorcet(gross) = must elect a candidate with a full
majority over every other candidate
2. weak FBC
3. Plurality (the arguable problem with MMPO bad examples)

MAMPO, ICA, and MaxMin(PS) satisfy these off the top of my head. If some
Plurality failures are actually allowed, then MDDA too.

Over the past decade I've thought about other ways of doing CCE. An advantage of
basing it on plain Condorcet is that it's relatively decisive. An FBC-compatible
version would be interesting though.

What's completely missing is a weak FBC method that satisfies Plurality and
doesn't have much truncation incentive.

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

That criterion sounds like it would inherently create compromise incentive,
because if A is an unviable trash candidate who pairwise beats B, then B also
cannot be allowed to win. So A>B>? voters could have compromise incentive.

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

Well, without ER or truncation, a cyclical compromise incentive is what we
expect from any cycle. So you've identified the limit of how good a Condorcet
method can be in that environment, I guess. But with ER or truncation, we can
definitely do better, because the cyclical compromising isn't always inevitable.
So I guess the endeavor only fails to the extent that we can't figure out how
good a method can be.

Possibly I misunderstand what the endeavor is.

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

But MaxMin(PS) does satisfy that, so that's not a very demanding standard.

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

I think the situation is not that full-rank resistance is being sacrificed, but
that full-rank resistance, at its best that can be achieved, is not really that
good.

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

Yes, I would think so in that case.

Kevin
votingmethods.net