Home / Papers / CS 269 I : Incentives in Computer Science

CS 269 I : Incentives in Computer Science

3 Citations2016
Tim Roughgarden
journal unavailable

This chapter considers a prediction problem where the goal is to come up with a ranked list, such as the Web pages most relevant to a search query, and several different heuristics for producing such ranked lists.

Abstract

1. Rank aggregation. Here, voters correspond to different ranking algorithms. Consider a prediction problem where the goal is to come up with a ranked list, such as the Web pages most relevant to a search query. Imagine you have several different heuristics for producing such ranked lists. Maybe one heuristic is based on anchor text, another on link structure, and another on the page content. It’s natural to try to combine these different and likely conflicting rankings into a “consensus ranking.” This is exactly a voting problem. The hope is that the consensus ranking is somehow “better” or “more accurate” than the individual rankings. For example, maybe the best pages are high on all of the lists, whereas a spam page is high on only a subset of the lists, and hence is ranked low in the consensus ranking.