Recommendation systems often face exploration-exploitation tradeoffs: the system can only learn about the desirability of new options by recommending them to some user. Such systems can thus be modeled as multi-armed bandit settings; however, users are self-interested and cannot be made to follow recommendations. We ask whether exploration can nevertheless be performed in a way that scrupulously respects agents’ interests—i.e., by a system that acts as a fiduciary. More formally, we introduce a model in which a recommendation system faces an exploration-exploitation tradeoff under the constraint that it can never recommend any action that it knows yields lower reward in expectation than an agent would achieve if it acted alone. Our main contribution is a positive result: an asymptotically optimal, incentive compatible, and ex-ante individually rational recommendation algorithm.

In the on-line Explore & Exploit [E&E] literature, central to Machine Learning, a central planner is faced with a set of alternatives, each yielding some unknown reward. The planner's goal is to learn the optimal alternative as soon as possible, via experimentation. A typical assumption in this model is that the planner has full control over the experiment design and implementation. When experiments are implemented by a society of self-motivated agents the planner can only recommend experimentation but has no power to enforce it. The first paper to marry the social aspects with the challenge of E&E, a new research domain for which we coin the term "social explore and exploit", is Kremer et. al. [Kremer et al. 2014]. In that work the authors introduce a naive setting (We use the notion of a "naive setting" for settings where the optimal non-social explore and exploit scheme is trivial - try all actions sequentially, each once, and settle on the optimal one thereafter) and study optimal explore and exploit schemes that account for agents' incentives.