  In the on-line Explore and Exploit 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. Kremer et al
(JPE, 2014) introduce the first study of explore and exploit schemes that
account for agents' incentives. In their model it is implicitly assumed that
agents do not see nor communicate with each other. Their main result is a
characterization of an optimal explore and exploit scheme. In this work we
extend Kremer et al (JPE, 2014) by adding a layer of a social network according
to which agents can observe each other. It turns out that when observability is
factored in the scheme proposed by Kremer et al (JPE, 2014) is no longer
incentive compatible. In our main result we provide a tight bound on how many
other agents can each agent observe and still have an incentive-compatible
algorithm and asymptotically optimal outcome. More technically, for a setting
with N agents where the number of nodes with degree greater than N^alpha is
bounded by N^beta and 2*alpha+beta < 1 we construct incentive-compatible
asymptotically optimal mechanism. The bound 2*alpha+beta < 1 is shown to be
tight.

Computer Science and Game Theory