Tall, Dark, and Mysterious

5/2/2005

Update: Electoral reform is, like, boring. And hard.

The Vancouver Sun has another useless article about how damned little British Columbians know about the single transferable vote system. How little is little? Well, 39% of the electorate claims to know “very little” about STV, while 25% knows “nothing at all”. The vice president of polling company Ipsos-Reid suggests some reasons for this, namely: STV isn’t “sexy or interesting”; anyone (anyone!) who looks into it finds STV to be “very complicated”; and - my favourite! - “There hasn’t been enough media coverage to create a buzz, and even people looking for information might not find enough to make an informed decision.” One wonders if the journalists who find these things out just nod sadly - hmm, not enough media coverage. Crying shame, that, but not much WE can do - and then ferret out another poll about how little the unwashed masses, with their lack of information and access to media coverage, know about stuff.

But the kicker was that right beside this dreck was a shorter, better piece (not available online, of course) about how in Victoria, James Hansen, a fourth grade teacher with a Master’s in political science or somesuch, had taught his students about the very complicated STV system by having them vote on the class hamster’s name - first via the first-past-the-post system currently in use in BC, and then by STV. No word on how sexy the fourth-graders found STV, but they certainly seemed to find it interesting enough, and the consensus appeared to lean strongly in its favour. The article was filled with all sorts of great quotes from kids, most along the lines of “I liked this way of voting because even though the hamster didn’t get the first name I wanted, I got to pick a second choice.” I wish I could have run this sort of thing in my math classes - that right there, that’s a real-life application of math. CBC did something similar, with the smoothly run, and very clearly illustrated Ice Cream Election. (Double Double Chocolate, Mint Chocolate Chip, and Vanilla were chosen, beating out crappy flavours like Peanut Butter Chocolate and Vanilla Cheesecake; this somewhat boosts my faith in my province’s electorate.) Anyway, my point is: the mechanics of hamster naming and ice cream choosing are apparently beyond the intellects of nearly two thirds of British Columbians of voting age, as well as The MediaTM.

Anyway, I fired off a snarky missive to the Vancouver Sun telling them that they should get Hansen on their staff; let him demystify this big, scary referendum for the ignorant voters who can’t find enough information about STV. Better yet, let’s get freelance jobs for his students, who seem to have a leg up on some 64% of people who are actually eligible to vote this month, and who could probably give a halfway decent explanation of electoral reform in simple language. Maybe I should rethink my general reluctance to teach little kids. Might as well teach them about the democratic process before they’re too old to understand it.

[Related, sort of: registering to vote by mail-in ballot is less of an ordeal than I expected. Not sure how good a thing that is, considering. And, although I said so in the comments - right now, I am quite sure that I will vote in favour of STV.]

24 Comments

  1. Hi,
    I read the CBC article, and I even read the link to the Citizen’s Assembly fact sheet. Yet, one question remains to me. What is the difference between the BC-STV and this: add all ratings for each candidates (the 1,2,3’s…). Sort the candidates in increasing order of their total sum of ratings. The top of the list gets elected. In what cases would the result be different?

    And here in QC, at the last referendum, people were complaining that the question was not “clear”… If only they had known BC…
    (”On se regarde, on se desole, on se compare, on se console.”)

    - happy not to live in BC — 5/2/2005 @ 8:57 pm

  2. Hi, HntLiBC:

    I concocted an example of where there’d be a difference; I’ll give that, and I’ll try my hand at an explanation of why I think that STV is better than the system you describe. (Thanks for asking that question, by the way, as it’s given me a chance to think about this more carefully.)

    Consider an election in which there are three candidates, A, B, and C, and 61 voters. The votes are distributed as follows:

    A gets 30 1st place rankings, 0 2nd place rankings, and 31 3rd place rankings.
    B gets 20 1st place rankings, 21 2nd place rankings, and 20 3rd place rankings.
    C gets 11 1st place rankings, 40 2nd place rankings, and 10 3rd place rankings.

    Notice that in the first-past-the-post system, A would win, because A get more 1st place rankings than anyone else.

    If we add up their scores, we get:

    A - 123
    B - 122
    C - 121

    So, C has the lowest score, indicating that more people ranked C with the better (1st and 2nd place) rankings than with the worse (2nd and 3rd) rankings. By your system C wins.

    However, using STV, on the first ballot we ditch C, because C got fewer 1st place rankings than anyone else. So the 11 ballots that placed C first are reviewed, and the second-place votes on those ballots are added to A’s and B’s scores. If the 11 people who all voted for C put B as their second choice, then B wins. Otherwise, A wins.

    The thing about your system is that it considers a 3rd place versus a 4th place ranking to be just as significant as a 1st place versus a 2nd place ranking: both of those differences result in the preferred candidate having a score of one unit lower than the less-preferred candidate. In STV, however, it’s more likely that more people will get their first choices, because that’s what’s looked at first. Your system says - hey, look, more people ranked C as their second choice than any other candidate, and they were less likely to rank C 3rd, so let’s choose C! STV, on the other hand, notices that the smallest number of voters actually liked C best, and knocks C out of the running first.

    I prefer STV, then, because it puts more weight on first choices. (Another way to look at it is: in your system, ranking someone 1st gets them 1 point, 2nd gets them 2…but why not give the 1st place person 0 points, the second place 5 points, and 3rd place 8 points? That would give very different results - A would win handily, and C would lose.)

    (Aside: note that the information from each individual ballot has to be stored separately. If Candidate X is dropped after the 1st ballot, then all of the ballots that ranked X 1st have to be reviewed individually to go to the second choice. The table of rankings I provided for the 3 candidates isn’t enough to determine who wins. [Completely, embarrassingly incorrect analysis of the complexity of counting STV ballots deleted, hopefully before anyone saw it.] Still seems like counting the n ballots will be O(n), but it could take a few times longer than counting them in a first-past-the-post system if there are a lot of relatively popular candidates. Still quite efficient by today’s standards, with our fancy computers and all, but if we’re hand-counting, then we’d no longer have election results within a few hours of polls closing, that’s for sure.)

    - Moebius Stripper — 5/2/2005 @ 9:56 pm

  3. It looks like it would be more accurate to say that the procedure takes O(mn) time, where n is the number of ballots and m is the number of seats.

    - Chris — 5/3/2005 @ 1:23 am

  4. I love kids ^.^ Can I adopt all of them?? Maybe a couple?

    - Rich Bateman — 5/3/2005 @ 6:38 am

  5. Chris, m is fixed for each riding, and small; we could consider it constant, or, at the very least, bounded above. So we’d still consider counting STV ballots to be O(n). Moreover, sometimes we’re just interested in the order of growth in terms of one of the variables, and in this case, number of ballots is a natural choice.

    - Moebius Stripper — 5/3/2005 @ 7:58 am

  6. I think it’s possible to only count each ballot once, instead of re-counting every time a candidate is elected or eliminated:
    There are finitely many possible rankings, and it’s not unreasonable to expect that a lot of the possible ones will be sufficiently “weird” that they’re not likely to come up in practice (f’rexample, radical liberal > radical conservative > centrist - a voter whose first choice is a radical liberal will probably prefer the centrist to the radical conservative). So keep track of every ranking that shows up and how many ballots had that ranking. When a candidate is elected or eliminated, take the rankings that had that candidate first and redistribute them appropriately. (This also reduces the total number of “relevant” rankings for the next step, since ballots that had the same rankings except that that candidate was ranked differently will no longer have “interesting” differences.)
    There will ALWAYS be no more unique rankings to go through than ballots to count, and additional ballots are more likely to duplicate an existing ranking than to add a new one, so this is likely to scale better-than-linearly with the number of ballots.
    (And it looks to me like the m in O(mn) is the number of candidates, not the number of seats - still small, but not bounded-in-theory.)

    - dave — 5/3/2005 @ 9:19 am

  7. Here’s some software that runs various STV-like voting schemes: http://stv.sourceforge.net/

    By the way, am I the only one who is driven nuts when I see “mathematical” discussion of algorithms without anyone actually writing down the algorithm?! How do you know you are even talking about the same thing? Or that you are even talking about the BC-STV algorithm at all?

    - john — 5/3/2005 @ 10:33 am

  8. In a textbook that I taught out of last year, the system of adding up the ratings for a candidate is called the “Borda count.” The problem with the Borda count is that it fails the condition known as “independence of irrelevant alternatives” and can be manipulated easily (google “Nader traders” for the idea in use in America).

    The STV system is also known as the Hare system, after Thomas Hare (1861). It is used in Australia, Malta, Ireland, and Northern Ireland :) The problem is that it can result in a tie, and is not monotonic (moving the winner up on some preference lists can result in that person not winning).

    The book is called “For All Practical Purposes,” by COMAP. ISBN 0-7167-4783-9 (so you can look it up online). I liked teaching this stuff because it gave a lot of insight into Ken Arrow’s voting paradox.

    Joshua Sasmor

    - Joshua Sasmor — 5/3/2005 @ 10:34 am

  9. M: I am assuming that in the worst case, almost every ballot must be counted per seat. I am also assuming that the number of seats per riding is a constant fraction of the eligible voters in the riding. Also, the number of ballots cast is a constant fraction of the eligible voters in the riding. Thus, if we only look at one variable, we have to draw the conclusion that the time it takes to count the ballots is O(n^2), where n is the number of eligible voters in the riding. This is clearly misleading, because the number of seats is much less than the number of voters, as you point out.

    (Also, I am probably wrong with my first assumption: there must be a trick like Dave’s that lets you only count the ballots once. But the STV algorithm isn’t very well specified, so I can’t be sure.)

    - Chris — 5/3/2005 @ 11:16 am

  10. Chris, that’s a good point about the number of seats (or, as Dave points out, the number of candidates) per riding being vaguely proportional to the number of voters in that riding. In that case, yes, this does throw a wrench into things, possibly making the algorithm O(n^2). Speaking of which, John, point well taken about discussion of algorithms without specifying what they are - in my defense, I only didn’t specify mine because it was the rather banal top-of-the-head procedure: count the first choices. If someone has a majority, count the second choices on the surplus ballots. Otherwise, knock off the losing candidate and count the second choices on the people who put the loser first. Repeat as necessary. So, worst case scenario, we have to go through some set of ballots per candidate.

    Dave’s algorithm involves storing the data for each ballot (which seems to use in memory what it saves in runtime, but that’s probably not a huge deal)…come to think of it, I’m not sure it’s that runtime-friendly, either, since it involves a lot of comparisons of rankings. Also, part of the beauty of the democratic process is that we’re allowed to thwart “reasonable” expectations, such as a lack of “weird” rankings such as the ones you expect. Politics is hardly linear, much as the liberal/conservative pigeonholing is applied.

    - Moebius Stripper — 5/3/2005 @ 11:42 am

  11. I bet parallel-processing could be used in some way to cut down on the time.

    But, getting back to practical considerations here — you do realize how fast computers are now, right? The multiple-passes algorithm would probably get done in no time. At worst, it may take a day to check and recheck.

    The vote-counting code would probably be the easiest part of the implementation.

    - meep — 5/3/2005 @ 12:19 pm

  12. Do you use computers for (counting) ballots in BC? I think they’re still hand-counted here; they were 10 years ago, anyhow, and I don’t recall any discussion about changing since.

    - wolfangel — 5/3/2005 @ 4:38 pm

  13. Meep - yeah, I know how fast computers are, which is why I was talking about the difference in runtime if the ballots were to be counted by hand. If we’re hand-counting, it’s significant. And aren’t you big on counting ballots by hand?

    Wolfangel - I’m not sure. I’ve only voted twice in BC - once in a municipal election, and once in a federal election. In the municipal election the ballot was a massive scantron form, so that was certainly done by computer. (We were voting for umpteen city councillors and such, as well as mayor and lackeys, so that makes sense.) For the federal election it was the old X-on-a-ballot, which I figure must have been counted by hand.

    - Moebius Stripper — 5/3/2005 @ 6:30 pm

  14. Some comments on BC-STV counting issues:

    - Due to the slightly higher complexity of BC-STV (as compared to FPP), there will almost certainly be more spoiled ballots. However, there will also now be a notion of a partially spoiled ballot, i.e. if you rank five candidates as “4 1 2 5″, then your ballot is counted for 1 and 2, but is then considered “exhausted” for votes after that because of the missing 3.

    - BC-STV requires the calculation — and re-calculation — of weights that depend upon the number of votes received by winning candidates. More so than the *time* it takes to do the counting, a greater worry is probably that these weights may be incorrectly calculated. There’s nothing tricky about the calculations themselves, but, if done by hand, there is ample room for error. Votes must be bundled and labelled with their weights. It’s not hard to imagine small slips in the calculating, bundling, or labelling steps that could cause an error. Because of this, an argument could be made that BC-STV is pretty close to the limit — or maybe past it — for hand-counted voting schemes.

    - Strictly speaking, BC-STV is a randomized algorithm: there is a possibility where a coin-flip (so to speak) decides the winner. This is exceedingly rare, and if the situations where it is called for ever occurred a re-count would probably be requested (just as if two candidates received nearly an equal number of votes in FPP).

    - Famously, Ireland and Australia, have used variations of STV in various elections for years. Data about counting time and statistics is available on the web. STV-like systems have also been used in various smaller electoral settings (e.g. regional districts, town councils, etc.), and it is clearly practical and effective, if not perfect.

    Despite its imperfections, BC-STV will solve a problem that is commonly seen in BC politics: the governing party usually receives well less than 50% of the popular vote, yet acts in a totally autocratic manner, answering to no one but themselves.

    - john — 5/3/2005 @ 7:08 pm

  15. Hi MS,
    I looked at your example, and the only possible distribution for the 61 ballots is:
    11 C-B-A (C first, B second, A third)
    20 B-C-A
    10 A-B-C
    20 A-C-B
    In the FPP system, Amanda wins (or Amelie, or Anna…).
    In the BC-STV system, Bernadette wins.
    In the “Borda count” system, Caroline wins.
    Ha! What a joke! However, I think the FPP still does the best job here…

    But I thought of a “middle-ground” system: each voter marks a single X for his first preference, just as simply as now with the FPP. But we take bigger ridings with more than one winner in each riding, as in STV. We apply FPP for the first winner, and redistribute the weighted surplus of his votes to determine the second winner, and so on… Reading about one’s comment about partially valid ballot made me wonder if people, even if they were conviced the STV was to give a better representation of their preferences, would decide that STV is so complicated that it is not “worth” the change.

    John, were is the STV randomized? Kepp in mind that if two candidates get the quota, they both get elected in the same round, and then their surplus get redistributed. I agree it would be random if one of them came before the other, but it is not the case here.

    And for the ones having fun with the O(n) vs O(mn), I think it is reasonable to assume m proportional to n, but I would add that n cannot become very big, as the riding would the get split into two smaller ones.

    Does all this stuff on your side mean that it will eventually migrate to our side? But of course, it would be a bit different. After all, we are a “societe distincte”, we could not just take it as is…

    - happy not to live in BC — 5/3/2005 @ 9:25 pm

  16. In BC-STV, randomness occurs when two or more winning candidates tie for first preference votes after the first count. Lots are used to decided whose surplus is distributed first. Also, in the first count, if two or more candidates tie for last place on first preference votes, then the one who is dropped is chosen by lot.

    After the first count, these ties are broken by referring to winners of previous counts, or again by lot if they tied on all previous counts.

    Practically, this isn’t a very big deal. A smarter tie-breaking rule would be to look at the later preferences of the voters.

    The Citizens Assembly technical report goes through the details of this and the rest of the counting procedure: http://www.citizensassembly.bc.ca/resources/TechReport.pdf

    - john — 5/3/2005 @ 10:46 pm

  17. John - thanks so much joining the discussion - I’m finding your comments really helpful. If I may ask, are you involved in any STV-related campaign, or research on voting? (Feel free to email me if you don’t want this public, and feel free to ignore the question entirely if you don’t want this known at all.) I was just about to ask what you meant by randomness, but you explained it. Another, related question - apparently if one candidate is elected on the nth ballot, then on the (n+1)st ballot, the surplus votes are distributed to the next choice of the ballots that chose the elected candidate. (At least, that’s what I gather from the explanation here.) Of course, however, there are fewer surplus votes for the newly-elected candidate than there are total votes for that candidate. So are ALL of the ballots that chose the elected candidate screened for the next choice, and those choices then tallied and weighted so that the total number of votes stays the same? Or are some of those ballots selected randomly? (ETA - I assume that answer’s in the 271 (!)-page report, but I’m not going to read it now - might get around to skimming it later this week.)

    HntLiBC - in another thread, wolfangel mentioned that the BC referendum has actually been getting a lot of press in Quebec, because of the possibility that it could migrate to BC. This would apparently hurt the PQ, and it looks like they’ll be in power soon, so I can’t imagine STV would be making its way out east that soon. (Then again, it was BC’s Liberal party that introduced the STV referendum, which would hurt them more than any other provincial party. But, as someone pointed out to me, if they really wanted STV to pass, they’d have passed it themselves, rather than toss it over to us for a referendum.)

    Regarding the distribution I gave for A, B, and C, that’s a reasonable approximation (and exaggeration) of what we could expect federally if A=Conservatives, B=Liberals, C=NDP. Polls consistently show that the Conservatives are essentially no one’s second choice - voters either love them or hate them. Canadians are pretty meh on the Liberals, routinely voting for them but with little enthusiasm. They’re a second choice for many. The NDP tends to do rather badly, but a lot of voters mention that they’d vote for them, but for the fact that (pick your reason: the NDP can’t be trusted with money, it’s a wasted vote, it’s more important to shut the Conservatives out and if that means voting NDP, so be it, etc…) - in STV I figure they’d gain a lot because the “anyone but the Conservatives” consideration wouldn’t feature as prominently. (For this reason, STV is a lot less vulnerable to manipulation and strategic voting.)

    - Moebius Stripper — 5/3/2005 @ 11:09 pm

  18. Counting ballots by hand? Hell no. What I am interested in is a hardcopy of all ballots. Of course, I live in NYC and still have to vote on one of those antiquated lever machines. There’s no proof of individual ballots.

    When I lived in North Carolina, we used paper ballots, and you filled in a space to indicate your choice. Then, as you left the polling place, you ran the ballot through a scanner, which checked that you didn’t mess up the ballot (if you did, it spat out the ballot and you got a do-over.) If it passed, it added your votes to its count and then dumped the ballot into a secured box. If there was a problem later with the vote count, someone could take the ballots out and rescan them or count by hand, if need be.

    I don’t know why they have to use computer touch screens for voting. It sounds expensive and relatively easy to screw up. Scannable paper ballots, I say! I suppose computer systems could print out a scannable paper ballot… hmmm. But then that just adds to the expense unnecessarily.

    - meep — 5/4/2005 @ 7:04 am

  19. I’m not involved in any campaign for STV, nor have I done research in voting. Although I have had research interests in problems that have lead me to look “fair division” protocols, which covers some of the same ground. Mainly, though, I have read through the BC-STV protocol in enough detail to write a program for doing the counting (I gave up on that when I discovered the SourceForge STV programs).

    BC-STV transfers votes using a method they call “weighted Gregory”: ballots of winning candidates are transferred at a discounted value. Initially, all votes have a value of 1.

    Suppose Juanita (and no one else) is elected on the first count, and that she received 100 votes in excess of what she needed to win (to win, a candidate must meet a pre-determined quota of votes equal to 1 + (#voters)/(1 + #people to elect)). This extra 100 votes is called her “surplus”, and then the value of these ballots are “marked-down” according to this formula:

    transfer value = (#of surplus votes for Juanita) / (#of votes in total for Juanita)

    All of these surplus votes are marked with this transfer value, which is used for counting their value. These ballots are then put into “parcels” according to their second-choice, and then these packets are “transferred” to the other candidates (ballots with no second choice are declared “exhausted” and are discarded).

    If more than one candidate wins in the first count, then the transfers are done in the order of most first-choice votes to least (using lots in the unlikely event of a tie).

    In later counting rounds, when a candidate wins then essentially the same thing happens, except the transfer value of the parcels is taken into account.

    For candidates who are dropped (in the case when no candidate meets the winning quota), the dropped candidates first-place votes and transferred parcels are then transferred to the next preferred candidate (or discarded if exhausted) at their current value: first-place votes are all transferred at value 1, and the parcels are transferred at whatever value they have on them when they were transferred to the candidate.

    The details are given on page 17 to 20 of the CA technical report: http://www.citizensassembly.bc.ca/resources/TechReport.pdf

    Also, there’s a text transcription of those pages here: http://cvs.sourceforge.net/viewcvs.py/stv/pSTV/BCSTVRules.html?rev=1.1&view=markup

    - john — 5/4/2005 @ 8:33 am

  20. “The Vancouver Sun has another useless article about how damned little British Columbians know about the single transferable vote system.”

    Well, count yourself lucky. Mention “STV” to an average American, and they’ll probably either think it’s one of those things you can keep from catching if you use condoms, or a new cable network about strippers.

    - fling93 — 5/5/2005 @ 1:46 pm

  21. Oh, and peanut-butter chocolate is NOT a crappy flavor!!!

    - fling93 — 5/5/2005 @ 2:07 pm

  22. Hi folks,

    By the way, there’s an excellent chapter on voting in Paul Hoffman’s “Arcimedes’ Revenge: The Joys and Perils of Mathematics.”

    –Jeff

    - Jeff Boulier — 5/5/2005 @ 7:06 pm

  23. fling93, did you vote in the Ice Cream Election? Cuz if you don’t vote, you can’t complain.

    JB - thanks. You know, I think I might even have a copy of that book somewhere here…haven’t looked at it in ages.

    - Moebius Stripper — 5/5/2005 @ 8:16 pm

  24. No, of course I didn’t. But when Dubya decides to preemptively invade Canada, you guys can’t complain either!

    - fling93 — 5/6/2005 @ 9:33 am

RSS feed for comments on this post.

Sorry, the comment form is closed at this time.