טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentRosenberg Itay
SubjectLearning Dynamics in Information Retrieval Games
DepartmentDepartment of Industrial Engineering and Management
Supervisor Professor Moshe Tennenholtz


Abstract

We consider a game-theoretic model of information retrieval with strategic authors.
We examine two different utility schemes: authors who aim at maximizing exposure
and authors who want to maximize active selection of their content (i.e., the number
of clicks). We introduce the study of author learning dynamics in such contexts. We
prove that under the probability ranking principle (PRP), which forms the basis of
the current state-of-the-art ranking methods, any better-response learning dynamics
converges to a pure Nash equilibrium. In addition, we show a lower bound in the worst case for the time required until convergence is guaranteed. We also show that other ranking methods induce a strategic environment under which such a convergence may not occur. Our study is also concerned with another aspect of the dynamics of the system, by considering situations where the number of authors can increase. We prove that under some natural assumptions, the PRP is the only ranking method that the social welfare cannot decrease when the number of authors is increasing. Together, the results in this thesis expose two fundamental strong properties of PRP, comparing to alternative mediators. This is in contradiction to the previous fndings on weaknesses of the PRP.