The social proof marketing strategy assumes that the marketer provides a novel product for free to some users of a social network and then promptly recommends the product to other users, by informing them that a number of their friends are already using it. In this paper we study this popular marketing strategy in scenarios where the new product enters in markets where two old products are already competing. We show that if customers tend to adopt the product that is the most popular one (over the three alternative products) among their friends, then this marketing strategy allows to maximize the diffusion of the new product only on a narrow class of networks. Moreover, even if we focus on this narrow class of networks, computing the best order of the recommendations is computationally intractable.

Instead, if customers are less prone to change their mind, that is, if they are willing to adopt some product only when an absolute majority of their friends has already agreed on it, then the marketing strategy always works well and, furthermore, an optimal order of recommendations can be computed in polynomial time.