Learning Valuation Functions
1A core element of microeconomics and game theory is that consumers have valuation functions over bundles of goods and that these valuation functions drive their purchases. In particular, the value given to a bundle need not be the sum of values on the individual items but rather can be a more complex function of how the items relate. Common valuation classes considered in the literature include OXS, submodular, and XOS valuations. Typically it is assumed that these valuations are known to the center or come from a known distribution. In this work we initiate the study of the approximate learnability of valuation classes in a distributional learning setting. We prove upper and lower bounds on the approximation guarantees achievable for learning over general data distributions by using only a polynomial number of examples. Our work combines central issues in economics with central issues in optimization (submodular functions and matroids) with central issues in learning (learnability of natural but complex classes of functions in a distributional setting).