What recommendation algorithms are optimal in (MAB) settings when they compete, and evaluates the intertemporal welfare effect of competition

当像Trivago这样的推荐服务竞争时，消费者会得到什么？参赛者应该选择什么样的推荐策略？本研究项目探讨了在多臂强盗（MAB）环境中，当它们竞争时，什么样的推荐算法是最优的，并评估竞争的跨期福利效应。MAB是一种流行的工具，用于模拟探索-利用权衡-从医学试验到互联网经济。推荐系统试图通过说服消费者选择所需的商品来收集不同产品的收益分布信息。当一个推荐者单独行动时，例如，谷歌的广告收入最大化算法，这个问题得到了很好的研究。然而，很少有人注意到代理人面临来自多个算法的建议的情况。换句话说，现有的文献已经探讨了MAB问题，当客户之间选择的产品，而不是产品推荐pairs.When算法竞争的客户，两个影响消费者效用，（i）对于一组给定的算法，信息获取是缓慢的，因为每个算法观察到一个严格的子集的可用信息，（ii）不同的算法可能会选择在没有竞争的情况下。更聪明的算法将减少持续次优选择的累积遗憾，但由于信息获取，对早期客户的预期效用较低。它们的计算成本也更高。所有这些都提出了关于消费者效用跨期分布的有趣问题。我的研究问题与最近的两篇论文直接相关。在“竞争的强盗：在竞争中学习”中，Mansour et al.（2018）在非常严格的特设假设下推导出一些分析解。Aridor等人（2019）考虑了一种更自然的设置，但使用模拟来近似“竞争下探索的危险：计算建模方法”中的最佳算法。他们的模型的一个共同特点是，客户只收到一个建议。为了模拟像互联网经济这样的设置，检查多个网站实际上是没有成本的，我假设每个消费者都观察每个算法的推荐，然后选择一个产品。竞争的出现是因为消费者只向一种算法透露他们的经验。我计划用分析的方法来解决最优算法。哪种算法是最佳的将在很大程度上取决于客户知道什么。在Mansour et al.（2018）的设置中，基本的贪婪算法获胜，但在Aridor et al.（2019）中，对于足够长的时间，更复杂的算法击败了贪婪算法。同样，对当事人可以观察到的信息的假设也是极其重要的。可以观察到的主体越多，我期望最优算法在任何非合作均衡中越贪婪。我计划在适当的情况下用模拟来补充理论研究结果。这项研究对在线市场的政策制定者和监管者具有重要意义。

Which consumers gain when recommendation services like Trivago compete? What recommendation strategy should an entrant pick? This research project explores what recommendation algorithms are optimal in multi-armed bandit (MAB) settings when they compete, and evaluates the intertemporal welfare effect of competition.MABs are a popular tool to model explore-exploit trade-offs - from medical trials to the internet economy. A recommender tries to gather information on payoff distributions of different products by persuading consumers to choose the desired good. When a recommender acts in isolation, for example, Google's ad-revenue-maximization algorithm, the problem is well studied. However, little attention has been given to situations where agents are faced with recommendations from multiple algorithms. In other words, the existing literature has explored the MAB problem when customers choose between products rather than product-recommender pairs.When algorithms compete for customers, two effects impact consumer utility, (i) for a given set of algorithms, information acquisition is slower as each algorithm observes a strict subset of the available information, and (ii) different algorithms may be chosen in case of no competition. Smarter algorithms will reduce cumulative regret from persistent suboptimal choices but have a lower expected utility for earlier customers due to information acquisition. They are also computationally costlier. All of the above raises interesting questions about the intertemporal distribution of consumer utility. My research question relates directly to two recent papers. In 'Competing Bandits: Learning Under Competition', Mansour et al. (2018) derive some analytical solutions under very restrictive ad hoc assumptions. Aridor et al. (2019) consider a more natural setting but use simulations to approximate the optimal algorithm in 'The Perils of Exploration under Competition: A Computational Modeling Approach'. A common feature of their models is that customers only receive one recommendation. To model setups like the internet economy, where checking multiple websites is effectively costless, I instead assume that each consumer observes a recommendation from each algorithm and chooses a product thereafter. Competition arises because the consumer only reveals their experience to one algorithm.I plan to solve for the optimal algorithm analytically. Which algorithm is optimal will depend heavily on what customers know. In the Mansour et al. (2018) setup, the basic greedy algorithm wins, but in Aridor et al. (2019), for long enough horizons, more sophisticated algorithms beat the greedy one. Similarly, assumptions on the information principals can observe are extremely important. The more principals can observe, the greedier I expect the optimal algorithm to be in any non-cooperative equilibrium. I plan to supplement the theoretical findings with simulations where appropriate. The research has important implications for policymakers and regulators of online markets.