Implementing Schulze STV

Thus far, my implementation of Schulze STV has worked fairly well. The downside I’ve recently run into is in simulating real world multiple winner elections. Take Vancouver’s 2008 municipal election as an example, in which 32 candidates ran for 10 seats. The problem-space we’re looking at consists of 32 choose 10 nodes and (32 choose 10) x 11 edges. For those unfamiliar with binomial coefficients, that’s roughly 64 million nodes and 709 million edges. Exponential runtime is a bitch.

For the purposes of heuristic development, let’s look at Tideman’s A03. It’s a set of 989 ballots to elect 7 winners from 15 candidates. Schulze STV computes the winning set as B/D/E/F/H/K/N by looking at 6435 nodes and 51480 edges. How do we best prune the number of candidates down so as to look at a smaller subset, yet still produce the same winning set in most cases? Well, what’s quickly available? We can easily calculate the sum of all votes, standard deviation, and whatnot.

If we wanted to prune off the least preferred by sum (indicated by larger sums), we’d be cutting off one of a winner Schulze STV would want to elect. Alternatively, let’s look at the number of voters that mark each candidate in first place. If a voter marks two candidates in first place, split their vote between the two.

That heuristic seems great at first as it didn’t accidentally eliminate winning candidates and it reduced the number of nodes to 120, a 98% reduction in problem space size. However, the winning set would now be computed by SchulzeSTV as A/B/D/E/G/L/N, which is significantly different. Furthermore, the heuristic is going to incentivize tactical voting. Sometimes there aren’t any easy shortcuts and the best thing to do is just optimize the implementation.

Motivated hobbies

Start a project around a subject you feel passionate about. It’s surprising how quickly you can get things done when there’s internal motivation. My most recent project went from prototype to useful application in about 10 days. I have to say, there’s a bit of pride that goes along with reaching a presentable milestone.

Modern Ballots

One of the difficulties I’ve run into with my recent project is explaining what it is a back-end web service does. In response, I’ve put a small web app up at modernballots.com. This front-end lets you create elections, but has no direct knowledge of voting systems. The winner is calculated remotely through the election web service, which is publicly available for other programmers to use.

At the moment, the front-end only requests the winner as calculated by Schulze STV, but that’s just to make the interface simpler.

Election Web Service

First draft of the Election Web Service is up and running. I’ve implemented Plurality, IRV, Ranked Pairs, the Schulze Method, Plurality at Large, and STV.

The source code is up on GitHub for anyone interested in implementing additional voting systems or using them as Python libraries. For those that just want to send requests to a server, I have one responding to posts at vote.cognitivesandbox.com (note that the server only response to HTTP POSTs and works solely on JSON encoded requests).

Hopefully this takes some of the burden out of implementing polls and whatnot. You take care of storing the ballots, I’ll show you who won (and why).

Example Request

{
  "votingSystem": "stv",
  "ballots": [
    {"count": 4, "ballot": ["orange"]},
    {"count": 2, "ballot": ["pear", "orange"]},
    {"count": 8, "ballot": ["chocolate", "strawberry"]},
    {"count": 4, "ballot": ["chocolate", "sweets"]},
    {"count": 1, "ballot": ["strawberry"]},
    {"count": 1, "ballot": ["sweets"]}
  ],
  "winners": 3
}

Example Response

{
  "rounds": [
    {
      "tallies": {
        "orange": 4.0,
        "strawberry": 1.0,
        "chocolate": 12.0,
        "pear": 2.0,
        "sweets": 1.0
      },
      "quota": 6,
      "winners": ["chocolate"],
    },
    {
      "tallies": {
        "orange": 4.0,
        "strawberry": 5.0,
        "pear": 2.0,
        "sweets": 3.0
      },
      "quota": 5,
      "winners": ["strawberry"],
    },
    {
      "tallies": {
        "orange": 4.0,
        "sweets": 3.0,
        "pear": 2.0
      },
      "quota": 5,
      "loser": "pear"
    },
    {
      "tallies": {
        "orange": 6.0,
        "sweets": 3.0
      },
      "quota": 5,
      "winners": ["orange"],
    }
  ],
  "winners": ["orange", "strawberry", "chocolate"]
}

Election API prototype

The project sputtered a few times before it really got going, but it seems well on its way. My first elections calculator was built to demonstrate the flaws of voting systems. This new one, however, is intended for the development community.

Most voting systems are plain Plurality (aka first past the post) and is prone to a great many flaws. Instead of implementing better voting systems libraries in each language, why not provide a general web service API?

The tool speaks JSON and provides and is completely stateless. You send your full request (ballots, desired voting system, etc) and it returns the winner (or winners) and an explanation as to how it reached that conclusion. All data is stored locally in cookies; The only server communication is for the result calculation.

I’m only about half-way done: four more algorithms to go (Schulze, STV, CPO-STV and Schulze STV) and a fair bit of polishing on the UI. Late December? Early January? Something like that.

A conflict of interests

Exhibit A: The Canadian Charter of Rights and Freedoms, Fundamental Freedoms section

2. Everyone has the following fundamental freedoms:
(a) freedom of conscience and religion;
(b) freedom of thought, belief, opinion and expression, including freedom of the press and other media of communication;
(c) freedom of peaceful assembly; and
(d) freedom of association.

Exhibit B: Bill 13 — Miscellaneous Statutes Amendment Act, 2009

“specified municipality” means any of the following:
(a) the City of Richmond;
(b) the City of Vancouver;
(c) the Resort Municipality of Whistler.

32 (1) Subject to this section and section 34, an officer or employee of a specified municipality or a person authorized by the council of a specified municipality has the authority to enter on property, and to enter into property, without the consent of the owner or occupier for the purpose of enforcing, in accordance with subsection (4), the specified municipality’s bylaws in relation to signs.

(1) Subject to subsection (2), the Council may make by-laws for the purposes of enforcing its by-laws, including establishing one or more of the following penalties to which a person convicted of an offence in a prosecution under the Offence Act is liable:

(a) a minimum fine;
(b) a maximum fine of up to $10 000;
(c) in the case of a continuing offence, for each day that the offence continues either or both of
(i) a minimum fine under paragraph (a), or
(ii) a maximum fine under paragraph (b);
(d) imprisonment for not more than 6 months.

The timing of this and the location constraint suggest that this is motivated by the coming Olympics. The short of it is if you have a sign they don’t like, they can fine you $10,000 and put you in jail for 6 months. I’d think that the Charter of Rights and Freedoms would trump this. How is it even being discussed then?

If this concerns you, please contact your MLA. If you don’t know who your MLA is, find out.

Partitioning control of electoral reform from vested interests

One of the key problems in electoral reform is that those who hold the power to change it benefit from the current system; It got them into office, right? Maybe there’s a way we can move that power out of those most disinclined to seriously consider it.

Just a thought. Every 10 years (5? 15?) hold a guaranteed referendum on what electoral system we should be using and switch to the preferred alternative. If the current system is FPTP, use FPTP as the referendum mechanism (likewise if it’s IRV, Schulze, etc).

Furthermore, the first referendum would occur in 10 years from now. Often candidates will run on platforms that include democratic reform, but abandon it once elected. By putting the first election far enough in the future, it can be ratified without directly threatening the power base of the current representative.

We don’t want the fox guarding the henhouse, right?

Single and multiple winner systems

Currently, Vancouver uses plurality to elect one mayor and plurality at large to elect 10 councillors. In so much as I’d love to see a multiple-winner Condorcet method used to elect both sets, I understand that such algorithms are too difficult for most to follow in multiple winner scenarios. While I think STV is a reasonable compromise, I dislike how IRV ignores votes and misrepresents large demographics when electing a single representative.

It’s unreasonable to suggest that we should use one method for single winner elections (Condorcet for the mayor) and another for multiple winner elections (STV for the councillors); I think that idea just wouldn’t sell. That being said, maybe IRV/STV is a imperfect, but reasonable stepping stone.

I’m not fully convinced yet, but I think small increments towards fairer representation is more realistic than giant leaps towards awesome.

Condorcet and later-no-harm

In recent discussions, I’ve had folks suggest that instant-runoff voting is fairer than Ranked Pairs. I disagree, but let’s cover the arguments.

Instant-runoff voting (STV@1) fails the Condorcet criterion

The majority of voters prefer C over B, but IRV elects B (failing the Condorcet criterion). Then 80 voters insincerely express a greater preference for C so as to ensure that B loses.

Ranked Pairs fails the later-no-harm criterion

Ranked Pairs elects C. Then 15 voters insincerely express a greater preference for A over C resulting in a win for B.

Comparison

It’s clear then that both systems are subject to tactical voting. This isn’t surprising as the Gibbard-Satterthwaite and Duggan-Schwartz theorems show that no system is immune to these types of problems. If no perfect system exists, the question is which system’s flaws are more acceptable?

The later-no-harm flaw in Ranked Pairs only arises when demographics vote tactically, whereas the Condorcet flaw in Instant-runoff requires demographics to vote tactically to avoid a sub-optimal winner. If we could guarantee completely sincere expressions of preference, range voting would be superb. If we could guarantee perfect strategy for all voters, I’d be good with IRV. As it stands, we live with a mix of both and I think that Ranked Pairs does a decent job of straddling that divide.

If we’re talking about mind-share, STV certainly has a lot more going for it and I’ll support it in any referendum against FPTP. It’s just a little frustrating to see a better system go unloved.

Presentation for Vancouver’s city council

Here’s the presentation on electoral reform I’m going to try to give to Vancouver’s city council. The two key ideas are reducing the scope to the municipal level and replacing STV with Ranked Pairs, which is arguably easier to explain. I feel like a small fish in a big pond getting involved in city politics like this, but I believe that this is a change in the right direction.

Update

The most convincing argument I’ve heard against this is that Ranked Pairs isn’t a proportional system. Its PR extension, CPO-STV, is obviously too complex. On the other hand, STV falls apart when electing one candidate (in the case of the mayor). Two systems isn’t an option, so what then? For now, I’ll just hold off and talk with others before taking this further.