Learnability and Stochastic Choice

In this paper, we study a non-parametric approach to prediction in stochastic choice models in economics. We apply techniques from statistical learning theory to study the problem of learning choice probabilities. A model of stochastic choice is said to be learnable if there exist learning rules defined on choice data that are uniformly consistent. We construct learning rules via the procedure of empirical risk minimization, where risk is defined in terms of incentive compatible scoring rules. This approach involves mild distributional assumptions on the model, with the main requirement being a constraint on the complexity of the stochastic choice model. Our main result shows that in the context of stochastic preferences, when the VC dimension of a preference model is finite, then we can recover the distribution over preferences (heterogeneity) in the uniform sense. We provide several applications and obtain general rates of convergence based on sample complexity. Under additional conditions, we establish a converse result for the non-learnability of models. An implication of our non-learnability result is that for any learning rule and sample size, the worst case expected distance between true and estimated choice probabilities is at least half times the maximum possible distance. In binary choice settings, this expected error lower bound is above the error from always predicting that each alternative will be chosen with equal probability. Lastly, we also address recoverability of cognitive heterogeneity and non-uniform learning