Saturday, October 27, 2007

Facetiousness immitates the academy...

...sort of.

A few weeks ago, I wrote a rather lengthy post on an alternative voting system, based on Google's algorithm for ranking websites. It was more of a thought experiment than a serious proposal.

Recently, while researching something on a different, though related, topic, I found out that the main idea behind Google's algorithm is a variation on something called the Kendall-Wei method. Wanting to know more about it, I decided to google Kendall-Wei. To my surprise, the fourth page that came up is a paper titled "An Introduction to Vote-Counting Schemes" [1]. So I'm not the first person to make a connection between Google's ranking of websites and the ranking of political candidates. Although, the use of the Kendall-Wei method described in this paper is quite different from my suggestion (thus the "...sort of" at the beginning of this post). Nevertheless, the fact that someone else besides me has connected elections with the use of the Kendall-Wei method, suggests that perhaps I ought to be taking my ideas more seriously. Expect me to announce the publication of my paper on the subject soon.

[1] You probably won't be able to download the paper, unless you happen to be on a university campus with a subscription to JSTOR.

Thursday, October 25, 2007

From the Mouths of Undergrads

Me: Do you recognize this sequence?
Student: It's not the Fibonacci sequence is it?
Me: No.
Student: Then what -nacci is it?

Wednesday, October 24, 2007

Thanks to the magic of facebook, I've discovered that today is poutine day. I'm not sure that today is actually poutine day, but supposing that it is, then, you're probably interested in knowing what it is. According to the facebook friend that I learned about the day from, "poutine day is, quite simply, the day on which we all eat poutine. Nothing says friendship more than fries smothered in gravy and cheese." Nothing like celebrating friendship by eating food that will likely end all of your lives early. Anyway, now you know. The 24th of October is poutine day. A great way to kick off the last-week-of-October season, which ends with Hallowe'en, that long slow feast of sugar consumption which could finish off the job that the poutine didn't.

Speaking of days with names, apparently, October 2 is Name Your Car Day. I've decided to name my car John Coffey. So. Happy belated Name Your Car Day. Last time I named my car, it ended up needed replacing within half a year. Hopefully the naming of the car was not the cause of its unexpected demise.

It's old news now, but one of McGuinty's first moves in his second term as Premier of Ontario is to declare a new holiday called Family Day, to take place on the third Monday of February. I think a better name would be Thanks For Nothing Day. I've been getting this day off for quite some time now, including the four days following it. These five days, as a whole, are referred to by students as "reading week". It's a secret we've all been keeping that we get these days off in February. Now that I see that I'd be getting shortchanged on a holiday, though, I think it's time to let the cat out of the bag [2]. The third Monday in February is also known as Heritage Day. I know this because every year around the time of our (formerly) secret week off, we get an email saying that the administrative staff have the day off [3]. I'm pretty sure it applies to a lot of other public servants too. So they don't get anything off either. Maybe that's why one of the secretaries nearly bit my head off the last time I locked myself out of my office and needed her to let me back in. Furthermore, the proposed holiday is in February. February folks. It's cold then! Presumably, by the name, the purpose of the holiday is to spend time with family (which, was the purpose behind other holidays). It makes sense to have a week off during this time of year, because you can go away to somewhere warm. But how far away can you get on a long weekend? Not very far, and wherever that is, it'll probably be just as cold. If Thanks for Nothing Day doesn't just doesn't have that ring, perhaps you could call it Take Your Kids Outside and Have Them Freeze Day. Speaking of weeks off. There's another week off around them time of year. This was a well kept secret too until the passport fiasco of earlier this year, when hordes of people were lined up for hours to get their passports so that they could go away for March Break. I guess I shouldn't speak for everybody. Not everyone lives the comfortable academic life like I do. If you're one of those, I hope you have fun with your family in the middle of winter. I, on the other hand, will be too busy with my reading week to enjoy Family Day.

[1] A friend with whom real life communication has almost exceeded by facebook communication. Real life communication itself has centred around the pros and cons of facebook.

[2] It wasn't really that hard to keep this a secret, since, as a graduate student, I mostly just talked to other graduate students, if I talked to anyone at all. It was a bit tricky, though, to come up with a fake reason for skipping a week of class on the third week of February six years in a row.

[3] And when the administrative staff have the day off, then there's not much point in the rest of us coming in. We're pretty much lost without them. Well, I know that I am. Whatever it is they get paid, it's probably not enough [4].

[4] I'm still too lazy to hyperlink my footnotes [5].

[5] I'm also too lazy to proofread. Please don't mind the typos.

Sunday, October 14, 2007

Friday, October 12, 2007

Post Election Thoughts

This past Wednesday, the province of Ontario held its latest provincial election. I didn't vote. If my memory serves me correctly, this is the first provincial election that I have not voted in since I've been eligible to vote. The party I would normally vote for doesn't seem to do well in this riding, and, besides, most of the campaign seemed to pass me by with out my noticing. I've been busy [1] and didn't have time to register in this riding (since it's not my home riding). All in all, it didn't seem worth my while to seek out a local polling station for them to tell me to go to another polling station where I would then find out that I lack sufficient documentation to prove my residency. Anyway. Enough with the excuses.

As usual we--and by we, I mean everyone but me--voted on who would form the next Government of Ontario. We also voted on whether to maintain the current first past the post (FPTP) system of representation, or to implement a new mixed member proportional (MMP) system of representation.

The Election

Aside from one issue, as far as I could tell, the election was mostly a matter of The Dud We Know vs. The Dud We Don't. Perhaps Archie comics have had a more profound effect on my life than they should have, but I don't think I could vote for a party led by a guy named Dalton. Even the new and improved Dalton seems to be at least 50% weenie. The main features of John Tory are that is first name is not Dalton, and that his last name is also the nickname of the party he leads.

I don't recall much that Dalton's done during these last four years. Somewhere along the line he did one or two things that I thought were good ideas at the time. I can't even remember what those were. He might even have broken one of his promises in order to do one of the things that I liked. For the most part, however, I didn't care enough to vote against him. John Tory didn't have much to offer me to get me out to vote for his party. I think he campaigned against Dalton's broken promises. As you may have guessed, that wouldn't be enough to entice me to vote for his party. There was the usual talk about tax cuts that we expect from the PC's, but nothing really inspiring. Then there was the issue of extending public funding to faith based schools. I doubt that this was part of any grand philosophy, nor that he meant it to be an election issue like it was. My guess--I feel it's more like stating the obvious than guessing--is that the leader was trying to win some votes from religious conservatives.

The spectre of religious groups receiving public funding certainly frightens a lot of people, myself included. As a religious person, the spectre of having my faith based organization funded by--and ultimately controlled by--the government certainly frightens me.

It was rather amusing to witness the reactions of the not-so-religious to the proposal here in Canada, where separation of church and state seems much more like something we fell into--if we really do have it at all--than a founding principle, and especially in Ontario, where a large number of students attend Catholic schools, which I presume, by their name, are based on some sort faith that I've heard about once or twice called Catholicism. Correct me if I'm wrong. If it is fear of funding fundamentalism, then the opponents need only take look at these schools. Hardly hotbeds of extremism. If they were to become so, the government would likely step in and stop them, as they've done before. If the Catholic schools are any example, then extending funding to all faith based schools is likely a better antidote to extremism than not. If it is the grand principle of separation of church and state that concerns them, then they should be agitating to withhold funding from Catholic schools just as passionately as they are to keep it withheld from other nonCatholic faith based schools. It doesn't seem like those who are arguing against it know what they're really arguing against. Nor does their position seem all that consistent.

Dalton disallowed all forms of religious arbitration, including Catholic, when Sharia courts were proposed a few years ago. He wasn't going to pick and choose which religious groups should be allowed arbitration, so he banned them all from doing it, even if they had already been doing it. If he is so opposed to other religious groups receiving public funds, why hasn't he taken the same position he did with religious funding as he did with religious arbitration? It's not like he hasn't taken a position on continued funding of Catholic schools. A quick google search will yield quotes from the man himself assuring the schools that they will continue to be publicly funded. So much for consistency. Sure there's the issue of the constitution. Damn the constitution, I say. This is important! Other provinces have gotten over this hurdle. I don't see why we can't.[2]

The Referendum

As I predicted, the No vote won. I'm surprised at how much it won by, however. I was expecting popular support for MMP to be at least 50%, but it didn't even make 40%. The number of ridings with more than 50% support was much smaller than I expected, too. Only 5 riding had more than 50% support for MMP.

Initially, I was opposed to any form of proportional representation (PR). There were primarily two parties who advocated it. These parties, of course, were the ones who had the most to gain if some form of PR was adopted. Much of their advocacy came across as thinly veiled self-interest, clothed in the rhetoric of fairness. Not only that but telling me "If Ontario had PR, then we would have more seats/at least one seat" was certainly not the way to advertise PR to me. I was happy with the number of seats those parties had, and wouldn't be upset if they had less. But to have more of them? I'll pass, thank you.

After hearing more about it from less self-interested parties, though, I warmed up to more. Not enough that I wanted it, but enough that I was disappointed that it didn't receive more support. If I could have voted "maybe", I'm might have been passionate enough about that option to have registered and gone out and voted.

There were a number of other objections that I raised to PR before I was told about any specific form of PR (there seem to be many). The MMP system seemed to take care of a lot of them. I wasn't crazy about the fact that there would be two types of MPP's. Don't ask me why, though. I don't know. Perhaps the hordes of objections to two tier health care that I've heard have instilled in me a latent dislike for two tiered anything, including MPP's.

I did like the possibility that I would be able to vote for the party and the local candidate separately. When I was back in Hamilton on Thanksgiving weekend, for example, I saw that there was candidate who I thought would be a good MPP, but who wasn't running for a party that I would normally support If we had MMP, I could have voted for him, but some other party. (Well, actually, I wouldn't have been able to vote for him, even I were voting in Hamilton. He was in the wrong riding.)

There are other things that MMP would have left unfixed, and might actually have made worse. For example, even under FPTP, MPP's are often elected with considerably less than 50% of the vote in their ridings. In that case, it is not so much that the MPP's are the best representatives, but rather they are the least-bad representatives. This is in part a function of the size of the ridings. Under the proposed MMP system, there would have been fewer ridings than now, so they would be larger, exacerbating the problem.

One of the strangest criticisms of the referendum that I've read in the wake of its outcome is that the material given out by the government was presented neutrally and without bias. How terrible that they would give me only the facts and let me think for myself and make up my own mind. Fascists the lot of them. Is it too late to vote out the bums? What? It is? Dammit!

I wonder why electoral reform has to go to referendum, as it just did in Ontario, and as it has previously in BC. What's to stop a (purportedly ill-gotten majority) government from simply legislating it. I wonder if McGuinty comes off as a hero to PR advocates for putting it to referendum, or if he comes off as a coward for doing so rather than just legislating it. If 60+% of the voters are happy with the system through which he obtained his ill-gotten majority, could that mean that it is not so ill-gotten? If the ill-gotten majority government did legislate some form of PR, would that new system be illegitimate because the government that legislated it had a majority of seats with less than 50% of the popular vote?

I've heard that some PR advocates are saying that MMP is the wrong form of PR to use. I wonder what they think is wrong with MMP and what they think would be better.

The issue of PR vs. FPTP reminds me of an example of a "paradox" in statistics that I heard about last year. There was an issue of whether Maori were represented adequately on juries in New Zealand. Statistics on Maori representation were presented in two different ways. In one presentation, only local statistics were given. In each jurisdiction, Maori's were underrepresented [3] on juries. In another presentation, only national statistics were given. In this case, Maori's were overrepresented [4]. Arguing that Maori's are underrepresented by the first presentation is analogous to choosing governments by FPTP. Arguing that Maori's are overrepresented based on the second is analogous to choosing governments by PR. It is not clear to me which statistics are relevant in determining whether the Maori are adequately represented on juries. Assuming that the analogy is legitimate, is it any clearer whether we should choose FPTP or PR?

[1] Read "lazy". But really. I didn't even use what spare time I had to do stuff for myself, such as grocery shopping. I'm so lazy, in fact, that I'm not going to bother hyperlinking my footnotes today.

[2] I once read that Ontario Catholics (and not Catholics in other provinces) have a strong tendency to support the Liberal Party. I wish I had a reference. I don't remember if this support was for the federal party, the provincial party, or both. If this support holds for the provincial party, then I doubt that the Liberals will be advocating this solution the the funding issue any time soon. I could get into conspiracies about McGuinty's own Catholicism, but I won't. Surely it's a coincidence. Surely.

[3] Under suitable definition of underrepresented.

[4] Under suitable definition of overrepresented.

Tuesday, October 02, 2007

Google Democracy

I wrote a post on this topic some time ago, but then decided to abandon it. However, a few days ago I received a brochure from some branch of the Ontario Government regarding the upcoming referendum on whether to replace the current First Past the Post system of representation with the Mixed Member Proportional system. In light of that, I decided to rewrite the post.

About a year and a half ago, I did a presentation in a math seminar on the PageRank algorithm that Google uses to rank pages on the web. They came up with a clever, though simple, idea to rank websites based on links between pages which greatly improved the quality of searches over search engines that predate Google. The algorithm is also resistant to abuse (though not completely abuse proof).

When I was researching the presentation, one of the things I read from Google itself was that it "relies on the uniquely democratic nature of the web". My first instinct when reading that is to groan. Thinking about it a little more, I realized that Google's algorithm really doesn't much resemble any democratic system that I've ever heard of. Later on, I asked myself what if? What if a country were to adopt a system modelled after the PageRank algorithm? How would/could that work?

The main idea behind Google's algorithm is the assumption that a link from webpage A to webpage B means that the author of page A thinks page B is good (of course, the author of A might link to B because of how bad B is, but, to imitateChandler Bing, perhaps the author of A thinks B is a good bad-website.) The term often used is authority. Thus, by linking to B, the author of A confers authority on B. The authority of web page B is then calculated based on the number of links pointing to B from some other website, but in a recursive way, which I'll try to explain now. Using the recursion, their algorithm calculates a score for each page as follows.

  1. Give each page a score of 1.
  2. For each page A, add up the points of the pages that link to A to get a new number. (This will be the number of pages that link to A).
  3. Replace A's score by this new number.
  4. For each page A, add up the points of the pages that link to A to get another new number
  5. Replace A's score by this new number.
  6. Go back to step 4.

At each step, each page gets assigned a new number. The numbers are going to get very large, so at each step they are also "normalized". That is, the numbers are all divided by one number to keep things from getting too large. (The number chosen may differ at each step). This is okay since it is the ranking of scores that is most important, and not so much the score itself, since we want to know the which websites are better than others, and not necessarily how good each site is. The process is repeated until the scores do not differ too much from one step to the next, so that each page has a ``final'' score.

There are a few other steps that are taken to prevent undesirable things from happening. For example if one page has a large number of links to other pages, then that page could have a strong influence on the algorithm and thus the overall ranking, so the "strengths" of links are scaled so that each page (or the author of each page) has the same amount of influence. For example, if there are 10 links from site A, then each of those links counts as one tenth of a link. If there are 2 links from site A, then each of those links counts as a half of a link. If there are n links from site A, then each of those links counts as one n-th of a link.

So why does this work? A rough measure of the authority of a page is the number of other pages that link to it. This is the score after the Step 3. Two pages, call them page A and page B, could have the same number of pages linking to them. At first we might think that the authority of A and B is the same. However, we could look at the pages that link to each of these, and count the total of the number of links into each of those pages instead. That is, we are counting the number of links to pages that link to each of A and B. These will be the new scores for A and B after we do Step 5 the first time (I'm fudging a little bit here). If there are many links to pages that link to A, while there are few links to pages that link to B, then intuitively, we feel A is better than B. So Even though A and B receive the same number of links, A is linked to by sites with more authority than those that link to B. We could go one step further back and count the numbers of sites that link to sites that link to sites that link to A and B and compare them (same fudge as before, but more of it). These numbers are the scores after we do Step 5 the second time. At each stage, the scores of A and B are updated in terms of the scores of the pages that link to them, so that the authorities of A and B are reinforced by the authority of the pages linking to them. A website that is linked to by many sites with a high authority score at each step will end up with a high authority score in the next step. Repeated enough times, the scores stabilize. That is, the scores don't change much from one step to the next. I illustrated this using two sites with the same number of links in, but it is possible that A could have a small number of links in, while B has a large number, but A's authority is higher than B after the process is repeated enough times.

So how would we use Google's idea to decide our elections? Suppose that we were to allow eligible voters to defer all or a portion of their voting rights to someone else. In such a system, I could retain all of my voting rights if I wanted. Otherwise I can defer my voting rights to someone else. In the language of the internet, I have linked to that person. Linking to that person implies voting authority. In the case that I retain my vote, I link back to myself. In between these two extremes, I could retain retain a portion of my voting rights, one half, while deferring the other half of my vote to you. I have linked to myself with a link of weight 1/2 and linked to you also with a link of weight 1/2. Perhaps I could split the remaining half of my vote between you and someone else, so that there is a link to myself with weight 1/2, and a links from me to you and someone else, each of weight 1/4. Otherwise, I could split my voting rights between the three of us evenly, or.... I could divide my vote any number of ways between any number of people, so long as the portions of my vote that I've given to everyone else adds up to 1, in line with the principle of "one person, one vote".

Then a "vote-authority" score would be calculated by a process similar to that described above. The process will be slightly different, because the "weigths" of the links from me to each person can be different, but I won't get into that here. The vote-authority score of person A is reinforced by the vote-authority score of the people that defer a portion of their voting rights to A. On election day, the weight of each persons vote is their vote-authority score. Instead of adding up the number of votes that a candidate gets, the scores of the people that voted for that candidate are added up. Whichever candidate has the highest score wins the riding (or whatever is at stake in the election), rather than the candidate with the largest number of votes.

You might ask why I would want to defer my voting rights to anyone at all besides myself. On election day, I am required to choose one of the candidates in my local riding who I think would best represent the constituents that riding in the legislature, which of course is the one that best represents my own political preferences. Usually, I don't know much about the candidates (though some are easy write-offs). Finding out is a lot of work, and what information I do find may not be reliable. Somebody else might know the candidates better than I do, or else they might know somebody who does. In the first case, they can make a more informed decision than I can. In the second case, they can choose to defer their judgement to a person who knows more about the candidates. Perhaps I just trust that person's judgement on political matters more than I trust my own. Perhaps I'm just lazy, and I want you to vote for me.

The idea that one person's vote could be worth more than another on election day is probably offensive to some. Those people shouldn't get too worked up. I'm not seriously proposing that we implement such a system, or any variation of it (it would probably be hard to implement). I am, however, curious to see how different things would turn out if such a system were implemented. Would the election results be more or less the same as they've always been? Would one party end up dominating? Would the major parties parties receive a larger or smaller share of the "popular vote" than they do now? Even if I were serious, however, I don't think that there would be that much to object to. We would each get one vote. The main difference is that how we use that one vote. Instead of using that one vote to decide on politicians, we use it to decide on who is qualified to decide on politicians. One of the claimed benefits of proportional representation is that it would increase participation in elections. If my crazy system is implemented, people can exercise their right merely by deferring all of their voting rights to someone else, and then staying home at night enjoying the election coverage on tv. How could the privilege to vote without leaving the comfort of your armchair nothing fail to increase participation?

If you think this idea is dumb, by the way, blame it on Google. They're the ones who connected the notion of hyperlinks to democracy in the first place. If you think it's a good idea, however, I expect full credit.

Since the referendum is on MMP, you might be wondering what my thoughts are on that. I think it probably won't pass, since, in order for to pass, it must receive the support of 60% of the population, as well as 50% of the vote in at least 60% of the ridings. Those seem like pretty strict conditions to me. So who cares.

I have my own idea for a system of proportional representation. See, a lot of people criticize the first-past-the-post system on the basis that voters are misrepresented, especially those in less popular parties, since the percentage of province wide (or nation wide) vote share does not translate into the same percentage of seats. MMP would still have 90 of the MPPs chosen by the first-past-the-post system to represent ridings. Of course, as is often the case now, someone could get elected to a riding with less than 50% of the vote in that riding. That means that more than half of the people there are misrepresented. This is simply unfair. In fact, it would be unfair even if the winner received more than 50% of the vote in that riding, since those who voted for other parties get no local representation by their preferred party. Second place candidates often get support in the 20-30% range, and sometimes even higher. If it's unfair that roughly 10% of the population votes Green, yet the party receives no representation, then it is most certainly unfair that an even higher percentage of voters in a riding receives no local representation by their preferred party. Since each voter in a riding should be fairly represented in the legislature, I propose that each candidate be appointed as the MPP of the riding for a time proportional to the vote share. Thus if a candidate gets 40% of the vote, then they are appointed MPP for 40% of the term. The candidate with the highest percentage would go first, followed be the next highest, and so on, until the end of the term. (Thank you McGuinty for fixed election dates, without which this entirely rational scheme could not be implemented.) This would solve both province wide and local discrepancies between voter preference and representation. It would also take care of the fact that we get tired of hearing the same politicians talking for four years straight. Queen's park would be a mad house by the end of the four years, what with the Libertarians picking fights with both Marxist-Leninists and Communists, while latter two parties fight vehemently with each other over policies that are indistinguishable to any unenlightened onlookers. But I'm willing to pay that price for the sake of fairness. What about you?

Monday, October 01, 2007

Opposite to what was, or might naturally be, expected

Near the end of this (rather lengthy) post, I described my car as driving on the green mile, because of the problems with my car that mean it is very likely destined for the scrap yard within the next two years. In particular, the car is certified environmentally unfriendly.

While preparing the post, I googled the phrase "driving on the green mile". To my surprise, among the hits that were not about Stephen King's movie, there was a site referring to Ford's commitment to produce cars that are more environmentally friendly, and later on there is another referring to Mercedes doing the same.

Question Answered

Many times I've been asked "How much wood would a wood chuck chuck if a wood chuck could chuck wood?" though I never knew the answer. In fact, I didn't think there was answer, like that other age old question "What is the sound of one hand clapping?" Courtesy of Oscar Leroy from Dog River, however, I've finally learned that a "A wood chuck would chuck all the would he could chuck if a wood chuck could chuck wood."

Farewell insomnia, and good riddance.