A “feed,” a personalized list of content, is the new normal for content consumption on the web. Whether in the form of a news feed based on search criteria from favorite news websites, or in the form of a personalized radio station, the consumption of content via feeds is clearly on the rise.

Feeds are monetized by inserting advertisements between the items in the feed, such as a radio commercial between two songs played on Pandora or a text advertisement inserted between two news stories. Hence, there is a clear need for sophisticated mathematical models that maximize the monetary value of the feed while providing a consistent experience to end users at the same time.

In this paper, the authors first study the problem of inserting ads in the content feed in order to maximize the monetary value. They formulate the problem as a reward maximization problem, where the reward is a function of the advertisements, their utility values, and the placements selected for those advertisements. The crux of the problem is that the probability that a user observes the nth item or advertisement is a nonlinear decreasing function of n, and is not a constant. This creates a nonlinear term in the objective function, which renders the overall optimization problem hard to solve using maximum matching algorithms.

To solve this, the authors first present a four-approximation algorithm by discretizing the nonlinear term, and then generalize the idea therein to create a polynomial-time approximation scheme (PTAS). An obvious question arises: Assuming the probability that a user observes the nth item is precalculated in an array and can be interpreted as a constant, does that not render the overall optimization problem trivial, while maintaining the utility of the practical scenarios presented in the paper?

In the second part of the paper, the authors present a mechanism design problem in which the network must assume that the advertisers need not be truthful when revealing the utility value of showing their advertisement. For this problem, the authors present an approximate mechanism. Considering the relevance and the hardness of keyword pricing and bidding algorithms, the second problem is significantly more applicable in many practical scenarios.