[EM] Quick and Clean Burial Resistant Smith, compromise

[Kristofer Munsterhjelm]

On 12.01.2022 01:26, Daniel Carrera wrote:
> On Tue, Jan 11, 2022 at 4:44 PM Kristofer Munsterhjelm
> <km_elmet at t-online.de <mailto:km_elmet at t-online.de>> wrote:
>>     My impartial culture results are slightly higher than JGA's, which I am
>>     guessing comes from that I don't restrict the strategic voters in
>>     that way.
> 
> 
> Your method sounds expensive. My intuition is that it must take a great
> deal of luck to find a random assignment of ballots for each voter that
> changes the election result. I mean... it's an enormous parameter space:
> 
> (num candidates) x (num voters that prefer c_k > w_A)^( (num candidates)! )
> 
> What value do you use for `strategy_iters`? One obvious optimization is
> to first check if JGA's method works before doing the expensive loop.

Yeah, you would think so, but in practice it seems to work pretty well.
Perhaps this is an indication that if an election is susceptible to
strategy, the strategy usually is not very exotic?

I have noticed a dropoff with >10 candidates, though.

Other (obvious?) optimizations include:
	- If there's a majority winner and the method passes the majority
criterion, give up directly: the election is unmanipulable.
	- Trying the naive exaggeration strategy (if A was the winner, make B>A
voters vote B first and A last); requires just one check per other
candidate.
	- Parallelizing on all cores: the problem is embarrassingly parallel,
so you'd get a near-perfect linear speedup.
	- For IRV, storing results for up to k candidates so that you only have
to recurse down to k candidates before you know if the strategy succeeded.

Come to think of it, I imagine it's possible to cast manipulation for
various known methods as some kind of puzzle, and then use a solver to
definitely determine if a particular election is manipulable. But this
solution doesn't scale: you'd have to find out how to phrase it that way
for each method you want to speed up.

I use numiters=1000, strategy_iters=512. It takes about 10 seconds to
get the stats for IRV (for a given number of voters and candidates).
Very manipulable methods are much quicker, of course; my result for
Coombs (99 voters, 3 cddts, IC) is 0.9956-0.9973, and it takes less than
a second to check.

In case it's useful, I can also mention that I'm using the Jeffreys
interval for binomial c.i. to avoid problems with the Gaussian when the
expected value is very close to 0 or 1. Though reading the Wikipedia
article, it seems that the consensus is that the Wilson interval is better.

-km