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?

No comments: