Estimating Random Utility Models over Bundles with Large-Scale Linear Programming
Abstract
This paper develops a simulation-based estimator for random utility models over combinatorial choice sets. When utility is linear in parameters, minimizing the average regret—the difference in utility between the observed choice and the optimal alternative under simulated shocks—yields a convex objective function. Convexity overcomes the computational hurdles of the standard simulated method of moments, enabling the estimation of high-dimensional parameter vectors such as item fixed effects and complementarities. I recast the sample objective as a linear program and solve it via constraint generation. In the numerical experiments, constraint generation terminates in far fewer iterations than worst-case convex optimization benchmarks. I establish formal consistency and asymptotic normality in the standard many-observation limit, with the number of choices and parameters fixed. I then use numerical experiments to demonstrate the method's scalability to single-profile large combinatorial objects, such as supermodular potential games. Finally, I apply the framework to the 1996 FCC C-Block spectrum auction. After estimating geographic complementarities and license-specific fixed effects from the realized allocation, I evaluate counterfactual bundling policies where licenses are aggregated into a coarser geographical partition, finding that it would have lowered both seller revenue and bidder surplus.