User choice, hidden gems, and the quadratic horizon

Content platforms typically engage with their users through small recommendation sets of items drawn from an extensive catalog. These sets are curated using machine-learned models optimized to present choices most likely to align with user preferences. We present surprising findings about such platforms. Even with complete information on user preferences within sets of up to k items, these models can only predict preferences within a "quadratic horizon" of $k^2$ items and might fail to identify the best items in larger sets. To illustrate, we present striking examples where a platform interacting with users through small item sets, despite knowing that one item is favored by millions of users, cannot identify this item with better than random chance. Through both theoretical analysis and studies across various datasets, we demonstrate that "hidden gems," items preferred by many users but invisible to platforms, exist in real-world datasets of moderate size, highlighting a significant gap in current recommendation platforms.