Misinterpreting problem spaces

Polls and elections aren’t the same type of thing. The former asks for descriptive data, the latter for prescriptive preferences. To illustrate the hazards of this common misunderstanding, let’s go over some other ways data can partitioned and the problems that arise from confusing them.

Ordered data vs unordered data

Ordered data has an innate linear ordering, whereas unordered data doesn’t.

Ordered

How many apples can you eat in one sitting? (0, 1, 2…)

Unordered

What was the last type of apple you ate? (Granny smith, red delicious…)

When unordered data is confused as ordered data, a relationship is erroneously implied between the items.

When ordered data is confused as unordered, data trends are buried.

Ordered discrete vs ordered continuous

With discrete data, there exist two values for which there is no valid value in between, whereas continuous data can always be broken down into more detail.

Discrete

How many thermostats do you have in your house? (0, 1, 2…)

Continuous

What is the average temperature in your house? (22.1°C, 20.3°C…)

When discrete data is confused as continuous, inappropriate conclusions can be reached (chances are you have 2.3 thermostats in your house).

When continuous data is confused as discrete, granularity is lost. We can’t tell from the graph below whether there’s a large portion of 0.0km entries, if only odd decimal entries exist (0.1, 0.3, 0.5…), or any other detail hidden by these brackets.

Simple data vs compound data

Compound data have multiple values that bear some relation to each other.

Simple

How big is your television diagonally (24″, 32″, 34″…)

Compound

What are the dimensions of your television (20″x18″, 24″x20″…)

Compound data can be misrepresented as multiple simple data axes by ignoring the coupling between the two values, whereby the conditional probabilities are lost. Worse, it can be restricted down to a single simple data axis, whereby relevant data is entirely discarded (e.g. do sampled televisions only exist at certain aspect ratios?).

Descriptive data vs prescriptive preferences

Descriptive

What did you have for dinner last night?

Prescriptive

What should we have for dinner tonight?

The difference is subtle, but it’s there. With descriptive data, respondents have no incentive to tactically misrepresent their opinions. With prescriptive preferences, respondents (aka voters) are aware that their response will influence a future that likely affects them and will vote accordingly.

When prescriptive preferences are confused as descriptive data, a few things can happen:

• Continuous data can be filtered down into discrete data. Instead of allowing degrees of preference, ballots are restricted to binary expressions of support.
• Compound data can be filtered down into simple data. Although multiple options exist, ballots restrict the voter to supporting a single candidate.

Both confusions are present when Plurality voting is used in lieu of a more expressive ballot, where in voters could express more than just a single binary preference for a single option. Maybe this comes from ignorance of alternative voting methods, technical restrictions from the online voting application used, or seeing everything as a nail when you’re holding a hammer; Take your pick.

When Plurality voting is used to obtain prescriptive preferences, the same type of analytical fallacy is being made as is detailed in the above examples, all of which lead to a poor understanding of the underlying reality the data represents.

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.