[EM] Quick and Clean Burial Resistant Smith, compromise

[Kristofer Munsterhjelm]

On 09.01.2022 23:07, Daniel Carrera wrote:
> On Sat, Jan 8, 2022 at 6:20 PM Kristofer Munsterhjelm
> <km_elmet at t-online.de <mailto:km_elmet at t-online.de>> wrote:
> 
>>     > Is there an intuitive explanation why Smith-IRV and Benham are more
>>     > resistant to strategy? I'm trying to find Behman's method on the
>>     > electowiki but I'm not finding it. I was sure I had seen it there
>>     > before. Does it have an alternate name?
>> 
>>     Perhaps you misspelled it - it isn't Behman but Benham. You should be
>>     able to find it at https://electowiki.org/wiki/Benham's_method
>>     <https://electowiki.org/wiki/Benham's_method> :-)
>> 
>>     As for why the Condorcet-IRV methods resist strategy better, I think
>>     it's a combination of dominant mutual third burial resistance (which
>>     also renders the method immune to the DH3 scenario) and chicken dilemma
>>     resistance.
>> 
>>     An example of the three categories can be seen on the left in
>>     https://www.votingmatters.org.uk/ISSUE29/I29P1.pdf
>>     <https://www.votingmatters.org.uk/ISSUE29/I29P1.pdf>, on page 8.
>>     Borda is
>>     in the top category, minmax is well, in minmax, and IRV and the
>>     Condorcet-IRV hybrid (Woodall) are at the bottom.
> 
> 
> Thanks! I've read the paper. This is really interesting. I tried to
> write a program to reproduce the experiment so I could add other
> Condorcet-IRV methods (IRV-BTR and Raynaud(Gross Loser)) but I got
> stuck. I couldn't figure out how to implement the coalition of strategic
> voters. The paper doesn't really explain how it's done. It says:
> 
> "In order to avoid massive computational
> cost, I make the restrictive assumption that all
> voters in the strategic coalition must cast the
> same ballot"
> 
> I couldn't figure out how to decide which voters need to be in the
> coalition or what ballot they need to cast to maximize their chances.

In quadelect (my election simulator), I just do this:

for n = 1...numiters:
	e_A = sample a random v-voter c-candidate election according to some
given distribution
	w_A = winner of e_A according to method M
	for c_k in every candidate but w_A:
		for i = 1...strategy_iters:
			e_B = e_A
			for every ballot B in e_B:
				if B ranks c_k ahead of w_A:
					replace B with a random preference order
			w_B = winner of e_B according to method M
			if w_B = c_k:
				then strategy successful
	if strategy successful:
		increment number of strategy successes SS
	else:
		increment number of strategy failures SF

strategic susceptibility = SS/(SS+SF)

It underestimates susceptibility with large numbers of voters but should
give approximately the same results as JGA with his orders of magnitude.
You could of course optimize the pseudocode by aborting the inner loop
as soon as you have a successful strategy (and skipping the whole test
if there's a candidate with a majority of the first preferences).

I also have some quick and dirty code for exact strategic susceptibility
for impartial culture with small numbers of voters and candidates (3 or
4 candidates, <11 voters) where enumerating every election is possible,
but it's not particularly nice.

If you want to do it JGA style, you would replace the inner loop with
something like:

for 1...strategy_iters:
	e_B = e_A
	b_B = random preference order
	for every ballot B in e_B:
		if B ranks c_k ahead of w_A:
			B = b_B
	w_B = winner of e_B according to method M
		if w_B = c_k:
			then strategy successful

> In any event, I was also interested in that big table that shows the
> features of the systems (MAP/MA, ISDA, etc). I would love to see a table
> like that for Condorcet systems. Something like the one on Wikipedia,
> but more granular. For example, I saw on the electowiki that IRV-BTR and
> Raynaud pass ISDA, but it wasn't clear whether Raynaud(Gross Loser). In
> the paper, the methods that pass ISDA (Smith-AV and Tideman) also
> fail mono-add-plump and mono-append and I'm wondering if that's always
> true, or if it's just incidental.

https://electowiki.org/wiki/Raynaud suggests that all versions of
Raynaud pass ISDA, including Raynaud(GL). I agree, it would be useful to
have a table, but it wouldn't be practical to render it for all criteria
defined on electowiki; it would need some kind of interactive component
so you could select just the criteria (and methods) that interest you.

I don't know if ISDA implies failure of the two monotonicity criteria. I
know that it's open whether Smith is compatible with mono-add-top (which
imples mono-add-plump), and that you can't have all three of Smith,
Plurality, and mono-add-top. But I don't think anyone has investigated
whether ISDA implies failure of the two other monotonicity criteria.

>>     Unfortunately, pretty much every method in the resistant category is
>>     nonmonotone. fpA-fpC (which Kevin calls my Linear method) is monotone
>>     and passes both DMTBR and chicken resistance, but I don't know how to
>>     extend it to a Smith set of more than three candidates.
> 
> 
> I'm not familiar with fpA-fpC. Is that in the wiki somewhere?

Yep, https://electowiki.org/wiki/fpA-fpC should do it.

-km