http://delivery.acm.org/10.1145/1070000/1064010/p1-altman.pdf?key1=1064010&key2=1714043711&coll=&dl=ACM&CFID=15151515&CFTOKEN=6184618

-or-

http://portal.acm.org/citation.cfm?id=1064010&dl=ACM&coll=&CFID=15151515&CFTOKEN=6184618 (Click on full text PDF)

This article discusses ranking systems, specifically Google’s PageRank. An analogy between page ranking and social choice is examined. Page ranking is compared to agents (pages) preferring other agents (pages). This preference on the internet is found in links between pages.

The paper states that “the current practice of the ranking of Internet pages is based on the idea of computing the limit stationary probability distribution on the Internet graph, where the nodes are pages, and the edges are links among the pages.” This basically means that the result of the search is similar to starting at a related page and than following random links iteratively from page to page. If this procedure is repeated, the pages most often visited should rank the highest in the search results.

The goal of the paper is to find a small set of simple axioms that do not require complex mathematical computations; these axioms should be found in good ranking algorithms.

One axiom discussed is isomorphism, which says that the ranking system should not depend on what the names given to the actual pager are. Another axiom is called “Vote by Committee” and says that if a page (call it a) links directly to two other pages (pages b and c), the same relative rankings should be given to all pages as in the case when a links to another page d that only links to b and c. Another axiom is called “Collapsing” and says that if a set of pages links to a and b, and a and b in turn link to another set of pages, this is equivalent to collapsing a and b into a single node. The paper goes on to prove that these and a few other more subtle axioms are satisfied by Google’s PageRank ranking system.

In the authors’ conclusion, they state that more work is clearly needed to “isolate the ‘essence’ of particular ranking systems,” but the paper does a good job at getting at some basic axioms that should be satisfied by successful ranking algorithms.