Learning Valuation Functions
Maria-Florina Balcan
Florin Constantin
Satoru Iwata
Lei Wang
10.1184/R1/6475859.v1
https://kilthub.cmu.edu/articles/journal_contribution/Learning_Valuation_Functions/6475859
<p>A core element of microeconomics and game theory is that consumers have valuation functions over bundles of goods and that these valuations functions drive their purchases. A common assumption is that these functions are subadditive meaning that the value given to a bundle is at most the sum of values on the individual items. In this paper, we provide nearly tight guarantees on the efficient learnability of subadditive valuations. We also provide nearly tight bounds for the subclass of XOS (fractionally subadditive) valuations, also widely used in the literature. We additionally leverage the structure of valuations in a number of interesting subclasses and obtain algorithms with stronger learning guarantees.</p>
2012-06-01 00:00:00
learning
valuations
no complementarities
algorithmic game theory
economics