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

[Kathy Dopp]

On Fri, Jul 16, 2010 at 7:39 AM, Kristofer Munsterhjelm
<km-elmet at broadpark.no> wrote:
> 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.

Kristofer,

Yes, and more than double that amount given partial rankings.

>
> 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?  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?

>
> 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.
>

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.

Best regards,



-- 

Kathy Dopp
http://electionmathematics.org
Town of Colonie, NY 12304
"One of the best ways to keep any conversation civil is to support the
discussion with true facts."

Realities Mar Instant Runoff Voting
http://electionmathematics.org/ucvAnalysis/US/RCV-IRV/InstantRunoffVotingFlaws.pdf

Voters Have Reason to Worry
http://utahcountvotes.org/UT/UtahCountVotes-ThadHall-Response.pdf

View my research on my SSRN Author page:
http://ssrn.com/author=1451051