[EM] Duncan results, let's try that again

[Kristofer Munsterhjelm]

As I read the proposal a bit too quickly, I initially thought that 
Duncan was CTE-Borda, so I wrote a post about its results. But I see 
that I was wrong, and it's actually:

> Duncan Definition:
>
> In the vast majority of the cases ... those in which the pairwise
> counts of the ballots unambiguously identify the candidate that
> pairbeats each of the others ... elect that candidate.
>
> Otherwise, elect the highest score candidate that pairbeats every
> candidate with lower score.

My implementation of this method is as follows:

Let a candidate's score be the number of candidates ranked strictly 
below him according to the base method's social ordering, if that 
candidate pairwise beats all of them.

Otherwise, let the candidate's score be -1.

Highest score wins. (Equal scores imply ties.)

What my simulator calls "Beat Chain[X]" is this method with X being the 
base method. "Smith//Beat Chain[X]" is the version restricted to the 
Smith set. So Forest's initial definition of Duncan is Beat 
Chain[Borda], and Mike's Smith restriction is Smith//Beat Chain[Borda].

My results are broadly the same as CTE: okay burial resistance with few 
voters, increasing to very good burial resistance with lots of voters, 
but at the cost of not particularly good total strategy susceptibility, 
approaching unity as the number of voters increases.

There's a caveat - my simulator checks burial resistance by every A>W 
voter ranking W last. If the method is nonmonotone, which the Duncan 
variants most likely are[1], then it may be possible to win using 
partial burial but not complete burial, e.g. if W is the winner, and 
honest is A>W>C>D, it's possible that A>C>W>D changes the winner from W 
to A, but A>C>D>W doesn't. My simulator won't catch that (yet), so 
burial numbers for nonmonotone methods may be lower than their real 
susceptibility. A similar caveat holds for compromising.

And here are my preliminary results:

Impartial culture, 3 candidates, 13 voters, 50k elections, 32k tests per 
election:

Beat Chain-[Borda]:

Ties: 0.1063 (5315)
Of the non-ties:

Burial, no compromise:	10923	0.244444
Compromise, no burial:	8282	0.185342
Burial and compromise:	2309	0.0516728
Two-sided:		4942	0.110596
Other coalition strats:	7850	0.175674
==========================================
Manipulable elections:	34306	0.76773

Smith//Beat Chain-[Borda]:

Ties: 0.02204 (1102)
Of the non-ties:

Burial, no compromise:	11917	0.243711
Compromise, no burial:	2720	0.055626
Burial and compromise:	281	0.00574666
Two-sided:		4361	0.0891857
Other coalition strats:	14168	0.289746
==========================================
Manipulable elections:	33447	0.684016

(For comparison, Schulze is manipulable 54% of the time, although the 
vast majority of that is burial.)

Impartial culture, 3 candidates, 97 voters, 50k elections, 32k tests per 
election:

Beat Chain-[Borda]:

Ties: 0.04154 (2077)
Of the non-ties:

Burial, no compromise:	2376	0.0495795
Compromise, no burial:	6919	0.144377
Burial and compromise:	130	0.00271268
Two-sided:		2979	0.0621622
Other coalition strats:	35466	0.740062
==========================================
Manipulable elections:	47870	0.998894

Smith//Beat Chain-[Borda]:

Ties: 0.00904 (452)
Of the non-ties:

Burial, no compromise:	2484	0.0501332
Compromise, no burial:	3897	0.078651
Burial and compromise:	15	0.000302737
Two-sided:		3202	0.0646242
Other coalition strats:	39908	0.805441
==========================================
Manipulable elections:	49506	0.999152

(For comparison, fpA-fpC is manipulable 17.2% of the time, and 
Smith//IRV 15.9% of the time. The latter also has a lower burial rate, 
subject to the caveat. fpA-fpC's burial rate is 0.068.)

Impartial culture, 5 candidates, 97 voters, 50k elections, 32k tests per 
election:

Beat Chain-[Borda]:

Ties: 0.03454 (1727)
Of the non-ties:

Burial, no compromise:	287	0.00594535
Compromise, no burial:	8188	0.169619
Burial and compromise:	5017	0.10393
Two-sided:		403	0.00834835
Other coalition strats:	34378	0.712158
==========================================
Manipulable elections:	48273	1

Smith//Beat Chain-[Borda]:

Ties: 0.02046 (1023)
Of the non-ties:

Burial, no compromise:	310	0.0063295
Compromise, no burial:	9887	0.20187
Burial and compromise:	1519	0.0310146
Two-sided:		478	0.00975968
Other coalition strats:	36783	0.751026
==========================================
Manipulable elections:	48977	1

I think the methods (CTE and Duncan) reveal something new: that even 
with Condorcet, we can have very low burial rates in the limit for 
impartial culture. However, the methods exact a very high price -- too 
high for my liking.

In a no-truncation setting like this, it appears that some level of 
compromise strategy is inevitable. And it also seems like some other 
strategy must be allowed (see e.g. fpA-fpC for three candidates). It 
might be possible to shift the majority of this required additional 
susceptibility over to coalitional strategy without having to pay the 
kind of heavy price that these methods require. Perhaps it's even 
possible while retaining monotonicity. But I don't know of any methods 
that accomplish that.

-km

[1] Suppose that the Borda order is A>B>C with an A>B>C>A cycle so that 
and B wins. Then if B is raised, turning the Borda order to B>A>C, then 
that should make C win instead.