Saturday, October 8, 2011

Voting: The Algorithm

How does one fairly distribute votes among a number of parties? Last time I came up with a criterion for what constitutes a fair distribution. Stated mathematically, if you had two parties, numbered i and j. If v(x) is the number of votes that party x receives and s(x) is the number of seats that party receives. Then for any value of i and j, v(i)/[s(i)+1] < v(j)/s(j).

Along with the definitions above, let v be the total number of votes cast, let s be the total number of seats available.

I call the algorithm, lowering the bar. The algorithm is as follows:
  1. Let p=v/s, the beginning number of votes required to make a seat.
  2. For all i, let s(i)=v(i)/p rounded down. This is the initial number of seats that each party is given. Because of the rounding down, the total of the s(i) values will be less than or equal to s.
  3. Then, calculate p(i)=v(i)/[s(i)+1], the value of p that would give that party an extra seat.
  4. Set p=max[p(i)] and if x was the party that gave the maximum p(i) then set s(x)=s(x)+1. If there are multiple parties that are tied for the maximum, give all such parties another seat. If there aren't enough seats to give them all an extra seat, a runoff election has to be held.
  5. Repeat at Step 3 until there are no more vacant seats.
How this works with the Single Transferable Vote system is that after seats are distributed, the party with the least number votes that also has no seats has all the votes cast for them redistributed to that ballot's next choice. This repeats until all the remaining parties have at least 1 seat, at which point the seats have been finalized.

It's very easy to see how our standard election works. The winner has the most votes. This system is harder to keep track of. So, to build trust in the people and ensure fairness, the information about all the ballots cast would need to be available to the public. It would also have to be anonymized.

I won't bother with the proof of how this satisfies the criterion that I listed above (at least not in this post). Rest assured that it does.