Carnegie Mellon University
Browse
- No file added yet -

Learning Valuation Functions

Download (520.61 kB)
journal contribution
posted on 2012-06-01, 00:00 authored by Maria-Florina Balcan, Florin Constantin, Satoru Iwata, Lei Wang

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.

History

Publisher Statement

© 2012 M.F. Balcan, F. Constantin, S. Iwata & L. Wang

Date

2012-06-01

Usage metrics

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC