Good advice costs nothing and it's worth the price: incentive compatible recommendation mechanisms for exploring unknown options

Abstract

Recommender systems are valuable to their users to the extent that they have unique information about which options are best. One way that such a system can gain this knowledge is by recommending that a user explore an option whose value is unknown, and receiving the feedback of the user. If this is done too often, though, the quality of the recommendations provided may su ffer to the point where users begin ignoring the system altogether. Therefore, I study the mechanism design problem of how a recommender can quickly learn the values of unknown options, within the constraint that it still be in agents' interests to follow the recommendations. The main conceptual contribution is a simplifying abstraction that transforms the problem from one of making decisions based on the total set of possible histories, into an acquisition problem where purchases made at one time a ffect the budget available in the future. I also characterize the optimal policy for exploring all options in a class of special cases, and prove that the recommender can decrease the time necessary to explore a particular target option by introducing new options.