David M. Pennock
Artificial Intelligence Lab
University of Michigan
Ann Arbor, Michigan 48109-2110
Eric Horvitz
Decision Theory & Adaptive Systems Group
Microsoft Research
Redmond, Washington 98052-6399
Access postscript or pdf file.
The growth of Internet commerce has stimulated the use of collaborative filtering (CF) algorithms as recommender systems. Such systems leverage knowledge about the behavior of multiple users to recommend items of interest to individual users. CF methods have been harnessed to make recommendations about such items as web pages, movies, books, and toys. Researchers have proposed several variations of the technology. We take the perspective of CF as a methodology for combining preferences. The preferences predicted for the end user is some function of all of the known preferences for everyone in a database. Social Choice theorists, concerned with the properties of voting methods, have been investigating preference aggregation for decades. At the heart of this body of work is Arrow's result demonstrating the impossibility of combining preferences in a way that satisfies several desirable and innocuous-looking properties. We show that researchers working on CF algorithms often make similar assumptions. We elucidate these assumptions and extend results from Social Choice theory to CF methods. We show that only very restrictive CF functions are consistent with desirable aggregation properties. Finally, we discuss practical implications of these results.
Keywords: Recommender systems, collaborative filtering, agents, Arrow's impossibility theorem, preferences, probability, decision theory.
In: AAAI Workshop on Artificial Intelligence for Electronic Commerce, National Conference on Artificial Intelligence (AAAI-99), July 1999, Orlando, Florida.
Author Email: dpennock@umich.edu, horvitz@microsoft.com