Information Retrieval Meets Game Theory: The Ranking Competition Between Documents’ Authors

摘要

In competitive search seŠings as theWeb, there is an ongoing rankingrncompetition between document authors (publishers) for certainrnqueries. Œe goal is to have documents highly ranked, and thernmeans is document manipulation applied in response to rankings.rnExisting retrieval models, and their theoretical underpinnings (e.g.,rnthe probability ranking principle), do not account for post-rankingrncorpus dynamics driven by this strategic behavior of publishers.rnHowever, the dynamics has major e‚ect on retrieval e‚ectivenessrnsince it a‚ects content availability in the corpus. Furthermore, whilernmanipulation strategies observed over the Web were reported inrnpast literature, they were not analyzed as ongoing, and changing,rnpost-ranking response strategies, nor were they connected to thernfoundations of classical ad hoc retrieval models (e.g., content-basedrndocument-query surface level similarities and document relevancernpriors). We present a novel theoretical and empirical analysis of thernstrategic behavior of publishers using these foundations. Empiricalrnanalysis of controlled ranking competitions that we organizedrnreveals a key strategy of publishers: making their documents (gradually)rnbecome similar to documents ranked the highest in previousrnrankings. Our theoretical analysis of the ranking competition as arnrepeated game, and its minmax regret equilibrium, yields a result thatrnsupports the merits of this publishing strategy. We further showrnthat it can be predicted with high accuracy, and without explicitrnknowledge of the ranking function, whether documents will bernpromoted to the highest rank in our competitions. ThŒe predictionrnutilizes very few features which quantify changes of documents,rnspeci€cally with respect to those previously ranked the highest.