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

[Kathy Dopp]

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.

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.

Best regards,

Kathy

> Date: Wed, 14 Jul 2010 23:38:55 +0200
> From: Kristofer Munsterhjelm <km-elmet at broadpark.no>
> To: EM <election-methods at lists.electorama.com>
> Subject: [EM] Impartial culture with truncation?
> Message-ID: <4C3E2E6F.5070901 at broadpark.no>
> Content-Type: text/plain; CHARSET=US-ASCII; format=flowed
>
> As part of tinkering with my simulator, I have found that for certain
> methods, it's having problems finding disproofs of criterion compliance.
> As I think the reason may at least in part be with my ballot generator
> (which uses impartial culture plus a hack for truncation and
> equal-rank), I've been considering an extension to that concept.
>
> Consider a random ordering generator where, for n candidates, it picks
> randomly among all possible orderings involving choosing k out of n
> candidates, where k <= n, and each ordering being equally likely. For
> instance, for n = 3, the orderings are:
>
> A
> B
> C
> A > B
> A > C
> B > A
> B > C
> C > A
> C > B
> A > B > C
> A > C > B
> B > A > C
> B > C > A
> C > A > B
> C > B > A
>
> and each of these would have equal probability of being picked. Because
> there are 6 (2,3) orderings and 6 (3,3) orderings and only three (1,3)
> orderings, it will favor longer preferences.
>
> My question is, then, how would I go about making a ballot generator
> that picks orderings according to that particular extension of impartial
> culture?
>
> A simple approach would seem to be to pick the number of candidates in
> the ballot, then generating a random ordering based on that fact
> afterwards; but as far as I can see, deciding the probability that the
> ballot will have a single preference, two preferences, or three
> preferences, requires expensive factorial calculations. Could something
> recursive be used?
>
>
>
> Even better would be to have the same concept but also with equal rank,
> but that would be hard indeed. In the three candidate case, the possible
> orderings would be:
>
> A
> B
> C
> A > B
> A = B
> A > C
> A = C
> B > A
> B > C
> B = C
> C > A
> C > B
> A > B > C
> A > B = C
> A = B > C
> A > C > B
> A = C > B
> B > A > C
> B > A = C
> B > C > A
> B = C > A
> C > A > B
> C > A = B
> C > B > A
>
> if I'm not mistaken (which I might be since it's late).
>
>

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