Learning Valuation Functions

A 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).

Speaker Details

Maria Florina Balcan is a Asst Professor at the School of Computer Science at the Georgia Institute of Technology. Her main research interests are computational and statistical machine learning, computational aspects in economics and game theory, and algorithms. Other interests include mathematical models for signal processing and computer vision. She is the recipient of the CMU SCS Distinguished Dissertation Award, the 2011 Microsoft Faculty Research Fellowship and of an NSF CAREER Award.

Date:
Speakers:
Maria Florina Balcan
Affiliation:
Georgia Institute of Technology