1

Content creators compete for exposure on recommendation platforms, and such strategic behavior leads to a dynamic shift over the …

We propose a new perspective in studying the sequential interactions between a recommender system and a user. Instead of assuming the user is omniscient, static, and explicit, as the classical practice does, we sketch a more realistic user behavior model, under which the user: 1) rejects recommendations if they are clearly worse than others; 2) updates her utility estimation based on rewards from her accepted recommendations; 3) withholds realized rewards from the system. We formulate the interactions between the system and such an explorative user in a $K$-armed bandit framework and study the problem of learning the optimal recommendation on the system side. Our result illustrates the inevitable price the system has to pay when it learns from an explorative user’s revealed preferences on its recommendations rather than from the realized rewards.

We establish a unified framework for strategic classification problems and introduce the notion of strategic VC-dimension (SVC) to capture its PAC-learnability. We instantiate our framework for the fundamental strategic linear classification problem and fully characterize: (1) the statistical learnability of linear classifiers by pinning down its SVC; (2) it’s computational tractability by pinning down the complexity of the empirical risk minimization problem.