[EM] Impartial culture with truncation? (Kristofer Munsterhjelm)
Kristofer Munsterhjelm
km-elmet at broadpark.no
Fri Jul 16 09:07:18 PDT 2010
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.
More information about the Election-Methods
mailing list