Algorithms and cooperation models in caching and recommendation systems

In the context of on-demand video streaming services, both the caching allocation and the recommendation policy have an impact on the user satisfaction, and financial implications for the Content Provider (CP) and the Content Delivery Network (CDN). Although caching and recommendations are traditionally decided independently of each other, the idea of co-designing these decisions can lead to lower delivery costs and to less traffic at the backbone Internet. This thesis follows this direction of exploiting the interplay of caching and recommendations in the setting of streaming services. It approaches the subject through the perspective of the users, and then from a network-economical point of view. First, we study the problem of jointly optimizing caching and recommendations with the goal of maximizing the overall experience of the users. This joint optimization is possible for CPs that simultaneously act as CDN owners in today’s or future architectures. Although we show that this problem is NP-hard, through a careful analysis, we provide the first approximation algorithm for the joint problem. We then study the case where recommendations and caching are decided by two separate entities (the CP and the CDN, respectively) who want to maximize their individual profits. Based on tools from game theory and optimization theory, we propose a novel cooperation mechanism between the two entities on the grounds of recommendations. This cooperation allows them to design a cache-friendly recommendation policy that ensures a fair split of the resulting gains.