[EM] Simulations considering competitiveness of nomination

[Kevin Venzke]

Hi,

Well, yesterday I spent a lot of time studying generally how things were
working. One notable thing I observed was that in a 1D centrist scenario,
Approval and Range would overselect the centrist (elect him even when he
is not best) while truncated Condorcet methods would underselect him.
The obvious explanation for the latter is that the voters were not 
"approving" him, but since ApprPoll uses the same cutoff, that doesn't
work: What seems to be the case is that, when voters truncate at 
(approval poll-based) expectation, respecting sub-majority defeats isn't
just less important than respecting majority defeats, it seems to be
harmful.

So I spent a lot of time thinking about what methods could be a "Bucklin
killer" or "DAC killer" (as these methods pick the centrist in the correct
scenarios). I implemented my old MDDA and MAMPO methods and was promptly
disappointed. I added in MAFP (Bucklin where you tie-break based on the
previous rank's count) and also newly named MARO1 and MARO2, which are
more promising.

"MARO" stands for "Majority Approval Runoff." The idea is if the top two
approval candidates have majority approval, there is a pairwise contest.
(As a real method you might limit qualification to the top three on first
preferences, to avoid the obvious way to abuse this method.) With MARO1 
the contest is decided on the ballot as truncated. With MARO2 all 
preferences are used, so either a second round is being held, or voters 
are allowed to rank beneath the approval cutoff.

(I had also, earlier, implemented Chris' new IBIFA method, which will
show up below as well.)

After this I got to working on my simulations that consider 
competitiveness of nomination, which seem to change the game a bit and
make me a bit more optimistic that the method to beat may not be Bucklin.

The idea is that usually candidates in reality are nominated in an attempt
to be competitive. Most randomly generated candidate allocations are not
very competitive. As I would prefer to simulate realistic elections, it
seems reasonable to try removing scenarios where one candidate wins a
high percentage of the time under a given method.

The stats I have put together are for one- and two-dimensional random
scenarios, limited to the most viable candidate winning within 65%, 55%,
and 45% of the elections in that scenario.

To begin with I'll note that the likelihood of a scenario being 
competitive doesn't vary all that much from method to method, and it's
not clear to me what variation means anyway. Generally the truncated
Condorcet methods admit the most scenarios as competitive, and Range
and Approval the fewest, sometimes even fewer than the method that 
magically picks the best winner.

Just a few stats on this: Of all 2D scenarios within the 65% threshold
for *some* method, MMPO is in this threshold 79% of the time, MMWV 71%,
IRV 63%, Bucklin 55%, Approval and Range 46-50%, magic BEST method 47%.

So, here are the average distances for 1D and 2D regarding only the
<65% scenarios for that method.

Dims	Rank	Method	Avg Dist	Avg Norm Dist
1	1	BEST	51.43	0.00
1	2	MMstrict	52.26	1.79
1	3	MARO2	52.26	1.79
1	4	MAP	52.26	1.79
1	5	MDDA	52.48	2.06
1	6	Bucklin	52.49	2.05
1	7	DAC	52.50	2.14
1	8	MAMPO	52.58	2.41
1	9	MARO1	52.65	2.63
1	10	MAFP	52.66	2.69
1	11	CdlA	52.83	4.25
1	12	IBIFA	52.84	4.25
1	13	QR	52.98	4.32
1	14	RangeNS	53.15	3.07
1	15	MMWV	53.16	5.07
1	16	C//A	53.17	5.07
1	17	SMDTR	53.21	5.21
1	18	DSC	53.31	3.99
1	19	2sMMPO	53.49	2.83
1	20	ApprPoll	53.49	2.83
1	21	MMmarg	53.91	7.06
1	22	IRV	54.10	6.76
1	23	Raynaud	54.60	9.38
1	24	MMPO	54.61	9.37
1	25	SPST	54.61	6.91
1	26	ApprZIS	54.70	3.01
1	27	VFA	55.81	9.42
1	28	WORST	77.76	100.00
2	1	BEST	114.46	0.00
2	2	RangeNS	116.09	3.71
2	3	MMstrict	116.23	5.64
2	4	MARO2	116.30	5.36
2	5	MARO1	116.37	5.62
2	6	MAFP	116.38	5.69
2	7	DSC	116.41	6.50
2	8	MDDA	116.47	5.51
2	9	DAC	116.48	5.29
2	10	MAMPO	116.49	5.70
2	11	Bucklin	116.50	5.33
2	12	IBIFA	116.54	6.48
2	13	MAP	116.59	7.07
2	14	QR	116.66	6.75
2	15	C//A	116.69	7.11
2	16	CdlA	116.69	6.89
2	17	MMWV	116.72	7.40
2	18	SMDTR	116.78	7.44
2	19	MMmarg	116.79	7.80
2	20	ApprPoll	116.82	5.61
2	21	IRV	116.83	7.46
2	22	ApprZIS	117.12	5.26
2	23	Raynaud	117.18	9.00
2	24	SPST	117.26	8.57
2	25	VFA	117.60	9.32
2	26	MMPO	118.15	11.45
2	27	2sMMPO	120.03	14.68
2	28	WORST	149.97	100.00

Perhaps not that surprising. It shows that the new methods I added can
be competitive with Bucklin. Approval has fallen in the rankings quite
a bit in the 2D case.

So, let's look at "very close" races where the most viable candidate is
winning within 55% of the elections:

Dims	Rank	Method	Avg Dist	Avg Norm Dist
1	1	BEST	50.35	0.00
1	2	MMstrict	51.30	1.66
1	3	MARO2	51.30	1.66
1	4	MAP	51.30	1.66
1	5	MAFP	51.93	2.81
1	6	MARO1	52.00	2.78
1	7	DAC	52.06	2.22
1	8	MAMPO	52.09	2.50
1	9	QR	52.12	4.70
1	10	DSC	52.12	4.04
1	11	IBIFA	52.21	4.48
1	12	CdlA	52.22	4.48
1	13	Bucklin	52.29	2.13
1	14	MDDA	52.32	2.16
1	15	MMWV	52.38	5.46
1	16	C//A	52.38	5.47
1	17	SMDTR	52.39	5.63
1	18	RangeNS	52.61	2.95
1	19	MMmarg	53.41	7.91
1	20	IRV	53.49	7.56
1	21	SPST	53.64	7.35
1	22	MMPO	54.27	10.71
1	23	Raynaud	54.32	10.72
1	24	ApprPoll	54.33	3.21
1	25	2sMMPO	54.33	3.21
1	26	ApprZIS	55.11	3.24
1	27	VFA	55.52	10.41
1	28	WORST	77.96	100.00
2	1	BEST	114.86	0.00
2	2	SMDTR	117.04	8.15
2	3	IBIFA	117.12	6.98
2	4	C//A	117.21	7.64
2	5	DSC	117.25	6.89
2	6	CdlA	117.27	7.41
2	7	MMWV	117.29	7.95
2	8	MARO2	117.30	5.74
2	9	MMstrict	117.36	6.24
2	10	MAP	117.45	8.08
2	11	MAFP	117.47	6.21
2	12	MMmarg	117.48	8.37
2	13	MARO1	117.49	6.09
2	14	QR	117.51	7.44
2	15	MAMPO	117.59	6.17
2	16	RangeNS	117.61	3.82
2	17	Bucklin	117.65	5.80
2	18	DAC	117.66	5.79
2	19	SPST	117.67	9.20
2	20	IRV	117.72	8.31
2	21	Raynaud	117.86	9.64
2	22	MDDA	117.88	5.92
2	23	VFA	118.01	10.11
2	24	ApprZIS	118.29	5.71
2	25	ApprPoll	118.52	6.03
2	26	MMPO	118.77	12.36
2	27	2sMMPO	121.42	16.58
2	28	WORST	149.01	100.00

The top two methods in 2D are both Chris's!

Lastly, let's look at scenarios that are so competitive under the method
that the leading candidate only wins within 45% of the time:

Dims	Rank	Method	Avg Dist	Avg Norm Dist
1	1	WORST	NULL	NULL
1	2	BEST	47.96	0.00
1	3	MMstrict	48.19	1.20
1	4	MARO2	48.19	1.20
1	5	MAP	48.19	1.20
1	6	RangeNS	48.48	1.49
1	7	Bucklin	48.85	1.65
1	8	MDDA	48.91	1.73
1	9	DAC	49.36	2.14
1	10	MAMPO	49.44	2.52
1	11	DSC	49.84	4.04
1	12	MARO1	49.90	3.04
1	13	MAFP	49.94	3.11
1	14	CdlA	49.98	5.01
1	15	QR	50.03	5.40
1	16	IBIFA	50.07	5.02
1	17	MMWV	50.83	6.38
1	18	C//A	50.84	6.41
1	19	SMDTR	51.12	6.66
1	20	SPST	51.87	8.16
1	21	IRV	52.53	9.61
1	22	MMmarg	52.57	9.73
1	23	MMPO	54.13	13.07
1	24	Raynaud	54.15	12.95
1	25	VFA	54.81	12.21
1	26	ApprZIS	56.12	3.87
1	27	ApprPoll	56.49	4.27
1	28	2sMMPO	56.49	4.27
2	1	SMDTR	117.11	9.94
2	2	BEST	117.65	0.00
2	3	IBIFA	118.39	8.36
2	4	MMWV	118.46	9.25
2	5	Raynaud	118.53	11.35
2	6	MMstrict	118.63	7.40
2	7	MMmarg	118.70	9.92
2	8	C//A	118.79	8.87
2	9	DSC	118.80	8.14
2	10	VFA	118.86	11.73
2	11	RangeNS	118.90	4.08
2	12	MAFP	119.02	7.35
2	13	QR	119.06	8.92
2	14	CdlA	119.11	8.64
2	15	SPST	119.34	11.14
2	16	IRV	119.44	9.60
2	17	MDDA	119.44	6.11
2	18	MARO1	119.46	6.87
2	19	MAMPO	119.74	6.73
2	20	MARO2	119.84	6.37
2	21	DAC	119.95	6.39
2	22	MMPO	120.28	13.94
2	23	Bucklin	120.41	6.00
2	24	ApprPoll	120.62	6.48
2	25	ApprZIS	121.09	6.38
2	26	MAP	121.83	11.04
2	27	2sMMPO	123.42	19.28
2	28	WORST	148.68	100.00

A couple of oddities here are that there were no 1D scenarios where the 
WORST candidate was that unclear. (In general we are down to having
about 60-300 scenarios to look at for a given method, though Range and
the Approvals have only 16-32 of these in the 1D case.) Also, the SMD,TR
method actually beat BEST in the 2D case.

What I still want to do is analyze what these scenarios look like.

I am concerned about the fact that a scenario can be competitive without
being realistic, if only due to the fact that the position could be
dominated by another strategy for both sides. For example, an FPP election
nominating an extreme left and an extreme right candidate could be
competitive, but it's not likely to occur, because it would be at least
as effective for either to nominate a candidate closer to the median.

(Incidentally I didn't include FPP or Antiplurality or some similar 
methods in this run, partly because I had trouble wrapping my mind around
the idea of assuming sincere voting but intelligent nomination.)

Kevin Venzke