View source for Space of possible elections

For a given type of ballot, number of voters and number of candidates, there is a finite and computable number of potential elections that can possibly occur. Due to the combinatorial nature of the problem this number is typically extremely large, even for modest electorate sizes.

Nevertheless, understanding the construction of this '''space of possible elections''' may be helpful to others looking for analyzing elections computationally, and may also be instructive for generating alternative parameterizations and analyses of election models.

This article details the space of possible elections for certain ballot types, as well as presents expressions for the total number of possible elections.

= Notation and parameters =

Throughout this article, the following conventions will be used:

* <math>n</math>: the number of voters
* <math>c</math>: the number of candidates
* <math>r</math>: the number of possible scores in a rated ballot
* <math>\mathcal{B}</math>: the set of possible ballots
* <math>\mathcal{E}(\mathcal{B}, n, c)</math>: the set of possible elections using ballots from <math>\mathcal{B}</math>, <math>c</math> candidates and <math>n</math> voters
* <math>|\cdot|</math>: the cardinality (or size) of a set, e.g. <math>|\mathcal{B}|</math> is the number of possible ballots.
* <math>p(k)</math>: the set of [[w:partition function|partitions]] for the integer <math>k</math>, with <math>|p(k)|</math> the [[w:partition number|partition number]] of <math>k</math>.
* <math>C(k)</math>: the set of [[w:Composition_(combinatorics)|compositions]] (ordered partitions) for the integer <math>k</math>, with <math>|C(k)|</math> the number of compositions of <math>k</math>.
* <math>\alpha \in p(k)</math>: a specific partition of <math>p(k)</math>
* <math>\kappa \in C(k)</math>: a specific composition of <math>C(k)</math>
* <math>\binom{N}{k} = \frac{N!}{(N-k)!k!}</math>: the binomial coefficient, the number of non-ordered ways to pick <math>k</math> elements out of <math>N</math>, without replacement.

= Number of possible ballots =

Since each voter may cast any of a finite set of valid ballots, we must first determine how many valid ballots are available.

== Single-mark ballots ==

Under single-mark ballots (1), like in [[plurality voting]], the number of ballots is trivially <math display="inline">|\mathcal{B}^1(c)| = c</math>.

== Cardinal (rated) systems ==

Let <math>\mathcal{B}^C(c,r)</math> be the set of cardinal (''C'') ballots with <math>r</math> possible evaluations for candidates. In this case, the total number of ballots is

<math display="block">|\mathcal{B}^C(c,r)| = r^c</math>

For [[approval voting]], <math>r = 2</math>.

:{| class="wikitable"
|-
| <math>c</math> || 2 || 3 || 4 || 5 || 6 || 7 || 8 || 9 || 10
|-
| <math display="inline">|\mathcal{B}^C(c,2)|</math> || 2 || 4 || 8 || 16 || 32 || 64 || 128 || 512 || 1,024
|-
| <math display="inline">|\mathcal{B}^C(c,5)|</math> || 25 || 125 || 625 || 3,125 || 15,625 || 78,125 || 390,625 || 1,953,125 || 9,765,625
|-
| <math display="inline">|\mathcal{B}^C(c,6)|</math> || 36 || 216 || 1,296 || 7,776 || 46,656 || 279,936 || 1,679,616 || 1,0077,696 || 60,466,176
|-
| <math display="inline">|\mathcal{B}^C(c,10)|</math> || 100 || 1,000 || 10,000 || 100,000 || 1,000,000 || 10,000,000 || 100,000,000 || 1,000,000,000 || 10,000,000,000
|-
| <math display="inline">|\mathcal{B}^C(c,11)|</math> || 121 || 1,331 || 14,641 || 161,051 || 1,771,561 || 19,487,171 || 214,358,881 || 2,357,947,691 || 25,937,424,601
|}

If blanks are allowed, they can be considered an extra degree of rating (so 0-5 scores + blank makes 7 total evaluations).

== Ordinal (ranked) systems ==

For ranked (>) systems, we must consider the possibility of equal rankings vs. strict rankings. Partial rankings may also be possible, which leads to a more complex computation.

=== Full strict rankings ===

Let <math>\mathcal{B}^{>}(c)</math> be the set of ranked ballots with strict, full rankings. In this case, the total number of ballots is simply

:<math display="block">|\mathcal{B}^{>}(c)| = c!</math>

These are the factorials or permutation numbers (OEIS sequence [https://oeis.org/A000142 A000142]).

:{| class="wikitable"
|-
| <math>c</math> || 2 || 3 || 4 || 5 || 6 || 7 || 8 || 9 || 10
|-
| <math display="inline">|\mathcal{B}^{>}(c)|</math> || 2 || 6 || 24 || 120 || 720 || 5,040 || 40,320 || 362,880 || 3,628,800
|}

=== Partial strict rankings ===

If limited to top <math>k</math> candidates, the number is

:<math display="block">|\mathcal{B}^{>\emptyset}_{k}(c)| = \frac{c!}{(c-k)!}</math>

But if voters are allowed to cast arbitrary partial rankings, the number becomes

:<math display="block">|\mathcal{B}^{>\emptyset}(c)| = \sum_{k=1}^{c} |\mathcal{B}^{>\emptyset}_{k}(c)| = \sum_{k=1}^{c} \frac{c!}{(c-k)!} = \mathrm{e} \Gamma(c+1,1) - 1</math>

Here, <math>\Gamma(x, z) = \int_{z}^{\infty} t^{x-1} \mathrm{e}^{-t} \mathrm{d}t</math> is the [[w:Incomplete gamma function|incomplete gamma function]], and <math>\mathrm{e}</math> is [[w:e (mathematical constant)|Euler's number]].

These are OEIS sequence [https://oeis.org/A007526 A007526].

:{| class="wikitable"
|-
| <math>c</math> || 2 || 3 || 4 || 5 || 6 || 7 || 8 || 9 || 10
|-
| <math display="inline">|\mathcal{B}^{>\emptyset}(c)|</math> || 4 || 15 || 64 || 325 || 1,956 || 13,699 || 109,600 || 986,409 || 9,864,100
|}

=== Full rankings, equality allowed ===

Let <math>\mathcal{B}^{\ge}(c)</math> be the set of ranked ballots with full rankings, possibly with equalities. Every equality creates an equivalence class between candidates, within which the order does not matter. There can be at least 1 equivalence class (all candidates are ranked equal), and at most <math>c</math> (all candidates different).

The equivalence classes are determined by the compositions <math>\kappa \in C(c)</math>. For example, for <math>c = 3</math> we may have the compositions (3), (2,1), (1,2) and (1,1,1), giving the ballots of the form (_ = _ = _), (_ = _ > _), (_ > _ = _) and (_ > _ > _). Thus, there are <math>\ell = |\kappa|</math> equivalence classes in a given composition, the size of each is given by <math>\kappa_i</math>.

Each of the "slots" in a ballot may be filled with a candidate, but the order should not matter within an equivalence. Therefore, for the 1st equivalence with <math>\kappa_1</math> slots, there are <math display="inline">\binom{c}{\kappa_1}</math> possible choices of candidates. For the second, <math display="inline">\binom{c-\kappa_1}{\kappa_2}</math>, for the third <math display="inline">\binom{c-\kappa_1-\kappa_2}{\kappa_3}</math> and so on, exhausting the possibilities at every level.

The total number of ballots is then given by

:<math display="block">|\mathcal{B}^{\ge}(c)| = \sum_{\kappa \in C(c)} \binom{c}{\kappa_1} \binom{c - \kappa_1}{\kappa_2} \cdots \binom{c - \sum_{i=1}^{\ell-1} \kappa_i}{\kappa_\ell}</math>

These are known as [[w:Fubini numbers|Fubini numbers or ordered Bell numbers]] (OEIS sequence [https://oeis.org/A000670 A000670]).

:{| class="wikitable"
|-
| <math>c</math> || 2 || 3 || 4 || 5 || 6 || 7 || 8 || 9 || 10
|-
| <math display="inline">|\mathcal{B}^{\ge}(c)|</math> || 3 || 13 || 75 || 541 || 4,683 || 47,293 || 545,835 || 7,087,261 || 102,247,563
|}

== Remarks ==

In addition to what was outlined above, specific voting systems may induce further structure to the ballots. For example, a cardinal system which normalizes ballots would reduce the number of possible ballots significantly. A cardinal system based entirely on margins would have a different number of ''effective'' ballots, despite the ballots themselves being different. Similar things may happen under ranked systems under additional constraints.

One may also want to exclude some ballots for having no effect. For example, the ballot with all equal ratings or rankings will have no effect in most voting systems. However, these ballots are only a vanishingly small number from the total possible ballots.

= The space of possible elections =

Each of the <math>n</math> voters may cast any one of the <math>|\mathcal{B}|</math> ballots, but since voters casting identical ballots are exchangeable the number of elections is smaller than <math>|\mathcal{B}|^n</math>.

The number of total unique elections depends on the possible partitions of the <math>n</math> voters into different groups, each casting identical ballots. For each partition <math>\alpha \in p(n)</math> of the <math>n</math> voters we have <math>|\alpha|</math> groups of voters, each casting a unique ballot. Therefore, we have to pick a different possible ballot for each of these groups. For the first group there are <math>|\mathcal{B}|</math> possibilities, for the second <math>|\mathcal{B}| - 1</math>, for the third <math>|\mathcal{B}| - 2</math> and so on. If the number of ballots is smaller than the number of voters, this sum must be truncated. Therefore, the total number of unique elections is then given by

<math display="block">|\mathcal{E}(\mathcal{B},n,c)| = \sum_{\begin{array}{c} \alpha \in p(n) \\ |\alpha| \le |\mathcal{B}| \end{array}} \frac{|\mathcal{B}|!}{(|\mathcal{B}| - |\alpha|)!}</math>

As the partition number may be approximated by <math display="inline">|p(n)| \approx \frac{1}{4n\sqrt{3}} \exp \left( \pi \sqrt{\frac{2n}{3}} \right)</math>, we can estimate for cardinal elections

:<math display="block">|\mathcal{E}(\mathcal{B}^C(c,r),n,c)| \approx \frac{1}{n} \mathrm{e}^\sqrt{n} (r^c)!</math>

and for full strict ranking elections

<math display="block">|\mathcal{E}(\mathcal{B}^{>}(c),n,c)| \approx \frac{1}{n} \mathrm{e}^\sqrt{n} (c!)!</math>

These numbers are exceptionally large for even modest number of candidates and voters.

= Final remarks =

Note that [[impartial culture]] models of voters do not sample this space uniformly, as there are many ballot combinations which produce identical elections due to the exchange symmetry between voters casting the same ballot. 

If there are more ballots than voters, the impartial culture model would on average split the voters into as many groups as there are voters, each voter casting a unique ballot. Due to strong correlations between voters and candidates in real-life elections, most possible ballots are not expected to occur. The structure outlined here can be used to develop alternative sampling models which are agnostic to specific models of utility or voter distributions.

Furthermore, if candidates themselves are also exchangeable we obtain the number of unique election 'scenarios'. Due to potentially distinct number of candidates in each ballot this computation is usually more convoluted. As a rule of thumb for ballots which specify all candidates, divide the number by <math>c!</math>.

The impartial anonymous culture model (also known as Dirichlet model) also fails to capture this structure properly, as sampling this space uniformly would in general produce too many unique ballots. The ideal approach would be to generate a random integer partition of voters and sample it through the Dirichlet model.

= References & external links =

* [[w:Impartial culture]]

* T. Nicolaus Tideman, Florenz Plassmann. [http://bingweb.binghamton.edu/~fplass/papers/ElectionGeneratingUniverse.pdf ''The Structure of the Election-Generating Universe'']

* Ya. V. Uspensky. ''Asymptotic expressions of numerical functions occurring in problems concerning the partition of numbers into summands''. Bull. Acad. Sci. de Russie, 14(6):199–218, 1920

* [https://oeis.org/ Online Encyclopedia of Integer Sequences]

[[Category:Elections]]
[[Category:Voting models]]