Elections and voting, read from a counter's source
This essay is not legal or electoral advice. It describes published counting methods as rules over the ballots and populations a reader records, and it reads a program that states them. It certifies no election and counts no real ballot for anyone: which method an election uses, who may vote and what a ballot says are decided by the law and the officials who run it. A winner in it is a verdict over the numbers written, under the method named. The elections in it are invented or historical, and it names no current election, party or candidate.
Suppose Tennessee is holding an election on the location of its capital. The population is split between four cities, and all the voters want the capital to be as close to them as possible. The options are Memphis, "large but far to the west"; Nashville, "medium, near the center"; Chattanooga, "small and in the east"; and Knoxville, "small and isolated". If each voter in each city selects the city on the ballot, the plurality voting page says, Memphis will be selected, "as it has the most votes 42%". The system "does not require that the winner have a majority, only a plurality". The same page adds that if all the voters for Chattanooga and Knoxville had instead voted for Nashville, Nashville would have won with 58%, though it would have been only the third choice for those voters.
One set of ballots, and a count that picks one city has picked a method before it has looked at a ballot. This essay reads the elections library for DKE, the Deterministic Knowledge Engine, which writes down some of what a person who counts votes is taught, in DKE Python, and teaches the subject from it. It is two halves that share nothing but the subject. The first records an election, its candidates and its ballots, and concludes: who wins on a plurality, who wins on a majority, who beats every other candidate head to head, who loses to every other, who has the highest Borda score, and that no one beats every other when the counts run in a cycle. It refuses to name any winner while a ballot's count is in dispute. The second calculates: an instant-runoff count round by round, the Hare and Droop quotas, a house's seats by largest remainders and by three methods of highest averages, and the priority of a state's next seat. Every program below runs as shown once the library's source file has been compiled into a store, in the order given, and every output is copied from a run. The programs name their own elections and print only those, so that a store which already holds others gives the same lines.
1. Four cities, three winners
Each ballot is a ranking of every candidate of one election, first to last, and the number of voters who cast it. The four groups of the example are four ballots, and the rankings are the template's: Memphis's voters rank Memphis, Nashville, Chattanooga, Knoxville; Nashville's, Nashville, Chattanooga, Knoxville, Memphis; Chattanooga's, Chattanooga, Knoxville, Nashville, Memphis; Knoxville's, Knoxville, Chattanooga, Nashville, Memphis. The library writes, for every pair of candidates, how many voters rank the one over the other, and a candidate who beats every other head to head is the Condorcet winner. A Condorcet winner, that page says, is one for whom "in each pairing the winner is the candidate preferred by a majority of voters". The rule that concludes it asks that no pair be found in which the candidate does not come out ahead:
if c.election == e and absent(e.disputed) and none(d in Duel: d.a == c and d.margin <= 0.0):
c.condorcet = TrueA pair is ahead by its margin, the voters ranking a over b less those ranking b over a, and a tie head to head is no win. The rule that makes a candidate a majority winner is the same shape. A computed field doubles its first choices, and the rule compares that with the voters of its election, so that no arithmetic is written in a condition:
if c.election == e and absent(e.disputed) and c.twice > e.total:
c.majority = Trueimport elections
elections.election("tn", ["memphis", "nashville", "chattanooga", "knoxville"])
elections.ballot("m", "tn", 42.0, ["memphis", "nashville", "chattanooga", "knoxville"])
elections.ballot("n", "tn", 26.0, ["nashville", "chattanooga", "knoxville", "memphis"])
elections.ballot("c", "tn", 15.0, ["chattanooga", "knoxville", "nashville", "memphis"])
elections.ballot("k", "tn", 17.0, ["knoxville", "chattanooga", "nashville", "memphis"])
print(elections.winners("tn"))
print(elections.first_choices("tn"))
print(elections.head_to_head("tn"))
print(elections.borda_scores("tn"))
for r in elections.runoff("tn"):
print(r)
n = why_not(elections.Candidate.memphis.condorcet)
print(n){'plurality': ['memphis'], 'majority': [], 'condorcet': ['nashville'], 'condorcet_loser': ['memphis'], 'borda': ['nashville']}
{'chattanooga': 15.0, 'knoxville': 17.0, 'memphis': 42.0, 'nashville': 26.0}
{'chattanooga>knoxville': 83.0, 'chattanooga>memphis': 58.0, 'chattanooga>nashville': 32.0, 'knoxville>chattanooga': 17.0, 'knoxville>memphis': 58.0, 'knoxville>nashville': 32.0, 'memphis>chattanooga': 42.0, 'memphis>knoxville': 42.0, 'memphis>nashville': 42.0, 'nashville>chattanooga': 68.0, 'nashville>knoxville': 68.0, 'nashville>memphis': 58.0}
{'chattanooga': 173.0, 'knoxville': 107.0, 'memphis': 126.0, 'nashville': 194.0}
{'chattanooga': 15.0, 'knoxville': 17.0, 'memphis': 42.0, 'nashville': 26.0}
{'knoxville': 32.0, 'memphis': 42.0, 'nashville': 26.0}
{'knoxville': 58.0, 'memphis': 42.0}
{'knoxville': 100.0}
rule `elections.condorcet_winner` needs elections.Candidate[memphis].condorcet_winner__none1 to be absent, and it is presentThe first line is the whole disagreement. Memphis wins on a plurality with 42 voters of 100, and is no majority winner. Nashville beats every other city head to head, 58 to 42 against Memphis and 68 to 32 against each of the small cities, so it is the Condorcet winner, and it has the highest Borda score, 194. Memphis, the plurality winner, loses to every other city head to head, 58 to 42: it is the Condorcet loser. And the instant-runoff count, which eliminates the candidate with the fewest first choices and gives its ballots to the next choice on each, is a third winner: Chattanooga goes out, then Nashville, and Knoxville wins with all 100. The instant-runoff page says its rule was "first discussed by the Marquis de Condorcet, who showed the rule could eliminate the majority-preferred candidate", and the run shows it doing so: Nashville is out in the second round, before it can meet Knoxville, whom it beats 68 to 32. The library's output agrees with the pages that work the example: the Condorcet page's pairwise counts of 58, 58, 58, 68, 68 and 83, and the Borda page's scores of 126, 194, 107 and 173 for Memphis, Nashville, Knoxville and Chattanooga.
why_not on Memphis's Condorcet verdict says that something its rule asks to be missing was found, which is a pair in which Memphis is not ahead. The instant-runoff count is a calculation and not a rule: it eliminates in rounds, which a standing rule does not say, and a value script does.
2. Counting points, counting pairs
The Borda count gives each candidate, from each ballot, a number of points equal to the number of candidates it is preferred to: n minus 1 for a first place down to 0 for a last. The library states the same thing without points. A candidate's score is the sum of its head-to-head counts, since a voter who ranks it over a candidate is a voter who gives it a point against that candidate:
c.borda = sum(d.ab)The two are the same number, and the output above gives it: Nashville's 194 is 58 and 68 and 68 added. The history of both methods is older than either name, and the pages tell it with some disagreement. Ramon Llull described the election of an abbess in the 1283 novel Blanquerna, a process the Borda page calls equivalent to the second of Borda's two definitions of his count. The Condorcet page says Condorcet methods "were first extensively analyzed by Ramon Llull", and that the manuscripts "were lost from the Late Middle Ages until being rediscovered in the 20th century". The Condorcet paradox page says the paradox "was first discovered by Catalan philosopher and theologian Ramon Llull in the 13th century, during his investigations into church governance, but his work was lost until the 21st century". The first page's own list of dates mentions "the 2001 discovery of his lost manuscripts". The two pages do not agree on the century, and this essay does not choose between them. Llull's own dates are written three ways: "(1232–1315)" on the Condorcet page, "(1232–1315/16)" on the Borda page and "c. 1232 – 1316" on Llull's own page, which says he was stoned by a mob in 1315 and that there is evidence he "died early the next year".
Nicholas of Cusa comes next. The Borda page's lead says "the first recorded proposal in 1435" was his, and its history section dates his "De Concordantia Catholica" 1433, in which he "provided the first description of the Borda count and argued unsuccessfully for its use in the election of the Holy Roman Emperor". Then Jean-Charles de Borda, who, the page says, "re-devised the system in 1770", in a paper presented to the French Academy of Sciences in 1784 as "a fair way to elect members" to the Academy. In that paper, the page says, he gave a last place 1 point and a first place n, which does not matter if every voter ranks every candidate. The count was "the sole method used for membership election to the Academy from 1795 until 1800, when it was supplemented by other methods at the urging of Napoleon".
The Condorcet page names the other method for the Marquis de Condorcet, "who popularized the concept", and the paradox page cites his 1785 Essai sur l'application de l'analyse à la probabilité des décisions rendues à la pluralité des voix. The Borda page says Condorcet argued the Borda count is "bound to lead to error" because it "relies on irrelevant factors to form its judgments". The Borda page's own example of the weakness is the presence of candidates "who do not themselves come into consideration", which a method that asks only for head-to-head winners is protected against.
3. A majority that goes round
Condorcet's discovery, in the paradox page's words, is that "majority rule can be self-contradictory as majority preferences can become intransitive with three or more options". The page's example is three voters and three options, each ranking the options in a rotation, so that a majority prefers A to B, a majority prefers B to C and a majority prefers C to A. It calls this a rock-paper-scissors scenario. In such a cycle, the page says, "every possible choice is rejected by the electorate in favor of another alternative". The library holds it as three ballots of one voter each:
import elections
elections.election("rps", ["a", "b", "c"])
elections.ballot("x", "rps", 1.0, ["a", "b", "c"])
elections.ballot("y", "rps", 1.0, ["b", "c", "a"])
elections.ballot("z", "rps", 1.0, ["c", "a", "b"])
print(elections.winners("rps"))
print(elections.head_to_head("rps"))
print(elections.without_condorcet_winner())
try:
print(elections.runoff("rps"))
except refuse:
print("the runoff refuses: a tie for last place")
w = why_not(elections.Candidate.a.condorcet)
print(w){'plurality': ['a', 'b', 'c'], 'majority': [], 'condorcet': [], 'condorcet_loser': [], 'borda': ['a', 'b', 'c']}
{'a>b': 2.0, 'a>c': 1.0, 'b>a': 1.0, 'b>c': 2.0, 'c>a': 2.0, 'c>b': 1.0}
['rps']
the runoff refuses: a tie for last place
rule `elections.condorcet_winner` needs elections.Candidate[a].condorcet_winner__none1 to be absent, and it is presentA beats B two to one, B beats C two to one and C beats A two to one, so no candidate beats every other and without_condorcet_winner() names the election. The module does not choose one. The Condorcet page says that "various Condorcet methods differ in how they resolve such a cycle", and the methods that resolve one are not in the library: it says there is no winner. The three-way tie is the same answer from the other side: each of the three is the first choice of one voter, so plurality and Borda each name all three, and the instant-runoff count refuses, since all three are last in its first round and the method names no way to break a tie for last place. A tie head to head is no win, and no loss either.
Arrow's name belongs here. The impossibility theorem page says "When Kenneth Arrow proved his theorem in 1950, it inaugurated the modern field of social choice theory", and that Condorcet's paradox "is a special case of Arrow's paradox, which shows that any kind of social decision-making process is either self-contradictory or a dictatorship". Arrow's own page says his monograph Social Choice and Individual Values "derives from his 1951 PhD thesis" and that he received the Nobel Memorial Prize in Economic Sciences in 1972, along with John Hicks. The year of the theorem differs by a page: 1950 on the theorem's, 1951 on the thesis's. The library proves nothing of the sort and does not try: it shows one cycle that can be run, which is the kind of thing the theorem says every method will meet.
4. A count in dispute
A winner concluded over a count that is in dispute is a winner under neither count. A rule that adds the voters of a ballot would, given a second count of that ballot from a second source, add both, and the total would be a number nobody counted. The library writes the second count beside the first with recount(), and while any ballot of an election holds a second claim on its count, disputed is concluded for the election, no winner is concluded, and every reader refuses. The election is Tennessee's, with a recount of Nashville's ballot at 30 where the ballot said 26:
import elections
elections.recount("n", 30.0, "recount")
print(elections.disputed_elections())
try:
print(elections.winners("tn"))
except refuse:
print("refused")
d = why_not(elections.Candidate.memphis.plurality)
print(d)
forget(elections.Ballot.n.count, 30.0, "recount")
print(elections.disputed_elections())
print(elections.winners("tn")["plurality"])['tn']
refused
rule `elections.plurality_winner` needs elections.Election[tn].disputed to be absent, and it is present
[]
['memphis']The second count is not decided between: the module has no way to say which of 26 and 30 is right, and says that no winner is known until someone does. Once the claim that is not to stand is forgotten, the verdicts return. The dispute is a fact about the count, and it names itself in the refusal. That is all it can do for a real count, which an election's officials and its courts settle, and the module settles nothing.
5. A quota is a divisor
A house with seats to give has a different question: not who wins, but how many each is owed. The first calculations are the quotas. The Hare quota page says it "is equal to the number of votes divided by the number of seats", and that Thomas Hare used it in his scheme for a single transferable vote, "though the Droop quota is used for most STV elections today". The Droop quota was first suggested by the English lawyer and mathematician Henry Richmond Droop (1831–1884), and the exact Droop quota, the page gives, is the total votes over the seats plus one. The page also says the original Droop "was one more than the exact Droop". The library takes the exact one, and says so:
return float(votes) / float(seats)
return float(votes) / float(seats + 1)The largest remainder page says that largest remainders by the Hare quota "is sometimes called Hamilton's method, named after Alexander Hamilton, who devised the method in 1792". Each state takes the whole part of its share of the seats, and the seats left go one each to the largest remainders. The library does it in integers, so that a tie is a tie:
out[k] = populations[k] * seats // total
rem[k] = populations[k] * seats % totalThe highest-averages methods give seats one at a time, each to the state with the highest priority. The D'Hondt page says its method divides by one, two, three and on, and "was first described in 1792 by American Secretary of State and later President of the United States Thomas Jefferson", and "re-invented independently in 1878 by Belgian lawyer Victor D'Hondt". The Sainte-Laguë page says its method "was first described in 1832 by American statesman and senator Daniel Webster", and was "independently invented in 1910 by the French mathematician André Sainte-Laguë"; it divides by one, three, five and on. The Huntington–Hill page says each of the fifty states is first "given its one guaranteed seat", and then each seat goes to the state whose population is highest over the geometric mean of the two divisors, the seats it holds and the next. Those are three lines of one comparison, population against population by cross-multiplying, so that no division is rounded:
x = a * (nb + 1)
x = a * (2 * nb + 1)
return wide_compare(a * a, nb * (nb + 1), b * b, na * (na + 1))The page's example of the D'Hondt method is eight seats among four parties of 100,000, 80,000, 30,000 and 20,000 voters:
import elections
print(elections.hare_quota(100, 3), elections.droop_quota(100, 3))
votes = {"a": 100000, "b": 80000, "c": 30000, "d": 20000}
print(elections.highest_averages(votes, 8, "dhondt"))
print(elections.highest_averages(votes, 8, "sainte_lague"))
print(elections.largest_remainder(votes, 8))
print(elections.highest_averages({"a": 100000, "b": 80000, "c": 30000}, 8, "huntington_hill"))33.333333333333336 25.0
{'a': 4, 'b': 3, 'c': 1, 'd': 0}
{'a': 3, 'b': 3, 'c': 1, 'd': 1}
{'a': 3, 'b': 3, 'c': 1, 'd': 1}
{'a': 4, 'b': 3, 'c': 1}Jefferson's divisors give the largest party four seats and the smallest none; Webster's divisors, and Hamilton's remainders, give the smallest one and the largest three. The same ballots, the same eight seats, and two answers. The D'Hondt and Sainte-Laguë pages work this example with these numbers, and the library's seats are theirs. The first line is a hundred votes over three seats, 33.333333333333336 by the Hare quota and 25.0 by the exact Droop. The last is the Huntington–Hill page's own example, eight seats among three parties of 100,000, 80,000 and 30,000 voters, where each must hold a seat before the rest are given.
6. The house grows and a state loses a seat
The Alabama paradox is the oldest of the ways such methods go wrong. The apportionment paradox page says it was discovered in 1880: after that census, C. W. Seaton, chief clerk of the Census Bureau, "computed apportionments for all House sizes between 275 and 350, and discovered that Alabama would get eight seats with a House size of 299 but only seven with a House size of 300". It generalises it: the term "refers to any apportionment scenario where increasing the total number of items would decrease one of the shares". A similar exercise after the 1900 census, it says, found that Colorado would have received three seats in every House size from 350 to 400 but 357. The page gives a small example of three states, populations 6, 6 and 2, with ten seats and with eleven:
import elections
states = {"a": 6, "b": 6, "c": 2}
print(elections.largest_remainder(states, 10))
print(elections.largest_remainder(states, 11)){'a': 4, 'b': 4, 'c': 2}
{'a': 5, 'b': 5, 'c': 1}An eleventh seat took a seat from the small state. Its fair share rose from 1.429 to 1.571, but the large states' fractional parts rose faster and overtook it. A method of highest averages does not do this. The page says a method "may be free of both the Alabama paradox and the population paradox", that "these methods are divisor methods", and that Huntington–Hill is one, though they "will necessarily fail to always follow quota in other circumstances".
The congressional apportionment page tells what Congress did. It was Jefferson's method from the first census, 1790, with the Apportionment Act of 1792, "used until the 1830 census"; Webster's, "proposed in 1832 by Daniel Webster and adopted for the 1840 census"; a law of 1850 that declared Hamilton's method for the future; and then, from 1850 to 1900, ad hoc bills. Congress chose after each census, the page says, a size of the House at which Hamilton's and Webster's methods gave the same apportionment, which "was driven by the discovery of the Alabama paradox, which created an uproar in the House". The Apportionment Act of 1911 set the size at 435 and returned to Webster's method; the Reapportionment Act of 1929 capped it there; and the method now used, "known as the Huntington–Hill method or method of equal proportions, was adopted in 1941 for reapportionment based on the 1940 census and beyond". The apportionment paradox page tells it differently on one point of its own: Hamilton's method, it says, was "vetoed by George Washington and not adopted until 1852", where the other says 1850. The D'Hondt page says only that Washington's first veto was of a bill that "introduced a new plan for dividing seats", and that ten days after it Congress passed Jefferson's method.
7. The 2020 House
The Census Bureau's Table 1 for the 2020 census gives each state's apportionment population and the number of representatives, 435 of them, from 331,108,434 people. The library takes the fifty populations, a seat each first and then the rest by Huntington–Hill:
import elections
population = {
"alabama": 5030053,
"alaska": 736081,
"arizona": 7158923,
"arkansas": 3013756,
"california": 39576757,
"colorado": 5782171,
"connecticut": 3608298,
"delaware": 990837,
"florida": 21570527,
"georgia": 10725274,
"hawaii": 1460137,
"idaho": 1841377,
"illinois": 12822739,
"indiana": 6790280,
"iowa": 3192406,
"kansas": 2940865,
"kentucky": 4509342,
"louisiana": 4661468,
"maine": 1363582,
"maryland": 6185278,
"massachusetts": 7033469,
"michigan": 10084442,
"minnesota": 5709752,
"mississippi": 2963914,
"missouri": 6160281,
"montana": 1085407,
"nebraska": 1963333,
"nevada": 3108462,
"new_hampshire": 1379089,
"new_jersey": 9294493,
"new_mexico": 2120220,
"new_york": 20215751,
"north_carolina": 10453948,
"north_dakota": 779702,
"ohio": 11808848,
"oklahoma": 3963516,
"oregon": 4241500,
"pennsylvania": 13011844,
"rhode_island": 1098163,
"south_carolina": 5124712,
"south_dakota": 887770,
"tennessee": 6916897,
"texas": 29183290,
"utah": 3275252,
"vermont": 643503,
"virginia": 8654542,
"washington": 7715946,
"west_virginia": 1795045,
"wisconsin": 5897473,
"wyoming": 577719,
}
seats = elections.highest_averages(population, 435, "huntington_hill")
print(sum(population.values()), sum(seats.values()))
print(seats["california"], seats["texas"], seats["new_york"], seats["minnesota"], seats["rhode_island"], seats["wyoming"])
print(elections.highest_averages(population, 435, "dhondt")["california"], elections.highest_averages(population, 435, "sainte_lague")["california"], elections.largest_remainder(population, 435)["california"])331108434 435
52 38 26 8 2 1
54 52 52California 52, Texas 38, New York 26, Minnesota 8, Rhode Island 2 and Wyoming 1: every state's seats are the Bureau's, and the module's second implementation in CPython, which works in exact fractions, is held to the same fifty. Under Jefferson's divisors California would have had 54 seats where Huntington–Hill gives 52 and the other two methods give 52 as well. Which method is used is a choice that the house's size and the populations alone do not make.
The last seat is the interesting one. The congressional apportionment page says Minnesota "was allocated the final (435th) seat", the second time in a row, and that "if either New York had registered 89 more residents or Minnesota had registered 26 fewer residents, New York would have been allocated the 435th seat instead". The Bureau's list of priority values gives the two: Minnesota's priority for its eighth seat, 762997.7052660, is the 435th, and New York's for its twenty-seventh, 762994.3528429, is the 436th. A priority is a population over the square root of seats held times seats held plus one:
return float(population) / math.sqrt(float(held * (held + 1)))import elections
minnesota = elections.priority_value(5709752, 7)
print(minnesota)
print(elections.priority_value(20215751 + 88, 26) < minnesota)
print(elections.priority_value(20215751 + 89, 26) > minnesota)762997.7052659745
True
TrueThe first number is the Bureau's, to the places it gives, and CPython gives the same. With 88 more people in New York its priority is still under Minnesota's, and with 89 it is over. The module's second implementation in CPython runs the whole House with 89 more people in New York, and gives New York 27 seats and Minnesota 7; with 88 more, 26 and 8, as announced. The page's other figure is 26 fewer residents for Minnesota, and the library agrees with it too, down to the person:
import elections
new_york = elections.priority_value(20215751, 26)
print(elections.priority_value(5709752 - 25, 7) > new_york)
print(elections.priority_value(5709752 - 26, 7) < new_york)True
TrueWith 25 fewer Minnesotans its priority is still over New York's, and with 26 fewer it is under. Neither figure is the library's finding: both are the page's, and the Bureau's list gives the priorities the library computes. What the library adds is that each can be run from the populations.
8. When two sources disagree
Where pages disagreed in this essay it said so, and the disagreements are the point of a record kept by rules rather than by prose. Llull's manuscripts came back in "the 20th century" on one page and "the 21st" on another, with 2001 named on the first; his dates are written three ways. Cusa's proposal is 1435 on the Borda page's lead and 1433 for the book that makes it, in the same page's history. Arrow's theorem is 1950 on its page and the thesis it came from is 1951 on his. Webster's method was "adopted for the 1840 census" on one page and "adopted" in 1842 on another, a census and an act, and neither page says they are one event. Hamilton's was adopted in 1850 and in 1852. A page that keeps these in prose can say both and a reader can miss it. The library has the same limit: it holds what it is told, and where it is told two things about one count it names the dispute and decides nothing.
9. What the library leaves out
The library leaves out most of an election. A ballot ranks every candidate of its election and no fewer: no partial ballots, no approval or score voting, no single transferable vote for several seats with its transfers of surplus, no two-round election, no districts and no turnout. A cycle has no winner and the Schulze and ranked-pairs ways of choosing one from a cycle are not in it. Its Hamilton's method gives each state the whole part of its share and the leftover seats to the largest remainders, and gives no state a seat for a share under one, as the apportionment paradox page's version does. A tie for the last seat refuses rather than be broken, and so does a tie for last place in the runoff, because neither method names a way to break one. A population above 3,037,000,499 is beyond Huntington–Hill's exact comparison, and the library says so rather than round. And it counts the ballots written to it, whatever they were: whether a ballot was lawfully cast, a count lawfully made or a method lawfully chosen is not in any of its rules.
Closing
The same ballots elect Memphis on a plurality, Nashville on every head-to-head count and the Borda points, and Knoxville by elimination. Three voters can prefer A to B, B to C and C to A, and the same populations give California 52 seats or 54. A house of 299 gives Alabama a seat that a house of 300 takes away. The library keeps these where a reader can run them and ask about them: it names the winner under each method and shows that they differ, says that a cycle has no winner, refuses to name one while a count is disputed, gives seats in whole numbers and finds a tie as a tie, and says for each verdict the head-to-head count or ballot it rests on. It decides nothing that a law, an official or a court decides. What it does is show how much was decided by choosing the method.