by Warren D. Smith, May 2008
Abstract. Some people have argued that the Borda Count, or Condorcet methods, are superior single-winner voting methods to range voting. Here, we shall discuss the "Gazillion Transform" of a voting method, which is a way to add new artificial "candidates" to any election. It turns out that the gazillion transform converts Borda and Copeland voting into range voting and median-based range voting, respectively. That is, in the new election, the topmost-finisher (using Borda or Copeland) among the non-artificial candidates is the range-voting winner – assuming honest voters. Range voting remains apparently superior even with strategic voters in the sense that strategy is exactly the same in the gazillionized Borda and Copeland elections as it is in the range election, except that the Borda and Condorcet voters then would be able also to apply more strategies too. So if having strictly more strategies (a superset) available makes (all other things being equal) a voting method worse, then they are worse than range voting.
This "proves" that range voting is at least as good as either Borda or Copeland-Condorcet voting. The only way I see to deny this "proof" is to believe that adding extra candidates hurts Borda or Condorcet more (as ordering methods) than it hurts range voting. (But if so, then that itself is an argument that range is superior.)
Simply add a "gazillion" (more precisely G, in the limit G→∞) extra artificial candidates to the election. Candidate p, where p is an arbitrary real number with 0≤p≤1, is equivalent in utility (from the point of view of voter v) to a lottery in which, with probability p voter v's favorite wins, while with probability 1-p voter v's most-detested choice wins.
The p-values of the gazillion new candidates are assumed to be uniformly spaced throughout [0,1].
I am here describing the "normalized Gazillion transform." One could also consider the "unnormalized Gazillion transform" in which the p-lottery instead is among these two alternatives: (A) everybody lives to be 140 years old happily all the way, and (B) everybody is tortured to death.
We now conduct the election using any election method which outputs a rank-ordering of the candidates (e.g. Borda voting). The winner is declared to be the topmost-finisher among the original candidates.
1. Note that the addition of the gazillion new candidates of course leaves unaltered the identity of the "best" winner among the original candidates.
2. (Normalized) range voting is invariant under the (normalized) Gazillion transform; the same winner results (with honest voters) as in the original election.
3. Obviously, voting in the new gazillionized election is very difficult and expensive (since, e.g. rank-ordering a billion candidates is difficult for both voters and talliers). However, that would not matter if we were interested in obtaining the best possible winner no matter how much it cost. And this expense only makes our arguments about the superiority of range voting over, e.g, Borda, become more true.
4. The gazillion transform will effectively convert any voting method based on rank-order ballots, into one instead based on rating (range-voting style) ballots.
In Borda voting, each voter rank-orders all N candidates. The kth-ranked candidate gets score N-k. The candidate with the highest score-sum is elected, and more generally, the voting system can be regarded as outputting an ordering of all the candidates by decreasing "Borda score."
Borda Count voting is transformed into (Normalized) Range Voting by the (Normalized) Gazillion transform, because the Borda scores are in the limit the same, up to a rescaling, as the range-voting scores.
By "Copeland" voting, we shall mean the following procedure. Each voter rank-orders all N candidates. The "Copeland score" of candidate C is then the number of "pairwise victories" he enjoys over his rivals. The candidate with maximum score is the winner, and more generally the voting system can be regarded as outputting a full ordering of all the candidates by decreasing Copeland score. (A serious problem with Copeland is its propensity for tied-winners, but that will turn out generically not to matter for our purposes here.) Copeland is a "Condorcet voting method," i.e. elects any pairwise-undefeated candidate.
Copeland voting is transformed into median-based Range Voting (with normalized votes) by the (normalized) gazillion transform. To see that, argue as follows. The artificial candidates are ordered, unanimously, by all voters by p-value. Each voter may be regarded as assigning a p-score between 0 and 1 to each candidate based on where she places that candidate in her overall ordering. Among the artificial candidates, consider the one Q whose p-value is the same as the greatest median score enjoyed by any original candidate. That candidate with the greatest median score will be exactly tied with Q (with pairwise margin=0), but will be defeated by (margin≤0) every artificial candidate whose p-value exceeds Q's, and will defeat every artificial candidate whose p-value is below Q's (ignoring pairwise ties where exactly half the voters say A>B and half B>A; these cannot occur if the number of voters is odd). Thus the Copeland score of each candidate will be, in the limit, proportional to the median of the p-scores the voters award to that candidate.
The gazillion transform actually can be applied to any voting method which outputs a full ordering of the candidates.
Further, any method which merely outputs a single "winner" can be regarded as outputting a full ordering by the following trick: Output the winner, then remove that candidate from the set of candidates and redo the election to yield the "second finisher," then remove it and redo to get the "third," etc. This will be called "removal order." (It is not necessarily the same as the "natural" order for a voting method for which a natural order exists.)
It is interesting to explore what effect gazillionizing has on different voting methods.
Assuming each voter has a fixed private utility threshhold and approves everybody above-threshhold, then approval voting is invariant under the gazillion transform.
Plurality voting is invariant. (And so is anti-plurality voting.)
By "Simpson-Kramer minmax" voting, we shall mean the following procedure. Each voter rank-orders all N candidates. We compute the N×N "pairwise margins table," saying, for each ordered pair (A,B) of candidates, the number of voters who prefer A>B minus the number who prefer B>A. The "Simpson-Kramer score" of candidate C is then the margin of the worst pairwise-defeat C suffered.
Gazillionizing Simpson-Kramer (with removal order) converts it into a simple but extremely bad voting method. Specifically, it is this:
The same silly voting method arises also as the Gazillion transform of the Nanson-Baldwin voting method (of repeatedly eliminating the Borda-score loser), using the natural elimination-ordering.
"Upper-truncated" range voting means that we elect the candidate with the greatest average score after all scores greater than T are truncated down to T. (We similarly can define "lower-truncated" range voting; and we can do this for median-based range voting too.) I mention these because they seem to be important ingredients when trying to understand the gazillion transforms of various Condorcet and Borda-related voting methods.
By "Basic Condorcet" voting, we shall mean the following procedure. Each voter rank-orders all N candidates. We compute the N×N "pairwise margins table," saying, for each ordered pair (A,B) of candidates, the number of voters who prefer A>B minus the number who prefer B>A. The "score" of candidate C is then the minimum number of "pair-vote-reversals" we need to cause C to beat every rival pairwise. For example, if C defeats every rival pairwise (i.e. has positive margin over) except for A and B – becasue A beats C by a 10-vote margin, and B beats C by a 5-vote margin – then C's score would be 10+5=15.
Gazillionizing Basic Condorcet (with removal order) almost converts it into median-based range voting. The reason is that every artificial candidate whose p-value exceeds the maximum median score of any candidate, is a Condorcet winner among them. We keep removing these from the top down. Eventually we get a situation in which the median-range winner among the original candidates beats every artificial candidate hence has boundedly large Condorcet score. But the other original candidates still are (generically) defeated by an arbitrarily-large number of artificial candidates, hence have arbitrarily-large Condorcet score, hence cannot win.
This would have proven the winner must be the median-based range winner, except that at this point a non-removed artificial candidate might still be the winner.
So all that we have really proven is that, using removal ordering, at some point in the removal sequence (at which moment all the original candidates still remain) we shall reach a situation in which the median-based range winner among the original candidates, has far smaller Condorcet score than any other original candidate.
Gazillionizing Schulze Beatpaths (with removal order, generically) also almost converts it into median-based range voting (up to ties, which is an issue we ignore rather badly).
The argument is as follows. The median-based range winner W (with median score M) plainly has a beatpath to everybody who has median-score below M (simply walk to an artificial candidate wth p=M-ε then downward in p, then to the target candidate). Every defeat on the beatpath is unanimous (100-0) except for the first and last ones which might be by tiny margins. The first hop (from W to an artificial candidate Q whose p-value lies ε below M) always has minimally small victory margin, namely 1 or 0 votes. There does not exist a beatpath from anybody to any artificial candidate with p>M, and the only beatpaths from original candidates to the artificial candidate with score M-ε, have minimal strength. Therefore, no rival of W among the original candidates can be a beatpath winner because it has greater minimum beatpath strength to Q than does W. So we would be able to conclude W must be a beatpath winner (although perhaps a tied co-winner) except that, again, some non-removed artificial candidate might still be the winner.
So, again, all that we have really proven is that, using removal ordering, at some point in the removal sequence (at which moment all the original candidates still remain) we shall reach a situation in which the median-based range winner among the original candidates, is the only one with a beatpath to every still-not-removed candidate.
Black's method employs rank-order ballots; it elects a Condorcet winner if one exists, otherwise it elects the Borda winner.
Black (with removal order) is converted by the Gazillion transform into this voting system: If the ordinary (averaging-based) range voting winner has greater average score than the median-based range voting winner's median score, then elect the former. Otherwise, if the median-based range voting winner is a Condorcet winner, then elect it. Otherwise something else (more mysterious) happens.
First, all the pairwise defeats of artificial candidates with lesser p by those with greater p are "locked in" immediately since they all are 100-0 defeats. But what happens next is more mysterious. If the median-based range voting winner is a Condorcet winner, it will be elected.
IRV under the Gazillion transform (with removal ordering) will actually act exactly the same as IRV (but using range-style ballots, albeit with the usual IRV counting procedure that ignores the numerical preference strengths) with only a single extra candidate E added, where E is given some common score (also called E) for all voters, and we just keep decreasing E a smidgen until this IRV procedure stops electing E, and then the new winner is the winner of Gazillion(IRV).
So it is possible to devise a reasonably efficient algorithm to find the Gazillion(IRV) winner, but I do not think it has any simpler description and it is sometimes the same as and sometimes not the same as, the ordinary IRV winner.
The same "shrinking E" algorithm idea can be used to determine efficiently
who wins Gazillion(Schulze)
elections.