2

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.