Tell Me Who I Am:An Interactive Recommendation SystemExtended AbstractNoga Alon∗Tel Aviv U. and [email protected] Awerbuch†Johns Hopkins [email protected] Azar‡Tel Aviv [email protected] Patt-Shamir§Tel Aviv [email protected] consider a model of recommendation systems, whereeach member from a given set of players has a binarypreference to each element in a given set of objects: in-tuitively, each player either likes or dislikes each object.However, the players do not know their preferences. Tofind his preference of an object, a player may probe it,but each probe incurs unit cost. The goal of the play-ers is to learn their complete preference vector (approx-imately) while incurring minimal cost. This is possibleif many players have similar preference vectors: such aset of players with similar “taste” may split the cost ofprobing all objects among them, and share the results oftheir probes by posting them on a public billboard. Theproblem is that players do not know a priori whose tasteis close to theirs. In this paper we present a distributedrandomized peer-to-peer algorithm in which each playeroutputs a vector which is close to the best possible ap-∗Schools of Mathematics and Computer Science, Tel AvivUniversity, Tel Aviv 69978, Israel and IAS, Princeton,NJ 08540, USA. Research supported in part by the IsraelScience Foundation and by the Von Neumann Fund.†Dept. of Computer Science, Johns Hopkins University.Supported by NSF grants ANIR-0240551, CCF-0515080and CCR-0311795.‡School of Computer Science, Tel Aviv University, TelAviv 69978, Israel. Research supported in part by theGerman-Israeli Foundation and by the Israel ScienceFoundation.§School of Electrical Engineering, Tel Aviv University, TelAviv 69978, Israel. Research supported in part by IsraelMinistry of Science and Technology and by the Israel Sci-ence Foundation.Permission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies arenot made or distributed for profit or commercial advantage and that copiesbear this notice and the full citation on the first page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a fee.SPAA’06, July 30–August 2, 2006, Cambridge, Massachusetts, USA.Copyright 2006 ACM 1-59593-452-9/06/0007 ...$5.00.proximation of the player’s real preference vector after apolylogarithmic number of rounds. The algorithm worksunder adversarial preferences. Previous algorithms eithermade severely limiting assumptions on the structure ofthe preference vectors, or had polynomial overhead.Categories and Subject DescriptorsC.2.4 [Computer-Communication Networks]: Dis-tributed Systems; F.2.2 [Analysis of Algorithms andProblem Complexity]: Nonnumerical Algorithms andProblemsGeneral TermsAlgorithms, Theory.Keywordsrecommendation systems, collaborative filtering, random-ized algorithms, electronic commerce, probes, billboard.1. IntroductionInformation fusion, recommendation systems, beliefpropagation networks, collaborative filtering, distributedagent learning are all classical subfields of Computer Sci-ence and Artificial Intelligence. These sub-fields attemptto improve efficiency of multiple agents (human or me-chanical), which are trying to leverage past experience ofothers in spite of significant diversity or uncertainty intheir perception of the world. There are many reasons forsuch diversity, e.g., people may have different taste (forbooks, movies, food, etc.), sensors may experience differ-ent reception due to different location, some eBay usersmay be dishonest, links on websites of different companiespoint to different suppliers preferred by these companies,etc. Even when no inherent diversity appears to exist, var-ious time-variable factors (such as noise, weather, mood)may create diversity as a side effect.There is a tremendous amount of work in AI and CSon modeling such diversity (e.g., [10, 16, 13]); in fact, someconferences are dedicated exclusively to this topic. Intu-itively, it seems that arbitrary diversity is unmanageable,and strong assumption need to be made in order come upwith algorithms algorithmic tools. All existing approachesrestrict diversity somehow, e.g., by assuming that userprofiles are a linear combination of a few “major types.”These assumptions are hard to justify, but superficiallythey appear unavoidable. In this paper, perhaps counter-intuitively, we present novel algorithmic tools that showthat effective (near optimal) collaboration by cooperativeagents is possible even with unrestricted diversity.Many commercial systems (e.g., Amazon, eBay, Epin-ion) are based on explicit or implicit notion of trust anduser preferences. Such preferences may be represented bya matrix where rows represent agents, and columns repre-sent objects. Each entry (i, j) represents the (unknown)opinion of agent i about object j. One of the fundamentaltasks of a recommendation system (e.g., an advertiser likeGoogle) is to reconstruct the full matrix.The challenge in these systems is how to take advan-tage of the existence of users with related opinions: In-tuitively, a set of users with similar preferences shouldbe able to collaborate, implicitly or explicitly, by sharingthe load of searching the object space and sharing the re-sults of their probes. To facilitate information sharing, itis assumed that the system maintains a shared billboard,similar, for example, to the eBay ranking matrix, whereusers post the results of their probes. The difficulty is thatusers do not know whose grades to adopt and that tastesmay differ to some degree even between potential collab-orators. Below, we describe two basic models for recom-mendation systems: interactive and non-interactive.Interactive recommendation system. In this model,the basic action available to algorithms is to reveal a gradethe algorithm chooses, but such an action incurs cost [6,4]. Revealing a grade models the process of a user testinga product, called probing. For example, consider adver-tisement placement. Probing takes place each time theadvertiser provides a user with an ad for some product:if the user clicks on this ad, the appropriate matrix entryis set to 1, and if the user does not click, it is set to 0.In any case, the matrix entry is revealed. The task is toreconstruct, for each user, his preference vector, namelyhis row in the matrix (e.g., so