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

摘要

In competitive search seŠings as theWeb, there is an ongoing rankingcompetition between document authors (publishers) for certainqueries. Œe goal is to have documents highly ranked, and themeans is document manipulation applied in response to rankings.Existing retrieval models, and their theoretical underpinnings (e.g.,the probability ranking principle), do not account for post-rankingcorpus dynamics driven by this strategic behavior of publishers.However, the dynamics has major e‚ect on retrieval e‚ectivenesssince it a‚ects content availability in the corpus. Furthermore, whilemanipulation strategies observed over the Web were reported inpast literature, they were not analyzed as ongoing, and changing,post-ranking response strategies, nor were they connected to thefoundations of classical ad hoc retrieval models (e.g., content-baseddocument-query surface level similarities and document relevancepriors). We present a novel theoretical and empirical analysis of thestrategic behavior of publishers using these foundations. Empiricalanalysis of controlled ranking competitions that we organizedreveals a key strategy of publishers: making their documents (gradually)become similar to documents ranked the highest in previousrankings. Our theoretical analysis of the ranking competition as arepeated game, and its minmax regret equilibrium, yields a result thatsupports the merits of this publishing strategy. We further showthat it can be predicted with high accuracy, and without explicitknowledge of the ranking function, whether documents will bepromoted to the highest rank in our competitions. ThŒe predictionutilizes very few features which quantify changes of documents,speci€cally with respect to those previously ranked the highest.