[EM] Defensive strategy for Condorcet methods KM

[Kristofer Munsterhjelm]

Kevin Venzke wrote:
> Hi Kristofer,
> 
> --- En date de : Mer 15.6.11, Kristofer Munsterhjelm <km_elmet at lavabit.com> a écrit :
>>> I guess that anything else that does something similar
>> would have a
>>> similar advantage.
>> FPC has some problems, though, as Jameson Quinn pointed
>> out. It is possible to reduce the compromise incentive by
>> doing something like Schwartz//FPC (as you'd have to know
>> who would be in the cycle), but then it's no longer
>> summable. Note that Schwartz,FPC doesn't reduce the
>> compromise incentive as much.
>>
>> So let's consider what properties a base method must
>> satisfy. Say we have X, Y, and Z. Y is the CW, and X voters
>> want to bury Y so that X>Y>Z>X in that order of
>> strength. If they accomplish this, Y will be beaten by X and
>> Z, so the property should be:
>>
>> Voters who vote Y below top must not be able to increase
>> the scores of X and Z by burying Y.
>>
>> Or, a weaker criterion:
>>
>> A ballot that ranks Y last must not decrease the points
>> given to the candidates still ahead of Y if Y is raised.
>> (This is just considering from the reverse situation,
>> "after" the burial, wrt before the burial.)
> 
> I am not sure I am able to follow this. In the first paragraph, if Y
> is the CW, you can't have an X>Y>Z>X cycle created by X voters. I guess
> you surely mean X>Z>Y>X. And then the rest of your description is
> assuming we're using the penalty point idea. I will try to think about
> this later.

Oops. Yes, that's true. It's a bit hard going through the logic, so I 
made a mistake. (If the X-voters could make X>Y they would just do so 
directly and then it would already have been X>Y before the burial 
happened.)

And yes, I'm considering the penalty point idea in particular. If we 
have an X>Z>Y>X cycle, then X is beaten by Y and Z, Y is beaten by X and 
Z, and Z is beaten by X and Y.

Say that X's FPP (base method) score is f(X). Then we'd ideally want 
that, despite the burial, f(Y) + f(Z) > f(X) + f(Y), i.e. that X's 
penalty is greater than Y's. This means that either Z's penalty is 
greater than Y (in which case Y still wins), or not (in which case Z 
wins, which means the burial backfires). We can remove the f(Y) from 
both sides to show that f(Z) > f(X).

So if X-voters bury Y, this should still make Z's FPP (or whatever) 
score be greater than X's. The only way X-voters can bury Y in a three 
candidate case is to go from X>Y>Z to X>Z>Y. So we want a method where 
doing so doesn't increase X's score relative to Y. FPP is such a method, 
but I can't think of much else where that is the case.

(If f(Z) < f(X) even before the burial, then engineering a cycle will 
work and there's nothing we can do about it. That is, burying in favor 
of the FPP winner will work.)

I think that's right. I tried to reason it out more slowly.

..

Or thinking about it again, what we really want is that either f(Y) + 
f(Z) > f(X) + f(Y) or f(Y) + f(Z) > f(X) + f(Z), because if the burial 
makes Z win, that makes the burial pointless. However, we prefer the 
former case because that blocks the burial outright, whereas the second 
case could be one where everybody buries and then the unwanted candidate 
Z wins. My earlier logic failed to account for the situation where 
burial makes Z win above X above Y.

So, we would prefer burial to keep f(Z) > f(X), but failing that, it 
should then have f(Y) > f(X).

>> Any ideas as to which methods could be used?
> 
> This may have nothing to do with what you propose, but if we talk about
> anti-burial Condorcet methods I think we should not forget methods like
> TACC, Condorcet//IRV, and also Condorcet//King of the Hill.
> 
> I'm short time and my memory isn't quite perfect. But in TACC it seemed
> to me that the anti-burial property was that you needed to be able
> to predict the approval order both pre- and post-burial, or it wouldn't
> work right. I'm going to kick myself if this is wrong, but I think it
> was defined (for 3 candidates) as electing the one who defeated the
> approval loser. It smells non-monotonic but I don't think it is.
> 
> With C//KOTH the B:C contest (where B is sincere CW and C is pawn) is 
> not regarded at all (in a cycle). If there is an A:B or A:C full 
> majority, it's over. Otherwise, burial by A voters succeeds.


>> Yet some Condorcet methods resist strategy better than
>> others. In particular, certain nonmonotone methods seem to
>> do so well. Maybe this involves the risk of the burial going
>> badly - if it's chaotic (not monotone), the buriers won't
>> know when it could backfire and when it couldn't. Not so
>> sure about that, either.
> 
> I'd be curious if you have anything in mind besides C//IRV and the
> penalty point system. It's interesting to consider what commonalities
> there may be.

I haven't tested FPC (since my reimplementation of JGA's strategy ideas 
was done before I moved to a more modular design for Quadelect), but as 
far as I recall, the really standout systems as far as strategy was 
concerned, were Condorcet-IRV hybrids (C//IRV, Smith,IRV, Smith//IRV, 
but interestingly not Landau//IRV or Landau,IRV). Next to those, at some 
distance, was a sorta-system that's like Ranked Pairs, only in that 
winners are ranked above losers in the sorted order and otherwise the 
order is fixed, so the system isn't neutral.
("Winners are ranked above losers" means that if A beat B, A>B is 
reached before B>A.)
That method is a worst-case (I think) estimate for Ranked Pairs-type 
methods. Making the sorting order depend on, say, the winner's FPP 
score, could be interesting, but I don't think that would be monotone 
(but hey, let's try to find burial resistance before we find monotone 
burial resistance :-)

I also read a paper about trying to find the method that would minimize 
burial opportunities. It reached the conclusion that in the three 
candidate case, one should elect the candidate that beat the FPP winner. 
The author further said that he didn't know how to generalize it beyond 
three candidates.
I think it was this one: 
http://www.nhh.no/Admin/Public/DWSDownload.aspx?File=%2FFiles%2FFiler%2Finstitutter%2Ffor%2Fdp%2F2008%2F1108.pdf
"Condorcet Methods - When, Why and How? ".

And from your other mail:

> Also am I mistaken or is FPC with three candidates identical to C//IRV?
> The candidate with the lowest penalty is going to be the one who is
> defeated by the "FPL." If you were to eliminate the FPL, the candidate
> with the best FPC score would beat the remaining candidate.

Hm, let's see. The three candidates are A, B, and C, and they're in a 
cycle. Say that C is the candidate with the least first place votes. In 
other words, f(A) + f(B) > f(A) + f(C) and f(A) + f(B) > f(B) + f(C), 
since f(A) + f(B) + f(C) sums to the number of voters, which is a 
constant for each election.

A's penalty is f(B) + f(C).
B's penalty is f(A) + f(C).
C's penalty if f(A) + f(B).

By the above, C's penalty is greater than either of the others'. So C 
can't be the winner. Thus C can be disregarded, and

A's penalty is f(B) + f(C),
B's penalty is f(A) + f(C),

since we're dealing with A vs B, we can remove f(C), so A wins if f(B) < 
f(A) and vice versa, i.e. A wins if he has more FPP votes than B. So it 
would seem similar, but it may not be quite the same.

In IRV, the C-first voters' votes get included in the the second round. 
However, in FPC, they don't, except to the extent they influence which 
direction the cycle goes. But in a three candidate case, each candidate 
is beaten by both of the two others.

So, perhaps something like this will give different results for IRV 
(C//IRV assuming cycle) and FPC:

x: A>B>C
y: B>C>A
z: C>A>B

where z is significantly large to tip the second IRV round to A, but 
where we have x < z, y < z (so C is the FPP loser), y > x (so B wins by 
first preferences), i.e.

y > x > z  (so B wins by FPP)
(z+x) > y  (so A would win in IRV)

and the right sort of cycle. Or maybe this is impossible. I can't quite 
calculate it.