Responsible RecSys by Design: Approximation Algorithms for Calibrated Recommendations with Sponsored Items

Calibrated Recommendation Systems (CRS) balance user preferences with constraints like diversity, fairness, and novelty to create inclusive recommendation lists. However, existing research often overlooks the mandatory inclusion of sponsored items, assuming unrestricted product selection. In practice, sponsored items, paid for by advertisers, must be included, which can conflict with CRS goals when advertisers' priorities misalign with system objectives. This paper addresses this gap by formulating CRS with sponsored items as a combinatorial optimization problem. We develop efficient approximation algorithms to generate the most calibrated recommendation lists while meeting sponsorship requirements.