[EM] Impartial culture with truncation? (Kristofer Munsterhjelm)

[Kristofer Munsterhjelm]

Kathy Dopp wrote:
> Kristofer,
> 
> If you are trying to generate disproofs of criterion compliance then
> using equal probability of selecting each ballot type for each voter
> may be preventing you from generating selections that disprove certain
> criterion, even if the method does not meet the criterion with some
> voter selections.

Yes, that is true. What I'm thinking is that my hack is, well, hackish 
and so doesn't cover a representative space of all possible ballots, 
thus making some otherwise simple disproofs inaccessible. I have no 
proof that going to equal-probability will be better - only that it has 
done well in the case of fully ranked ballots.

> Why not use nested loops to test all possible combinations of ballot
> selections for each certain number of voters? It would be a
> long-running program but would not miss any cases of failure to meet
> criterion because you would be testing all cases.

That would be possible for small voter,candidate numbers. If the number 
of candidates is small enough, it's even possible to show that the 
method fails a criterion by the use of a theorem prover.

However, some disproofs require many candidates and voters. Consider, 
for instance, the disproof showing that Schulze fails independence of 
pareto-dominated alternatives, as shown on 
http://alumnus.caltech.edu/~seppley/Independence%20from%20Pareto-dominated%20Alternatives.htm 
. It uses five candidates and 30 voters.

If we were to consider all possible ballots with five candidates 30 
voters total, that bee a prohibitively large number. There are 120 
different permutations (full rankings), so the first voter can pick any 
of 120 different ballots, then the second can pick any of 120 different 
ballots, and so on, for 120^30 total. That's 208 bits' worth -- I could 
crack AES-128 before I'd be done.

Therefore, my program needs some form of sampling. As impartial culture 
seems to do reasonably well in the full-rank case, yet I cannot test 
criteria that may need truncated ballots for a disproof, I was wondering 
how to generalize it.

Maybe the simple truth is that impartial culture does well only on 
certain criteria and will be very slow at finding solutions to others; 
in that case, I should look for some other approximation (or even black 
box search). On the other hand, maybe the disproof does require 
truncated ballots and so I'm kinda stuck with my hack unless I can find 
a "proper" way of extending impartial culture.