Technically Exists

Free sequential cancellation criterion

The free sequential cancellation criterion is an extension of the free cancellation criterion to sequential multi-winner voting methods. This criterion requires that for any two ballots that express identical preferences for the candidates elected so far, any other portion of those ballots expressing opposite preferences must cancel and any remaining portion must be free to express other preferences. While the free cancellation criterion itself can be applied to multi-winner methods, it is incompatible with proportional representation which arguably makes it a bad criterion to pass in multi-winner contexts. The free sequential cancellation criterion fixes this by requiring methods to obey free cancellation only when two voters have given the same amount of support to all candidates elected so far.

To give a more formal definition of the free sequential cancellation criterion, some terms and notation will need to be defined first. An incomplete list of winners $W$ is a (possibly empty) list of candidates that is smaller than the number of seats in the election, and a subset of the unelected candidates $C$ is a (possibly empty) set of candidates that does not contain any of the candidates in $W$ . A ballot $b'$ is in agreement with another ballot $b$ over a collection of candidates $C$ if for every candidate $c$ in $C$ , $b'(c) = b(c)$ . A ballot $b'$ is an opposite to another ballot $b$ over a collection of candidates $C$ if there exists an integer constant $k$ such that for every candidate $c$ in $C$ , $b'(c) = k - b(c)$ . The notation $b(c)$ refers to the level of support that candidate $c$ receives from ballot $b$ . The notation $m(b_1, b_2, \dots, b_n)[i]$ refers to the $i$ th winner produced by the voting method $m$ given the list of ballots $b_1, b_2, \dots, b_n$ . The notation $m(b_1, b_2, \dots, b_n)[1:i]$ refers to the list of the first $i$ winners produced by the voting method $m$ given the list of ballots $b_1, b_2, \dots, b_n$ .

With that out of the way, a sequential voting method $m$ passes the free sequential cancellation criterion if for every ballot $b$ , incomplete list of winners $W$ , and subset of the unelected candidates $C$ , all of the following hold:

There exists a ballot $b'$ that is in agreement with $b$ over $W$ and is an opposite to $b$ over $C$ .
For every ballot $b'$ that is in agreement with $b$ over $W$ and is an opposite to $b$ over $C$ , and for every list of ballots $b_1, b_2, \dots, b_n$ , if $m(b_1, b_2, \dots, b_n)[1:\vert W \vert] = W$ , $m(b_1, b_2, \dots, b_n, b, b')[1:\vert W \vert] = W$ , and $m(b_1, b_2, \dots, b_n, b, b')[\vert W \vert+1]$ is in $C$ , then either $m(b_1, b_2, \dots, b_n, b, b')[\vert W \vert+1] = m(b_1, b_2, \dots, b_n)[\vert W \vert+1]$ or $m(b_1, b_2, \dots, b_n)[\vert W \vert+1]$ is not in $C$ .
For every unordered pair of candidates $c_1, c_2$ not in $W$ or $C$ , there must exist three ballots $b'_1, b'_2, b'_3$ that are in agreement with $b$ over $W$ and are opposites to $b$ over $C$ such that $b'_1(c_1) < b'_1(c_2)$ , $b'_2(c_1) > b'_2(c_2)$ , and $b'_3(c_1) = b'_3(c_2)$ .

Note that this definition assumes that $m$ is deterministic and passes the anonymity criterion (though this criterion can be extended to also apply to non-deterministic methods).

Because no candidates are elected before the first round, the free sequential cancellation criterion requires that ballots obey the free cancellation criterion during that round. This also means that it reduces to the free cancellation criterion for single-winner methods since they only have one round.

Application to bloc voting methods

The free sequential cancellation criterion was primarily designed with proportional methods in mind, but it also behaves nicely in the context of bloc voting. In fact, the free sequential cancellation criterion and the free cancellation criterion are equivalent for bloc methods. Below is an informal sketch of the relevant proof.

First, it must be shown that if a bloc method passes the free sequential cancellation criterion, it passes the free cancellation criterion as well. A bloc method works by applying a single-winner method to elect a candidate, removing that candidate from the ballots, and then repeating those two steps until all seats are filled. The free sequential cancellation criterion requires that a voting method pass free cancellation in the first round, so the single-winner method employed by the bloc method must pass free cancellation. Since the bloc method uses this same method in every round, it will pass free cancellation in every round. Thus, the bloc method itself must pass free cancellation.

Next, it must be shown that if a bloc method passes the free cancellation criterion, it also passes the free sequential cancellation criterion. Consider some arbitrary ballot $b$ , incomplete list of winners $W$ , and subset of the unelected candidates $C$ . Let $b_{-W}$ be the ballot formed by taking $b$ and removing every candidate from $W$ . Since the single-winner method employed passes free cancellation, there must exist some ballot $b'_{-W}$ that is an opposite to $b_{-W}$ over $C$ . Let $b'$ be this ballot but modified so that it maps each candidate $w$ in $W$ to $b(w)$ . If adding $b$ and $b'$ doesn’t change the first $\vert W \vert$ winners, then in the next round all candidates in $W$ will have been removed and these ballots will reduce to $b_{-W}$ and $b'_{-W}$ . Because the single-winner method employed passes free cancellation, the next winner elected must meet the requirements for free cancellation, which in this scenario are exactly the requirements needed to satisfy free sequential cancellation. Therefore, this bloc method must pass free sequential cancellation.

It’s worth noting that this same argument applies to non-bloc voting methods that still have the same basic structure as bloc methods, such as single non-transferable vote and satisfaction approval voting.