IRV counting with integers to handle multiple candidates at the same preference level
I'd like to stop the misconception that IRV -- instant runoff voting,
also called "single-winner ranked choice voting" -- cannot allow a voter
to mark two or more candidates at the same preference level.
In particular, it's ridiculous that the FairVote organization promotes
the practice of tossing out a ballot when the counting reaches a
preference level where the voter has marked more than one candidate.
Although such shared preference levels are easy to handle using
fractions or decimals, that violates the common legal requirement that
votes be allocated to candidates in "whole" numbers.
Instead it can be done using only integers. It just involves
"grouping." Here's how:
When there are two ballots that rank candidates A and B at the same
preference level, one of the ballots is allocated to candidate A, and
the other ballot is allocated to candidate B.
When a third ballot with this preference is encountered, it's not yet
allocated. Then when the fourth arrives the third and fourth ballots
(with this pattern) are allocated to the two candidates, with one ballot
going to each candidate.
When there are 379 ballots with this pattern, 378 will be allocated, and
only one ballot will be uncounted. That's much better than tossing out
all 379 ballots.
It's that simple.
Writing the software is not difficult. It just involves grouping
equivalent ballots together. This grouping must be done separately for
each elimination round because the patterns change as candidates are
eliminated.
If anyone wants to know how the software can do this using only
integers, and simple C-language-like statements, just ask. I've
implemented it in my vote-counting software on GitHub.
The importance of this issue goes beyond a voter not having a preference
between two (or more) candidates.
Most of us voters want to be able to mark a strongly disliked candidate
at the lowest preference level. For example, imagine having 9
candidates and 6 ranking levels and strongly disliking candidate "I":
A > B > C+D > E > F+G+H > I
Not being able to rank candidate "I" at the lowest preference level is
unacceptable! Yet that can't be done if IRV counting can't handle
shared preference levels.
(And having 9 preference levels for 9 candidates puts us on a slippery
slope to how to handle the 135 candidates in the infamous California
gubernatorial recall election.)
Keep in mind that the number of viable candidates in elections will
increase. That's because vote splitting in general elections is what
caused political parties to limit themselves to just one nominee from
each party. As more places adopt IRV and other better ranked-choice
methods, vote splitting won't be an issue.
There's yet another reason some political parties will need to offer a
second candidate. It defeats the election tactic named "blocking."
That's the tactic of giving money to support a weaker candidate in a
primary election so that it's easier to defeat that party during the
general election. A clear example happened in the 2008 U.S.
presidential election when Hillary Clinton was blocked from reaching the
general election partially because some Republicans gave money to Barack
Obama based on their expectation that he could not possibly win the
general election.
Another reason for political parties offering a second nominee is that
in a gerrymandered district (which applies to most U.S. federal and
state districts) the winner's party is pre-determined, so offering just
one nominee means the district's minority-party voters have no
meaningful choice in the general election.
(By the way, as pointed out in a recent article at the Center for
Election Science, this is why extremist candidates are getting elected
rather easily under our single-nominee election system. They can get
elected with plurality support from less than half the dominant-party
voters, who themselves only need to be around 55 or 60 percent of the
district's voters. The single-nominee rule means the extremist
candidate is virtually unopposed in the general election.)
(Of course defeating these tactics won't come from political parties,
and certainly won't come from government initiatives. Yet ways to
defeat these unfair political-manipulation tactics are waiting to be
adopted.)
(BTW, tiny parties, with fewer than, say 15 percent of the voters
registered in that party, would only get one nominee. Or they would be
allowed a second nominee when a big party fails to offer a second nominee.)
So, the increase in the number of party nominees, and hopefully an
increase in opposition parties, will increase the number of candidates.
This means the places that get stuck with IRV (in spite of much better
methods), should not also be stuck with ranking each candidate at a
different preference level.
Of course the FairVote organization avoids this fairer approach because
they're trying to use IRV as a stepping-stone to STV, and STV becomes
complex when voters mark ballots this way. But it's time to reject the
unfairness of tossing out IRV ballots just because counting those
ballots under STV would become complex.
(Also, there are better STV-like methods that don't have the limitations
of STV.)
Now that discussions of IRV are increasing because of the proposed
"Forward Party" endorsing "ranked choice voting," those of us who
understand the math behind vote counting need to make it clear that IRV
does not have the shared-ranking limitation that FairVote imposes in
their certified software.
Probably all of you who write messages on this forum already understand
this concept.
Yet I'm hoping that those who only read this forum's messages will
understand that FairVote's claims (on their website and elsewhere) that
IRV ("single-winner RCV") cannot handle a voter marking more than one
candidate at the same preference level is a request to drink their
Kool-Aid, not an actual limitation in IRV.
Richard Fobes
The VoteFair guy
Here's how to make even IRV precinct summable in a practical way, even when
there are 135 candidates with 135 factorial permutations, and many more
when you take equal rankings an truncations into account:
Encode each ballot as a string, just as we do on EM list election profiles.
Add the ballot strings together algebraically as though each string were a
variable name. Algebra software easily adds these strings together
algebraically (as opposed to string concatenation) by collecting like terms
on the fly. The precinct sums are added together, as well, again by
collecting like terms. The coefficients of the collected terms tell how
many ballots in each faction, just as in our EM example profiles.
You don't need to initialize 135 factorial bins, when almost all of the
would end up empty, anyway!
El mié., 26 de ene. de 2022 5:46 p. m., Richard, the VoteFair guy <
electionmethods@votefair.org> escribió:
I'd like to stop the misconception that IRV -- instant runoff voting,
also called "single-winner ranked choice voting" -- cannot allow a voter
to mark two or more candidates at the same preference level.
In particular, it's ridiculous that the FairVote organization promotes
the practice of tossing out a ballot when the counting reaches a
preference level where the voter has marked more than one candidate.
Although such shared preference levels are easy to handle using
fractions or decimals, that violates the common legal requirement that
votes be allocated to candidates in "whole" numbers.
Instead it can be done using only integers. It just involves
"grouping." Here's how:
When there are two ballots that rank candidates A and B at the same
preference level, one of the ballots is allocated to candidate A, and
the other ballot is allocated to candidate B.
When a third ballot with this preference is encountered, it's not yet
allocated. Then when the fourth arrives the third and fourth ballots
(with this pattern) are allocated to the two candidates, with one ballot
going to each candidate.
When there are 379 ballots with this pattern, 378 will be allocated, and
only one ballot will be uncounted. That's much better than tossing out
all 379 ballots.
It's that simple.
Writing the software is not difficult. It just involves grouping
equivalent ballots together. This grouping must be done separately for
each elimination round because the patterns change as candidates are
eliminated.
If anyone wants to know how the software can do this using only
integers, and simple C-language-like statements, just ask. I've
implemented it in my vote-counting software on GitHub.
The importance of this issue goes beyond a voter not having a preference
between two (or more) candidates.
Most of us voters want to be able to mark a strongly disliked candidate
at the lowest preference level. For example, imagine having 9
candidates and 6 ranking levels and strongly disliking candidate "I":
A > B > C+D > E > F+G+H > I
Not being able to rank candidate "I" at the lowest preference level is
unacceptable! Yet that can't be done if IRV counting can't handle
shared preference levels.
(And having 9 preference levels for 9 candidates puts us on a slippery
slope to how to handle the 135 candidates in the infamous California
gubernatorial recall election.)
Keep in mind that the number of viable candidates in elections will
increase. That's because vote splitting in general elections is what
caused political parties to limit themselves to just one nominee from
each party. As more places adopt IRV and other better ranked-choice
methods, vote splitting won't be an issue.
There's yet another reason some political parties will need to offer a
second candidate. It defeats the election tactic named "blocking."
That's the tactic of giving money to support a weaker candidate in a
primary election so that it's easier to defeat that party during the
general election. A clear example happened in the 2008 U.S.
presidential election when Hillary Clinton was blocked from reaching the
general election partially because some Republicans gave money to Barack
Obama based on their expectation that he could not possibly win the
general election.
Another reason for political parties offering a second nominee is that
in a gerrymandered district (which applies to most U.S. federal and
state districts) the winner's party is pre-determined, so offering just
one nominee means the district's minority-party voters have no
meaningful choice in the general election.
(By the way, as pointed out in a recent article at the Center for
Election Science, this is why extremist candidates are getting elected
rather easily under our single-nominee election system. They can get
elected with plurality support from less than half the dominant-party
voters, who themselves only need to be around 55 or 60 percent of the
district's voters. The single-nominee rule means the extremist
candidate is virtually unopposed in the general election.)
(Of course defeating these tactics won't come from political parties,
and certainly won't come from government initiatives. Yet ways to
defeat these unfair political-manipulation tactics are waiting to be
adopted.)
(BTW, tiny parties, with fewer than, say 15 percent of the voters
registered in that party, would only get one nominee. Or they would be
allowed a second nominee when a big party fails to offer a second nominee.)
So, the increase in the number of party nominees, and hopefully an
increase in opposition parties, will increase the number of candidates.
This means the places that get stuck with IRV (in spite of much better
methods), should not also be stuck with ranking each candidate at a
different preference level.
Of course the FairVote organization avoids this fairer approach because
they're trying to use IRV as a stepping-stone to STV, and STV becomes
complex when voters mark ballots this way. But it's time to reject the
unfairness of tossing out IRV ballots just because counting those
ballots under STV would become complex.
(Also, there are better STV-like methods that don't have the limitations
of STV.)
Now that discussions of IRV are increasing because of the proposed
"Forward Party" endorsing "ranked choice voting," those of us who
understand the math behind vote counting need to make it clear that IRV
does not have the shared-ranking limitation that FairVote imposes in
their certified software.
Probably all of you who write messages on this forum already understand
this concept.
Yet I'm hoping that those who only read this forum's messages will
understand that FairVote's claims (on their website and elsewhere) that
IRV ("single-winner RCV") cannot handle a voter marking more than one
candidate at the same preference level is a request to drink their
Kool-Aid, not an actual limitation in IRV.
Richard Fobes
The VoteFair guy
Election-Methods mailing list - see https://electorama.com/em for list
info
On 27.01.2022 04:26, Forest Simmons wrote:
Here's how to make even IRV precinct summable in a practical way, even
when there are 135 candidates with 135 factorial permutations, and many
more when you take equal rankings an truncations into account:
Encode each ballot as a string, just as we do on EM list election
profiles. Add the ballot strings together algebraically as though each
string were a variable name. Algebra software easily adds these strings
together algebraically (as opposed to string concatenation) by
collecting like terms on the fly. The precinct sums are added together,
as well, again by collecting like terms. The coefficients of the
collected terms tell how many ballots in each faction, just as in our EM
example profiles.
You don't need to initialize 135 factorial bins, when almost all of the
would end up empty, anyway!
It has always been known that any method is summable in O(V) space :-)
Summable in the sense of the criterion means more like O(log V) * O(C^k).
Strictly speaking, yes, you could store all the votes on a memory card.
Suppose the election has a billion voters and there are 10 candidates.
We need 22 bits to store the permutation index since log_2(10!) =
21.791... (Arithmetic coding might get you even closer, but ignore for now.)
This times a billion voters gives 22 gigabit = 3 gigabytes, simple and
easy. And that's before compression, so it's a worst bound. Most likely
there are a lot of voters who would vote from left to right or vice
versa, and considerably fewer who would vote far right first, far left
second.
So, if this is easy, then what are the downsides? I guess there are two.
First, that detailed ballot information makes it easier to buy and sell
votes, because you could use the ranking as a signature to prove that
you're voting the way your benefactor wants you to.
Second, transparency: a matrix can be printed out on paper and it's
obvious what it means. A memory card requires a computer, where anything
might happen to your ballot. If observing the process is itself
important, and paper recounts need to be possible, then summable methods
have an advantage.
-km
On 27.01.2022 02:45, Richard, the VoteFair guy wrote:
I'd like to stop the misconception that IRV -- instant runoff voting,
also called "single-winner ranked choice voting" -- cannot allow a voter
to mark two or more candidates at the same preference level.
In particular, it's ridiculous that the FairVote organization promotes
the practice of tossing out a ballot when the counting reaches a
preference level where the voter has marked more than one candidate.
Although such shared preference levels are easy to handle using
fractions or decimals, that violates the common legal requirement that
votes be allocated to candidates in "whole" numbers.
Instead it can be done using only integers. It just involves
"grouping." Here's how:
This seems to be using fractional rank, i.e. that if you vote A=B, your
vote should count a half for A and a half for B.
Electowiki has some other alternatives. One is "equal vote without
elimination support" (my wording) which is basically this: A vote of the
type A=B does neither counts toward A or B as long as both are in the
race. As long as all candidates ranked equally, but one, are eliminated,
the ballot then counts maximally for the remaining candidate.
The idea, I think, is that if you express A=B>C on an IRV ballot, that
would be interpreted as you having no opinion of whether A or B
continues on, as long as one of them does. So you don't mind B being
eliminated if IRV then counts you as supporting A.
Such an approach would need no division at all and sidestep the problem
entirely :-)
-km
El jue., 27 de ene. de 2022 2:44 a. m., Kristofer Munsterhjelm <
km_elmet@t-online.de> escribió:
On 27.01.2022 04:26, Forest Simmons wrote:
Here's how to make even IRV precinct summable in a practical way, even
when there are 135 candidates with 135 factorial permutations, and many
more when you take equal rankings an truncations into account:
Encode each ballot as a string, just as we do on EM list election
profiles. Add the ballot strings together algebraically as though each
string were a variable name. Algebra software easily adds these strings
together algebraically (as opposed to string concatenation) by
collecting like terms on the fly. The precinct sums are added together,
as well, again by collecting like terms. The coefficients of the
collected terms tell how many ballots in each faction, just as in our EM
example profiles.
You don't need to initialize 135 factorial bins, when almost all of the
would end up empty, anyway!
It has always been known that any method is summable in O(V) space :-)
Summable in the sense of the criterion means more like O(log V) * O(C^k).
Strictly speaking, yes, you could store all the votes on a memory card.
Suppose the election has a billion voters and there are 10 candidates.
We need 22 bits to store the permutation index since log_2(10!) =
21.791... (Arithmetic coding might get you even closer, but ignore for
now.)
This times a billion voters gives 22 gigabit = 3 gigabytes, simple and
easy. And that's before compression, so it's a worst bound. Most likely
there are a lot of voters who would vote from left to right or vice
versa, and considerably fewer who would vote far right first, far left
second.
So, if this is easy, then what are the downsides? I guess there are two.
First, that detailed ballot information makes it easier to buy and sell
votes, because you could use the ranking as a signature to prove that
you're voting the way your benefactor wants you to.
The precinct summary would be something like
150 ABCDEFG+920BADEFG+ ...13GFED
The coefficients add up to the number who voted in the precinct.
That could easily be printed out with terms arranged in alpha numerical
order (in case you want to put in equal signs)
In a billion voter election, states print out the algebraic sum of all
their precinct expressions ...again, each expression will have one term per
actual faction, not per possible faction.
And nothing to stop them from making pairwise summaries as well.
The final algebraic expression in a billion ballot election would probably
have fewer than a million terms, ordered alphabetically for easy searching
online.
I'm not recommending STV, but like Richard The Vote Fair guy, I think the
STV people are making too many excuses for unjustifiable limitations.
Second, transparency: a matrix can be printed out on paper and it's
obvious what it means. A memory card requires a computer, where anything
might happen to your ballot. If observing the process is itself
important, and paper recounts need to be possible, then summable methods
have an advantage.
-km
On 27.01.2022 20:49, Forest Simmons wrote:
El jue., 27 de ene. de 2022 2:44 a. m., Kristofer Munsterhjelm
<km_elmet@t-online.de mailto:km_elmet@t-online.de> escribió:
On 27.01.2022 04:26, Forest Simmons wrote:
Here's how to make even IRV precinct summable in a practical way, even
when there are 135 candidates with 135 factorial permutations, and
many
more when you take equal rankings an truncations into account:
Encode each ballot as a string, just as we do on EM list election
profiles. Add the ballot strings together algebraically as though each
string were a variable name. Algebra software easily adds these
strings
together algebraically (as opposed to string concatenation) by
collecting like terms on the fly. The precinct sums are added
together,
as well, again by collecting like terms. The coefficients of the
collected terms tell how many ballots in each faction, just as in
our EM
example profiles.
You don't need to initialize 135 factorial bins, when almost all
of the
would end up empty, anyway!
It has always been known that any method is summable in O(V) space :-)
Summable in the sense of the criterion means more like O(log V) *
O(C^k).
Strictly speaking, yes, you could store all the votes on a memory card.
Suppose the election has a billion voters and there are 10 candidates.
We need 22 bits to store the permutation index since log_2(10!) =
21.791... (Arithmetic coding might get you even closer, but ignore
for now.)
This times a billion voters gives 22 gigabit = 3 gigabytes, simple and
easy. And that's before compression, so it's a worst bound. Most likely
there are a lot of voters who would vote from left to right or vice
versa, and considerably fewer who would vote far right first, far left
second.
So, if this is easy, then what are the downsides? I guess there are two.
First, that detailed ballot information makes it easier to buy and sell
votes, because you could use the ranking as a signature to prove that
you're voting the way your benefactor wants you to.
The precinct summary would be something like
150 ABCDEFG+920BADEFG+ ...13GFED
Yes. That is an explicit compression version of my method, and using
text instead of binary.
If you want to put every bit to maximum use, then instead of the string
"ABCDEFG", you can use a 13 bit integer field; in this case, the field
would have value 0. GFEDCBA would correspond to value 5039. Truncation
and equal rank make it a bit harder; I tried to construct a bijection
between truncated/equal-rank ballots and integers once but didn't quite
manage to do it.
If V >> c!, then the best format is an array c! long that gives how many
voters voted for each particular ranked ballot. If V << c!, then the
best approach is just a list of the rank indices for each voter (this
list should probably be sorted so as not to leak information about what
the tenth voter voted).
If the number of distinct orders is small, then it may pay off to, in
effect, RLE encode by index number. The fields would then look like:
(index number, number of voters voting this way)
for every index where there's at least one vote. E.g. if 1024 people
vote ABCDEFG, then the pair is (0, 1024). The loss here is that you use
some bits explicitly denoting the index.
-km
On 1/29/2022 5:28 AM, Kristofer Munsterhjelm wrote:
On 27.01.2022 20:49, Forest Simmons wrote:
El jue., 27 de ene. de 2022 2:44 a. m., Kristofer Munsterhjelm
<km_elmet@t-online.de mailto:km_elmet@t-online.de> escribió:
On 27.01.2022 04:26, Forest Simmons wrote:
The precinct summary would be something like
150 ABCDEFG+920BADEFG+ ...13GFED
Yes. That is an explicit compression version of my method, and using
text instead of binary.
If you want to put every bit to maximum use, then instead of the string
"ABCDEFG", you can use a 13 bit integer field; in this case, the field
would have value 0. GFEDCBA would correspond to value 5039. Truncation
and equal rank make it a bit harder; I tried to construct a bijection
between truncated/equal-rank ballots and integers once but didn't quite
manage to do it.
Thank you Forest and Kristofer for answering my question.
I'm interpreting your replies to mean that of course we can summarize
the ranked choice ballot data in the way that IRV counting requires. Is
that right?
As Kristofer says" "Truncation and equal rank make it a bit harder."
I believe it might be useful to summarize the ballot info in four ways:
-
Counts and encoded rankings for ballots that rank each candidate at a
different preference level. Using the method above. -
Separate counts and encoded rankings for the ballots that have shared
ranking levels, but just sending a subset of these, and truncated to
only show the ranks for the most popular candidates (omitting the
clearly can't-win candidates) -
Sending the pairwise vote counts -- both for use in finding pairwise
losing candidates, and as a complete summary of all the ballot data (but
not sufficient to track IRV or STV vote transfers). -
Maybe also sending counts for how many ballots mark each oval in the
pattern. This is like saying 236 ballots have a mark in column 1 and
row 1, 932 ballots have a mark in column 2 and row 1, etc. (If a ballot
marks more than one oval for the same candidate, only the higher-ranked
oval would be counted.) Of course this is equivalent to how Score
ballots can be summarized.
Regarding type 2, namely shared-preference-level ballots, if a precinct
has say 50,000 voters, is there a way to estimate whether the upload
time is hours versus minutes (at normal internet speeds)?
Obviously there can be huge numbers of possible marking patterns when
shared-preference-level ballots are involved, but how many of those
patterns would appear on more than just a few ballots?
Would it be reasonable to allow the precinct software to estimate the
possible winners and truncate the detailed pattern data to only include
the possible winners (based on this precinct-level estimate). Or should
the central counting location be the only source for requesting this
kind of truncation?
Does anyone recognize whether summary method 4 offers any meaningful way
to eliminate some of the candidates as can't win candidates?
I continue to believe there must be ways to overcome the IRV limitation
of not being precinct summable. At least for gathering enough
information within an hour of poll closing time to either:
-
tentatively reveal enough data to reveal a winner, ...
-
or else reveal the election is very close, and a day or two is needed
to collect the full detailed vote counts.
Richard Fobes
The VoteFair guy
On 1/29/2022 5:28 AM, Kristofer Munsterhjelm wrote:
On 27.01.2022 20:49, Forest Simmons wrote:
El jue., 27 de ene. de 2022 2:44 a. m., Kristofer Munsterhjelm
<km_elmet@t-online.de mailto:km_elmet@t-online.de> escribió:
On 27.01.2022 04:26, Forest Simmons wrote:
Here's how to make even IRV precinct summable in a practical way, even
when there are 135 candidates with 135 factorial permutations, and
many
more when you take equal rankings an truncations into account:
Encode each ballot as a string, just as we do on EM list election
profiles. Add the ballot strings together algebraically as though each
string were a variable name. Algebra software easily adds these
strings
together algebraically (as opposed to string concatenation) by
collecting like terms on the fly. The precinct sums are added
together,
as well, again by collecting like terms. The coefficients of the
collected terms tell how many ballots in each faction, just as in
our EM
example profiles.
You don't need to initialize 135 factorial bins, when almost all
of the
would end up empty, anyway!
It has always been known that any method is summable in O(V) space :-)
Summable in the sense of the criterion means more like O(log V) *
O(C^k).
Strictly speaking, yes, you could store all the votes on a memory card.
Suppose the election has a billion voters and there are 10 candidates.
We need 22 bits to store the permutation index since log_2(10!) =
21.791... (Arithmetic coding might get you even closer, but ignore
for now.)
This times a billion voters gives 22 gigabit = 3 gigabytes, simple and
easy. And that's before compression, so it's a worst bound. Most likely
there are a lot of voters who would vote from left to right or vice
versa, and considerably fewer who would vote far right first, far left
second.
So, if this is easy, then what are the downsides? I guess there are two.
First, that detailed ballot information makes it easier to buy and sell
votes, because you could use the ranking as a signature to prove that
you're voting the way your benefactor wants you to.
The precinct summary would be something like
150 ABCDEFG+920BADEFG+ ...13GFED
Yes. That is an explicit compression version of my method, and using
text instead of binary.
If you want to put every bit to maximum use, then instead of the string
"ABCDEFG", you can use a 13 bit integer field; in this case, the field
would have value 0. GFEDCBA would correspond to value 5039. Truncation
and equal rank make it a bit harder; I tried to construct a bijection
between truncated/equal-rank ballots and integers once but didn't quite
manage to do it.
If V >> c!, then the best format is an array c! long that gives how many
voters voted for each particular ranked ballot. If V << c!, then the
best approach is just a list of the rank indices for each voter (this
list should probably be sorted so as not to leak information about what
the tenth voter voted).
If the number of distinct orders is small, then it may pay off to, in
effect, RLE encode by index number. The fields would then look like:
(index number, number of voters voting this way)
for every index where there's at least one vote. E.g. if 1024 people
vote ABCDEFG, then the pair is (0, 1024). The loss here is that you use
some bits explicitly denoting the index.
-km
On 31.01.2022 03:12, Richard, the VoteFair guy wrote:
On 1/29/2022 5:28 AM, Kristofer Munsterhjelm wrote:
If you want to put every bit to maximum use, then instead of the string
"ABCDEFG", you can use a 13 bit integer field; in this case, the field
would have value 0. GFEDCBA would correspond to value 5039. Truncation
and equal rank make it a bit harder; I tried to construct a bijection
between truncated/equal-rank ballots and integers once but didn't quite
manage to do it.
Thank you Forest and Kristofer for answering my question.
I'm interpreting your replies to mean that of course we can summarize
the ranked choice ballot data in the way that IRV counting requires. Is
that right?
Essentially, what we're saying is that IRV maximally fails the
summability criterion, but computers make storagge cheap.
Summability is still better (it's easier to keep control of a paper
tally than all the computers that the SD card will be visiting), but if
summability is off the table for some reason, it's not the end of the
world. At least not as far as storage requirements are concerned.
As Kristofer says" "Truncation and equal rank make it a bit harder."
I believe it might be useful to summarize the ballot info in four ways:
-
Counts and encoded rankings for ballots that rank each candidate at a
different preference level. Using the method above. -
Separate counts and encoded rankings for the ballots that have shared
ranking levels, but just sending a subset of these, and truncated to
only show the ranks for the most popular candidates (omitting the
clearly can't-win candidates) -
Sending the pairwise vote counts -- both for use in finding pairwise
losing candidates, and as a complete summary of all the ballot data (but
not sufficient to track IRV or STV vote transfers). -
Maybe also sending counts for how many ballots mark each oval in the
pattern. This is like saying 236 ballots have a mark in column 1 and
row 1, 932 ballots have a mark in column 2 and row 1, etc. (If a ballot
marks more than one oval for the same candidate, only the higher-ranked
oval would be counted.) Of course this is equivalent to how Score
ballots can be summarized.
This is called, I think, a positional matrix. Once you have it, you can
calculate the result according to any weighted positional method (like
Borda, Plurality, Antiplurality, etc.) and also Bucklin.
Regarding type 2, namely shared-preference-level ballots, if a precinct
has say 50,000 voters, is there a way to estimate whether the upload
time is hours versus minutes (at normal internet speeds)?
The number of distinct ballots when truncation and equal-rank are both
allowed is, I think, https://oeis.org/A000629. To store an index of
maximum value n, we need ceil(log_2(n)) bits[1]. So the ballot format
that just gives the first voter's ballot, the second voter's ballot, and
so on, requires v * ceil(log2(n)) bits in total. This is a worst case
format: in most cases there will be more than one voter voting a
particular way, in which case the duplication can be compressed.
(https://electowiki.org/wiki/Space_of_possible_elections#Full_rankings,_equality_allowed
has information about how many distinct ballot types there are for
various ballot types, but it doesn't yet have both truncation and equal
rank at the same time.)
So let's take an example with 50k voters -- and 10 candidates.
With 10 candidates, the table says that there are 204495126 different
ballots, so we need 28 bits per voter. The total space required is 1 400
000 bits, or 175 KB. This would take less than a second to transfer on a
normal internet connection. You could easily fit the data on an 1.44MB
floppy, for that matter.
With 20 candidates, you'd need 73 bits per voter and the total election
image would come to 457 KB. That's the worst case. A global election
(7.9 billion voters) with 20 candidates is 72 GB.
So if a lack of summability is a problem, it's not raw storage that
makes it troublesome: it's keeping the people who'd want to corrupt the
results from doing so, and in particular from doing so undetectably.
Obviously there can be huge numbers of possible marking patterns when
shared-preference-level ballots are involved, but how many of those
patterns would appear on more than just a few ballots?
Would it be reasonable to allow the precinct software to estimate the
possible winners and truncate the detailed pattern data to only include
the possible winners (based on this precinct-level estimate). Or should
the central counting location be the only source for requesting this
kind of truncation?
Does anyone recognize whether summary method 4 offers any meaningful way
to eliminate some of the candidates as can't win candidates?
IRV advocates often use this observation to propose a method that (IIRC)
is used in Australia. Basically, each round of IRV is summable. So the
precincts can send the center the Plurality counts (one number per
candidate); then the center says "X lost, eliminate him", and they do
and recalculate, send their new counts to the center, and the process
repeats.
Thus if you allow interactivity, not much storage is required at all.
I don't think it's possible to definitely exclude any candidates on a
precinct level when doing IRV. Imagine that the first precinct has
everybody voting for candidate A (i.e. an unanimous result). Meanwhile,
A is the loser in every other precinct but the first one doesn't know
this. Then there's no way for the first precinct to know it should
eliminate A.
So however you do this early elimination, it has to be from the center's
point of view. Hence there must be communication between the precincts
(telling the center what it needs to know in order to know who to
eliminate), and then communication back to the precinct about who should
be eliminated. But at that point you have pretty much the Australian
protocol and you can just use that.
Determining whether the election is close can be done by the kind of
statistics used in polls in general. Suppose the precincts record a
thousand ballots at random. At each stage of the count, they will know
what the likely margin for the true count will be. If it's possible for
the counts to be somewhere inside the margin and X be eliminated, or for
them to be somewhere else inside the margin and Y be eliminated, then
it's too close to tentatively call. Note that X may be eliminated no
matter what the results are within the margin, and yet by bad luck the
sample just happened to be unrepresentative: so this can't be used to
definitively call an election, only to tentatively do so.
(One problem with IRV is that ties may amplify in unpredictable ways.
If, at any stage in the elimination process, either X or Y may plausibly
be eliminated, the differences in ballots can cascade down and change
the result completely depending on whether X or Y was actually
eliminated. In some cases, e.g. when there's a CW with >1/3 first
preferences, or a majority favorite, IRV is stable, but it's not in full
generality.)
-km
[1] As I mentioned earlier, I think it's possible to get this down to
ceil(log_2(n)*v) by using arithmetic coding, but that would just
complicate my argument so I don't bother.