Summary of W.D.Smith's most prominent "Best Voting Systems" theorems
This page concisely summarizes some of the most important theorems proved by Warren D. Smith in his 3-part
"best voting systems" papers
I,
II,
III.
The goal of these papers was to prove theorems about, and show how to evaluate, and actually evaluate,
the Bayesian regrets (BR) of various voting systems, and identify best – meaning lowest BR –
systems. For any particular algorithmic voting method E,
we can compute BR(E) to arbitrarily high accuracy (if you run the computer long enough)
by computerized Monte Carlo election simulations. However, the goal
of these 3 papers was instead to do it with the human brain, and to make statements valid for infinite sets
of voting methods, not just one particular one at a time.
That was indeed accomplished, but at a price. The main "price" to be paid is that my human brain, to prove theorems,
needs to make oversimplified, and hence less-realistic, assumptions about voters and elections, versus what the
computer can handle. But within some oversimplified "clean" election models, I was indeed able to do it,
which was a breakthrough.
Description of the three models:
Random Normal Elections Model (RNEM):
Each voter Y gets a random standard normal variate as her utility for the election of candidate X
(and this happens independently for all candidate-voter XY pairs).
(The centers of the normals do not need to all be 0;
they could be voter-dependent constants.)
Absurdly Spherically Symmetric Issue-Space Model (ASSISM):
Let the V voters and C candidates each be points in a D-dimensional issue space with C≥1 and D≥1 fixed.
Let the utility of each candidate for each voter be a fixed decreasing function of the Euclidean distance between them,
which decreases to zero sufficiently quickly at ∞ (or it is acceptable for it to tend to any other constant, and
these constants can be voter-dependent, of course).
Suppose the voters are distributed according to a radially-decreasing probability density spherically symmetric about
some centerpoint 0, with each voter's location chosen independently from that density (and again we need this density
to decrease sufficiently quickly at ∞; it will suffice if it is a normal distribution or has compact support).
But no assumption is made about the locations of the candidates aside from supposing their locations
are sufficiently generic that the C distances from the candidates to 0 all are distinct.
YN (yes/no) model:
There are D independent "issues"
and 2D "candidates"; each candidate announces
a clear yes or no stance on each issue, and by some benificent miracle we have a full
democratic marketplace, i.e, all 2D possible issue-stances are
represented. Hence in the case D=4 we could
name the 16 candidates YYYY
("yes" on all 4 issues), YYYN, YYNY,..., NNNN.
We shall suppose, for each voter, the utility of electing
any given candidate is just the
number of issues
on which that candidate agrees with the voter.
Finally, we suppose without loss of generality
that all D issues each would win if put to a single-issue
yes/no vote, therefore the objectively best candidate is YYYY.
Remarks.
The RNEM generalizes a model that
had long been called the "Impartial Culture" in the political science literature, in which
"all V-voter C-candidate ranked-ballot elections are equally likely" and there is especial interest in the V→∞ limit.
The YN model arguably is the simplest possible "issue space" political model.
There are two reasons ASSISM is "absurdly spherically symmetric"
(1) use of Euclidean distance (not,
e.g, L1 distance which probably would have been more realistic) and
(2) spherically symmetric assumed distribution of voters.
Unfortunately my main result in ASSISM turns out to be sensitive to even slight asphericity.
Descriptions of the most prominent theorems:
In the RNEM, I evaluated the exact BR values of several voting methods, sometimes in closed form in terms of constants like π.
I proved the best (meaning least-BR!) 3-candidate election ranked-ballot method (under RNEM) is Borda, but with ≥4 candidates it is new.
I proved that both Approval Voting and Score Voting equal or better all rank-order voting systems, for
both honest and strategic voters (or any mixture) in 3-candidate RNEM elections.
For Score Voting this superiority is strict.
Score Voting with honest voters is superior to every rank-order ballot method in C-candidate RNEM
elections for each C∈{3,4,5,...31}.
For strategic voters using what I call "pseudo-best" voting strategy,
I proved Score Voting superior to any rank-order system for any mixture of honest and strategic voters
in C-candidate RNEM elections for each C∈{3,4,...,9}.
Honest Score Voting has regret which in the limit C→∞ is zero
relative to that of "random winner," whereas various other voting methods like Approval and Borda
have asymptotically nonzero relative regret; and strategic range=approval voting has asymptotic regret
which is a constant factor times smaller than that of random winner, although certain
other voting methods (e.g. Plurality) with strategic voting have asymptotically the same regret as random winner.
Under ASSISM, Condorcet voting methods are optimum in the limit of an infinite number of wholy-honest voters,
in the sense that they achieve asymptotically zero regret with probability→1.
(Meanwhile, Score Voting and every weighted positional system have positive regret.)
In the same spherically-symmetric ASSISM model, certain variants of honest and strategic Approval voting also are asymptotically optimum.
But the optimality of both Condorcet and these flavors of Approval Voting both are artifacts of ASSISM's exact spherical symmetry,
and are destroyed by even slight asphericity.
Under the "YN Model" (another D-dimensional politics model, this time with binary yes/no rather than continuum issues),
I proved Score Voting always delivers zero regret for any number V of honest voters.
In contrast I showed that many other voting systems such as
approval, Borda, instant runoff, and Condorcet (and score voting with strategic dishonest voters)
can exhibit horrible pathologies in contrived situations inside this model, e.g. electing the worst candidate,
plus many of them exhibit significantly positive regret in more realistic randomized settings.
A generalization, the "YN model with added jokers," has the property that honest voter range voting still is
always optimal (zero regret always) but every "weighted positional" rank-order method can be made to perform almost arbitrarily badly.
Conjecturally the same is true for the full class of all rank-order methods.
Bottom line:
"Best" voting systems were identified in all of these models, and Score Voting proven superior to all rank-order systems
in some of them.
For more details and more results, read the original papers.