Calibrated Recommendations for Users with Decaying Attention

There are many settings, including ranking and recommendation of content, where it is important to provide diverse sets of results, with motivations ranging from fairness to novelty and other aspects of optimizing user experience. One form of diversity of recent interest is calibration, the notion that personalized recommendations should reflect the full distribution of a user’s interests, rather than a single predominant category—for instance, a user who mainly reads entertainment news but also wants to keep up with news on the environment and the economy would prefer to see a mixture of these genres, not solely entertainment news. Existing work has formulated calibration as a subset selection problem; this line of work observes that the formulation requires the unrealistic assumption that all recommended items receive equal consideration from the user, but leaves as an open question the more realistic setting in which user attention decays as they move down the list of results. In this paper, we consider calibration with decaying user attention under two different models. In both models, there is a set of underlying genres that items can belong to. In the first setting, where items are coarsely binned into a single genre each, we surpass the \((1-1/e)\) barrier imposed by submodular maximization and provide a novel bin-packing analysis of a 2/3-approximate greedy algorithm. In the second setting, where items are represented by fine-grained mixtures of genre percentages, we provide a \((1-1/e)\) -approximation algorithm by extending techniques for constrained submodular optimization. Our work thus addresses the problem of capturing ordering effects due to decaying attention, allowing for the extension of near-optimal calibration from recommendation sets to recommendation lists.