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.

Vancouver Open Data

Some months ago, there was talk in Vancouver about opening up the city’s data. As of yesterday, that data is now widely accessible in open formats at data.vancouver.ca. One such data layer is the bike routes in the city. There’s a lot more and it’ll be fun to see where it leads.

Short codes

With the advent of Twitter, shortened URLs have become all the rage: http://bit.ly/5dk33b, http://imgur.com/9G2rL, http://www.reddit.com/9dfo1. This kind of thing really isn’t all that hard to do.

$short_code = substr(preg_replace(
  array('/\//', '/\+/'),
  array('-', '_'),
  base64_encode(sha1(serialize($data, $salt), true))
), 0, 7);

Your $salt might be something as simple as a manually generated random string. If your data is time sensitive, it could be microtime(). Fancier two-way conversions are doable, in which you convert your primary key into a base-62 number, but I’ve yet to find a need for that.

Root latke waffles

• 8 cups shredded root vegetables (e.g. yam, sweet potato, beet, carrot, onion, etc.)
• 1 cup flour
• ½ cup cornstarch
• 1 tsp salt
• ½ cup water
• ¼ cup oil
• spices to taste

Shred the vegetables in a food processor (if you try this by hand, you’re likely to be at it all day). Mix the dry and wet separately before combining. Fry them up in a waffle iron and serve hot with any kind of dressing that suits: ketchup, salad dressing, raw tahini. It’s all good.

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"]
}

Spinning a clocklet disc

Imagine an infinitely small particle that keeps perfect time. Let’s call this particle a clocklet. We don’t have such particles, but they’re useful for considering the following.

Make a disc of clocklets about and start it spinning. Clocklet C0 is at the centre of the disc, C2 is on the edge, and C1 is half way in between. When the disc is spinning slowly, all three clocks agree on the time. C2 moves at twice the speed of C1. C0 spins, but does not otherwise move.

As we spin our disc faster and faster, the clocklets begin to differ due to an effect known as time dilation. Furthermore, C2 can never go faster than the speed of light even if C1 is moving faster than half the speed of light.

So what happens if it does? Assume that the disc spins fast enough such that C1 moves at 51% the speed of light. If the disc stops spinning, would C1 still be half way in between C0 and C2? Furthermore, does C0 differ at all from an independent clocklet outside of this disc?

I don’t have the background to answer these questions, but it’s certainly entertaining to think about.

Chained matching

Sometimes you want to find references to “foo bar” or things like that, but regex won’t cut it. Maybe “foo” is on a different line from “bar”. It can get a little hairy when you want to chain that together even further.

grep -ilR 'foo' * | xargs grep -il 'bar' | etc...

Chocolate oatmeal cups

Sometimes a recipe doesn’t turn out the way you’d expect. I have this one for oatmeal cookies that’s always turned out much flatter than I’d like. Instead of putting them on a cookie sheet, I tried using a muffin sheet such that they might hold their shape a little better. Little did I know that they’d puff up and collapse, creating chocolate oatmeal cups. Fantastic.

Ingredients

• ½ cup margarine
• 1 cup dry sweetener
• 1½ tsp vanilla extract
• 1 “egg” (I’m using Ener-G)
• 1 tsp baking soda
• ½ tsp salt
• 1 cup rolled oats
• ¼ cup cocoa
• ½ cup flour

Method

1. Like with all cookie recipes, mix the wet, sift together the dry, combine.
2. Bake in a muffin tray at 350°F for 10 minutes.
3. Let them cool down before putting them in the freezer for at least an hour.
4. Fill with anything: jam, ice cream, peanut butter, etc.