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.
----
Election-Methods mailing list - see http://electorama.com/em for list info
