• Welcome to the new Internet Infidels Discussion Board, formerly Talk Freethought.

Vote-counting: election-system analysis

The multiseat methods that I have described do not incorporate anything about political parties. So I now turn my attention to methods that do.

In general ticket, one votes for a party, then whichever party wins then fills all the seats.

In party-list proportional representation, each party gets a number of seats in proportion to how many votes it received. The party-list part is from a long tradition of parties publishing lists of candidates that they want seated. In the pizza example, one can imagine that some of one's friends do the catering job, putting toppings on the pizzas. The vegetarian would offer pepper, artichoke, garlic, onions, and olives. The meat lover would offer sausage, pepperoni, chicken, and ham. The oddball one would offer anchovies, mushrooms, and cheese.

So you and your friends vote for vegetarian, meat-lover, or oddball, and the caterers put toppings over areas in proportion to the votes, putting more toppings on larger areas.

In closed-list PR, the party decides which candidates are seated first. In this pizza example, it would be the caterers who decide on which toppings.

In open-list PR, one can vote for a candidate as well as for a party. The candidates with the most votes get seated first. The meat lovers could vote for sausage, to be sure that they will get sausage even if they don't get much pizza area. Likewise, the vegetarians could vote for peppers to ensure that they will get peppers.

One can limit the openness by ensuring that only candidates who go past some quota will get seated, like (total votes) / (number of seats).

Likewise, one can limit the representation to parties that get lots of votes by having some minimum fraction of the votes for a party to be represented, usually a few percent.
 
An important problem with proportional representation is ensuring that every party gets a nonnegative-integer number of seats. One can do it with
(total number of seats) * (party's votes) / (total votes)

but that is hardly ever an integer. A naive way of getting an integer is to round it off. But the total often does not add up to the total number of seats - one often gets a few seats too many or too few.

An alternative is largest remainder. One rounds down, finds how many seats are left over, then gives those seats to the parties that have the largest remainders. This has a problem called the "Alabama paradox". Back in 1880, someone discovered that if the US House of Representatives got some additional seats, then the state of Alabama would go from 8 to 7 seats in it.

Yet another alternative is highest averages. For each party's votes Vi, one calculates a denominator D from the party's number of seats ni, and then divides:
Qi = Vi / D(ni)

One then assigns a seat to the party with the largest quotient Qi. To ensure proportionality, D(ni) ought to be proportional to ni for large ni. This assignment continues until all the seats are assigned.

One need not start out with zero seats for each party. One can start out with the round-down version of the naive method, like what is used in largest remainder.

There are several denominators that have been used:
  • D'Hondt: D(n) = n + 1
  • Sainte-Lague: D(n) = n + 1/2
  • Huntington-Hill: D(n) = sqrt(n*(n+1)) ~ n + 1/2 - 1/(8n) + ...
The US House of Representatives uses the Huntington-Hill method, starting with 1 Rep per state.

The D'Hondt method tends to give larger parties more representation, and the Sainte-Lague method tends to give smaller parties more representation.
 
The thing about these alternate systems in the US: most of the population is rather math illiterate (I'm trying to be nice, here.). So the simplest system to vote and understand is important. That means, IMO, that instant runoff is the way to go. Most people at least understand ranking their choices and then 1-1 vote. Even if you keep the voting simple rank order, but use a more complex system of counting, there will be idiots and GOP (but I repeat myself) that scream fraud from the rooftops.

It's all good exercise to see what's out there, I suppose, but whatever is chosen has to survive the 'real world'...and the real world is pretty stupid.
 
The next methods are hybrids of single-member districts and party-list proportional representation.

A simple version is parallel voting or supplementary member, where some legislature seats, the district seats, are elected in single-member-district fashion, and the others, the list seats, are elected in party-list fashion, independent of the district seats.

A more proportional version is mixed-member proportional representation or the additional member system. In that one, the list seats are elected in party-list fashion, but to make the entire legislature proportional.

It sometimes has the problem that the list seats cannot compensate for disproportionality in the district seats. The extra disproportional ones are sometimes called "overhang" seats. One may either accept it or else add more list seats to compensate.


Some places have a majority bonus, where whichever party gets the most seats gets some extra seats to give it a majority of seats.

There is a proposed system called dual-member proportional representation - this system has two members per district. The first one is the winner of a district election, while the second one is one of the other candidates, chosen to make the legislature proportional.
 
I'll now address how highest-averages methods work. Of the parties in an election, party i got votes Vi and has seats ni. At each step, calculate quotients

Qi = Vi/D(ni)

for some denominator function D. Find the i that has the highest Qi and add a seat to that party: ni += 1.

How it works:

For it to work, it requires D to be positive and monotonically increasing, increasing for every value of its arg. So relatively low ni will make 1/D(ni) relatively high, and vice versa. So a relatively low value of ni will get incremented.

What makes it proportional? When one has added enough seats, the Qi's will become close in value, and D(ni) will be close to Vi/Q, where Q is the average value of the Qi's. To make ni proportional to Vi, D(ni) must be linear in ni: D = D1*ni. That makes ni close to Vi/(D1*ni).

For typical denominator functions, that is the case in the limit of large ni:
  • D'Hondt: D(n) = n + 1
  • Sainte-Lague: D(n) = n + 1/2
  • Huntington-Hill: D(n) = sqrt(n*(n+1)) ~ n + 1/2 - 1/(8*n) + ...

As to why D'Hondt supports larger parties and Sainte-Lague smaller ones, that is from what happens for the first few values:
DH: 1/D(n) = 1, 1/2, 1/3, ...
SL: 1/D(n) = 2, 2/3, 2/5, ...

So SL gives more of a boost for a small number of seats than DH does.
 
Worldtraveller said:
The thing about these alternate systems in the US: most of the population is rather math illiterate (I'm trying to be nice, here.). So the simplest system to vote and understand is important. That means, IMO, that instant runoff is the way to go. Most people at least understand ranking their choices and then 1-1 vote. Even if you keep the voting simple rank order, but use a more complex system of counting, there will be idiots and GOP (but I repeat myself) that scream fraud from the rooftops.
Click to expand...
DemoChoice Polls - has do-it-yourself IRV and STV polls. It shows the results of each round of counting, so it should be easy to follow how it works. Here is an example: DemoChoice Results - r/Neoliberal Dem Primary Poll - the participants in that subreddit are rather atypical of the overall population, and it shows in what candidates they like. Andrew Yang had the most first-round votes, and he had the most votes until the end, where Beto O'Rourke won. This has caused some controversy in some IRV-using elections, but it's a feature and not a bug - one wants a candidate that as many people as possible will like, even if that candidate is not their first choice.

Condorcet Internet Voting Service - another one. I looked through most of its public polls, and I found only a few that did not have perfect Condorcet sequences -- sequences where every member beats every later member. Here is one: CIVS poll result - Democratic Straw Caucus Clicking on "Show Details" reveals the poll's Condorcet matrix. It is almost perfect, but Andrew Yang beats Bernie Sanders instead of being beaten by him, and Deval Patrick and Michael Bennet are tied.
 
Some of the methods get rather complicated, though I've coded several of them.

 Schulze method or the beatpath method or cloneproof Schwartz sequential dropping.

In this method, one tries to find the best beatpath that contains all the candidates.

The Condorcet matrix: for candidates X and Y, D(X,Y) is the count of how many times X beats Y in the ballots.

In this method, a path from candidate X to candidate Y is a sequence of candidates C(1) ... C(n) such that

D(C(i),C(i+1)) > D(C(i+1),C(i)) for all i from 1 to n-1

The strength of path {C} P(C) = min over i of D(C(i),C(i+1))

The strength P(X,Y) of the connection between X and Y is the maximum over all paths C of P(C)

This connection strength is transitive: if P(X,Y) > P(Y,X) and P(Y,Z) > P(Z,Y), then P(X,Z) > P(Z,X)

That makes it possible to sort the candidates into an overall order, a best beatpath.

Although it might seem like one has to go through all the permutations of the subsets of the candidates, there is a much faster way, using a variant of the  Floyd–Warshall algorithm. That algorithm runs with time O(n^3) for n candidates.
 
The  Kemeny–Young method is another method that works with paths, in this case, every possible permutation C of the candidates.

For each path C, it finds overall score P(C) = sum over i,j with j>i of D(C(i),C(j))

The winning path is the path C with the highest score P(C). Needless to say, this algorithm requires a run time of O(n!) for n candidates.


Another path-making algorithm is Tideman's  Ranked pairs algorithm.

It starts with making quadruplets of candidates and their Condorcet-matrix values: (X, Y, D(X,Y), D(Y,X))

It next sorts those quadruplets by their third entries, breaking ties by reverse sorting by their fourth entries.

With those quadruplets, it creates what I call a beatlist.

Add the highest member of the sorted quadruplets to the beatlist. Then add the rest of them in sequence, if doing so does not create a cycle -- the beatlist's quadruplets should be a "directed acyclic graph".

When that step is done, then sort a list of candidates so that they are in the order of the candidates in the quadruplets in the beatlist.

That sorted list is this method's output. The runtime is O(n^4) for n candidates.
 
The  Minimax Condorcet method finds the candidate with the smallest defeat by any other candidate.

It scores each candidate X as M(X) = max over Y of M(Y,X)
The winner has the smallest M(X) value.

There are three ways to find two-arg M:
  • Winning Votes: M(X,Y) = D(X,Y) if D(X,Y) > D(Y,X) otherwise 0
  • Margins: M(X,Y) = D(X,Y) - D(Y,X)
  • Pairwise Opposition: M(X,Y) = D(X,Y)

 Copeland's method reduces the Condorcet matrix's elements into -1, 0, or 1:
R(X,Y) = 1 if D(X,Y) > D(Y,X) otherwise -1 if D(X,Y) < D(Y,X) otherwise 0

It scores each candidate X as R(X) = sum over Y of R(X,Y)
The winner has the largest R(X) value.
 
Ipetrich
Thank you for all the voting information. I for one have found it most informative.

Though sometimes Stalin's dictum come sto me - 'It doesn't matter how people vote. Its how the votes are counted that is important.'.

Australia's looks most like the Instant run off.
 
 Majority judgement is a different way of counting rated votes. Instead of summing them, or equivalently, taking their mean, it takes their median.


 Maximal lotteries took a bit of work to figure out, but it makes a generalization of the Condorcet winner.

First, create an antisymmetric version of the Condorcet matrix: A = D - (transpose of D).

Then create a vector of weights w, one for each candidate X: w(X)

Solve these equations
A.w = 0
sum of w = 1

with constraints
0 <= w(X) <= 1 for all X

Doing so requires something called linear programming, and I ended up writing my own implementation of the simplex algorithm for doing that.

A Condorcet winner gives w = 1 for that winner and w = 0 for all the others. Otherwise it identifies what may be called partial Condorcet winners.
 
 List of electoral systems by country - Australia does indeed have IRV for its House of Representatives, and STV for its Senate.


 STAR voting - Score Then Automatic Runoff - seems like some odd hybrid to me.

It is a stage of score / rated voting, followed by a top-two runoff that uses the ratings to decide on the votes. In that stage, whichever of the two top candidates has the higher rating is the one that gets the vote in this stage.
 
To get down home about voting, I'll consider messageboard polls. I looked in this list: 10 Best Forum Software (Free & Paid) | websitesetup.org
I then looked through the available documentation to find out what poll features they offer. I'll only be concerned with what's directly relevant to vote counting, like being able to to select only one option or more than one - single or multiple votes.
  • vBulletin: Yes. Multiple.
  • Discourse: Yes. Multiple. Max number. Min number.
  • phpBB: Yes. Multiple. Max number.
  • SMF: Yes. Multiple. Max number.
  • XenForo: Yes. Multiple. Max number.
  • Vanilla: Yes (no further details)
  • MyBB: Yes. Multiple.
  • Flarum: No. (FriendsOfFlarum "Polls" extension: Yes.)
  • Invision: Yes.
  • NodeBB: No. (NodeBB nodebb-plugin-poll extension: Yes. Multiple. Max number.)
So there is this hierarchy of features:
  • No polls.
  • Single-vote polls.
  • Multiple-vote polls.
  • Multiple-vote polls with a maximum number of votes.
  • Multiple-vote polls with a minimum and/or a maximum number of votes.
I couldn't find any extensions that do cumulative voting or rated voting or preference voting.
 
In addition to DemoChoice and CIVS, I've found Brian Olson's site: bolson.org

2010 Redistricting Results - with an algorithm that optimizes for equal population and compactness. I've done some calculations like that myself.

BetterPolls.com - another site for creating one's own poll. Voter authentication is done by logging into Facebook or Google. So the only way one can do ballot stuffing is by having more than one Facebook and/or Google identity.

Voting And Election Reform discusses various methods and various voting issues.


One has to watch out for different names of voting methods:

First-past-the-post / plurality voting / single-choice voting
Range voting / rated voting / score voting


RangeVoting.org - Center for Range Voting - front page - advocates rated voting. It is good in having a low "Bayesian regret", from comparison of actual results to desired results as expressed in one's voting.

These articles disagree:
New Lessons from Problems with Approval Voting in Practice - FairVote
Approval voting has never faced voters on the ballot -- although it was repealed in 2009 by a vote of 81% of Dartmouth alumni after it was tried for electing trustees to the alumni board and contributed to a perception that tactical voters were getting an advantage over other voters. But we have evidence that suggests the problem of workability is very real, which is the focus of the rest of this analysis.

...
Two recent uses of the approval voting method by the Independent Party of Oregon and the Independent Voters Network show that it has value in certain uses, but is a far more problematic electoral method than ranked choice voting for electing candidates in meaningfully contested elections. These uses show that tactical voters can flip outcomes, and, due to that reason, most voters treat the election like a traditional plurality voting election and vote for only one. While in competitive RCV elections for important offices some nine in ten voters will rank more than one candidate, in approval voting elections that number plunges to less than half indicating support for more than one candidate, and often far less.
Click to expand...
How is RCV better than Approval, Score or Condorcet voting methods? - FairVote
RCV is also one of the few methods that satisfy a property called later-no-harm, which we believe is necessary in the context of high-stakes, competitive elections. Namely, under RCV a vote for your second choice cannot hurt the chances your first choice will be elected; a vote for your third choice does not hurt the chances of your first or second choice; and so on. This is not true under approval, score, or Condorcet voting — a vote for a later choice works against an earlier choice. When a voting system violates later-no-harm, voters face pressure to bullet vote, meaning to cast a vote for only one's first choice. Case in point: approval voting was used to elect the Dartmouth Board of Trustees, but once the Trustees elections became mildly competitive, they abandoned approval due in part to concerns over bullet voting. The more voters bullet vote, the closer the system will resemble plurality in practice, and then we're back to square one in terms of improving our voting system.
Click to expand...
Any system that will always elect the Condorcet winner will violate later-no-harm. In practice, however, IRV winners are almost always Condorcet winners.
 
I'll do an example of circular preferences. Most polls at CIVS have Condorcet sequences of candidates, and even those that don't have mostly-Condorcet sequences. In a Condorcet sequence, each candidate is a Condorcet winner relative to those behind it in sequence.

Here is an example, and I'll strip it down for convenience: CIVS poll result - Democratic Straw Caucus Using only Elizabeth Warren (EW), Bernie Sanders (BS), Joe Biden (JB), and Andrew Yang (AY), its Condorcet matrix is:
EW
BS
JB
AY
EW
-
7
10
10
BS
6
-
9
7
JB
4
6
-
8
AY
4
8
7
-
It's clear that EW is the Condorcet winner. But the remaining three candidates have circular preferences: BS > JB > AY > BS. Let us try to disambiguate them.
 
Copeland's method produces a 3-way tie: 0-0-0.

Minimax has these intermediate results, for all three variants of that method.
  • Winning
    • BS _ - 0 8 _ 8
    • JB _ 9 - 0 _ 9
    • AY _ 0 8 - _ 8
  • Margins
    • BS _ - -3 1 _ 1
    • JB _ 3 - -1 _ 3
    • AY _ -1 1 - _ 1
  • Opposition
    • BS _ - 6 8 _ 8
    • JB _ 9 - 7 _ 9
    • AY _ 7 8 - _ 8
All three variants have a BS - AY tie.

The Kemeny-Young method is fairly easy, since we have only 3 candidates. We have only 3! = 6 permutations to look at.
  • BS JB AY _ 24
  • BS AY JB _ 23
  • JB BS AY _ 21
  • JB AY BS _ 22
  • AY BS JB _ 24
  • AY JB BS _ 21
It's a tie between BS-JB-AY and AY-BS-JB
 
For ranked pairs, we have only 6 to sort: (BS, JB, 9, 6), (BS, AY, 7, 8), (JB, BS, 6, 9), (JB, AY, 8, 7), (AY, BS, 8, 7), (AY, BS, 7, 8).

The sorted list: (BS, JB, 9, 6), (JB, AY, 8, 7), (AY, BS, 8, 7), (BS, AY, 7, 8), (AY, BS, 7, 8), (JB, BS, 6, 9)

It gives us BS-JB-AY and AY-BS-JB.


For the Schulze beatpath method, I find these paths:
BS - JB: 9
JB - AY: 8
AY - BS: 8
BS - JB - AY: 8
JB - AY - BS: 8
AY - BS - JB: 8

So I get BS > JB, BS = AY, and JB = AY, and overall orders BS-JB-AY, BS-AY-JB, and AY-BS-JB


For maximal lotteries, I first find the Condorcet matrix minus its transpose:
0 3 -1
-3 0 1
1 -1 0
Multiplying by vector (p1,p2,p3) and finding what gives zero gives us p2 = p1, p3 = 3*p1.
With the p's adding up to 1, we have a solution: (p1,p2,p3) = (1/5, 1/5, 3/5)
So it's (BS: 1/5, JB: 1/5, AY: 3/5)
 
Why not just go out and get pebbles of enough colors to match the number of candidates. Relate the stones by color to candidates. Then have individual voters bring stones of their candidate's color and deposit them in a common voting barrel. The candidate whose pebble count is highest after voting is the winner. Every one learns something and a practical result is obtained.
 
You must log in or register to reply here.
Back
Top Bottom