On-Line Profit-Maximization Algorithms for Managing Sponsored Content in Cellular Networks

Recent years have seen an explosion in the use of cellular data connections, which results from the rapid adoption of smartphones and tablets. The emerging demand for data services enables Wireless Service Providers (SPs) to increase their revenue by offering various data plans to their users. Currently, SPs explore another potential source of revenue by allowing Content Providers (CPs) to sponsor users' requests, referred to as sponsored content. In this option, CPs can place bids on specific user requests, if a bid is selected then the chosen CP provides the requested content and compensates the SP for the service cost. The user benefits from free content without charging his data plan. In this work we explore various aspects of sponsored content in cellular networks and the eco-system that they yield between the SPs, CPs and mobile users. Then, we present different on-line algorithms for maximizing the combined profit of a given SP both from the users data plans as well as sponsored content. We consider two commonly offered data plans; pay-for-usage and fixed-quota. In the first plan, a user fee is proportional to the amount of unsponsored content that it consumed and for this plan we describe a $k$-competitive algorithm, where $k$ is a limited number of allowed profit-ratios. We also show that this competitive ratio is tight. In the fixed-quota data plan, a user pays a fixed fee for the rights to obtain pre-determined amount of unsponsored content. We show for this date plan that there is no on-line algorithm with bounded competitive ratio, however, by relaxing the requirements efficient on-line algorithms are introduced. Our extensive simulations show that the proposed algorithms outperform alternative solutions and yield near optimal profit for the SPs.