[EM] Completion methods for Smith Sets
Buddha Buck
bmbuck at 14850.com
Mon Jun 18 20:02:14 PDT 2001
LAYTON Craig <Craig.LAYTON at add.nsw.gov.au> writes:
> >The problem is that step C requires examining every ballot at least
> >once. If this is a public election, that could require examining and
> >recounting possibly millions of ballots. With large numbers of candidates,
>
> >the number of possible rankings grows hyper-exponentially, and even 13
> >candidates under consideration would yield more possible rankings than the
> >population of the Earth. There is no way to represent ranking data in the
> >aggregate; re-examining the entire collection of ballots is the only way to
> go.
>
> What is the formula for the number of possible ballots (assuming equal
> rankings are possible, as long as at least one rank distinction is made)?
I don't know -- it's a messy problem, and I'm not certain that there
is a concise formula.
Working under a different condition: assuming equal rankings are not
possible, and all candidates are ranked, it's easier: N candidates
have N! rankings. With 13 candidates, that's 6,227,020,800, which is
close to the current population.
Let's see...
If equal rankings are possible, we can look at it as a labelling
problem: equally-ranked candidates get equal labels, and then we just
sort the labels.
For N candidates, there are
N^N ways to affix up to N different labels.
Unfortunately, those N^N ways have lots of duplicates (N ways with
only 1 label, N(N-1)*(2^N-2) ways with exactly 2 labels, etc), all of
which have to be subtracted.
So, we have a lower bound of N!, and an upper bound of N^N. Since
both N! and N^N are hyperexponential, I felt confident with my claims
;-).
>
> Craig
More information about the Election-Methods
mailing list