[EM] Impartial culture with truncation?

[Kristofer Munsterhjelm]

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