Kathy Dopp wrote:
On Fri, Jul 16, 2010 at 7:39 AM, Kristofer Munsterhjelm
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.
Could you give each of the more than 120^30 (e.g.) possible unique
voter-ballot combinations equal probability of sampling and choose
that way?
I think that's what happens with impartial culture, since that sampling
has equal probability for each possible ballot. If we consider giving
each possible assignment of ballots to 30 voters a distinct number, so
that we could "look them up" by simply drawing a number between 0 and
120^30 out of a hat, then the probability that the first voter votes,
say, A>B>C is equal to the probability that it votes B>C>A (1/120).
Therefore, drawing permutations, where each permutation is equally
likely, 30 times, should give the same result as picking a random number
between 0 and 120^30 and translating that into a ballot group. The
advantage of doing it in the former way is, of course, that you don't
need to have 256-bit integers to do it nor memory to store every
possible combination.
Or could you simply sample each possible unique
voter-ballot combination one at a time and keep a simple array of
success or failure at meeting the criterion so as not to run up
against computer limitations?
If I could devise a bijection between the integer range [0..120^30> and
all possible ballot groups, then that could work; all I would have to do
would be to make a 208-bit cipher, then encrypt 0, 1, etc, up, and
reject all numbers greater than 120^30. This would work because of the
pigeonhole principle: say the encryption algorithm maps 0 to 6. Then it
can't map any other integer to 6 because then it would be impossible to
decrypt "6" again. There would be no need to keep an array, just an
index number meaning "passed criterion for all below this number" - once
one finds a failure, that's the disproof and there's no reason to search
further.
However, this would still require very large integers and so would be
slow -- and I would have to build the 208-bit cipher and the bijective
function. A method of drawing a truncated permutation with equal
probability for each would be better.
Is the computer limitation, the time it takes to run the program or
the memory space? I would be inclined to simply chug away at all the
possible combinations because if you randomly select some, you may
miss the criterion failures since you do not know how many criterion
failures there may be out of the total you would not know how large
the sample size has to be to hit them.
If you're talking about exhaustive search - trying every single one -
then the problem is speed. Say I can generate and test a billion ballot
groups a second. To test all 120^30 I would then have to work for...
7.5*10^45 years. The cipher solution would shuffle the ballot groups
around enough to make sampling work, but it wouldn't be exhaustive.
For similar reasons, simply storing all 120^30 explicitly and shuffling
the indices around would be impossible - there wouldn't be enough memory
to go around, nor time to even finish the shuffling pass.
----
Election-Methods mailing list - see http://electorama.com/em for list info
