Learning Valuation Functions

Maria Florina Balcan, Florin Constantin, Satoru Iwata, Lei Wang
Proceedings of the 25th Annual Conference on Learning Theory, PMLR 23:4.1-4.24, 2012.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v23-balcan12b, title = {Learning Valuation Functions}, author = {Balcan, Maria Florina and Constantin, Florin and Iwata, Satoru and Wang, Lei}, booktitle = {Proceedings of the 25th Annual Conference on Learning Theory}, pages = {4.1--4.24}, year = {2012}, editor = {Mannor, Shie and Srebro, Nathan and Williamson, Robert C.}, volume = {23}, series = {Proceedings of Machine Learning Research}, address = {Edinburgh, Scotland}, month = {25--27 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v23/balcan12b/balcan12b.pdf}, url = {https://proceedings.mlr.press/v23/balcan12b.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Learning Valuation Functions %A Maria Florina Balcan %A Florin Constantin %A Satoru Iwata %A Lei Wang %B Proceedings of the 25th Annual Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2012 %E Shie Mannor %E Nathan Srebro %E Robert C. Williamson %F pmlr-v23-balcan12b %I PMLR %P 4.1--4.24 %U https://proceedings.mlr.press/v23/balcan12b.html %V 23 %X 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.
RIS
TY - CPAPER TI - Learning Valuation Functions AU - Maria Florina Balcan AU - Florin Constantin AU - Satoru Iwata AU - Lei Wang BT - Proceedings of the 25th Annual Conference on Learning Theory DA - 2012/06/16 ED - Shie Mannor ED - Nathan Srebro ED - Robert C. Williamson ID - pmlr-v23-balcan12b PB - PMLR DP - Proceedings of Machine Learning Research VL - 23 SP - 4.1 EP - 4.24 L1 - http://proceedings.mlr.press/v23/balcan12b/balcan12b.pdf UR - https://proceedings.mlr.press/v23/balcan12b.html AB - 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. ER -
APA
Balcan, M.F., Constantin, F., Iwata, S. & Wang, L.. (2012). Learning Valuation Functions. Proceedings of the 25th Annual Conference on Learning Theory, in Proceedings of Machine Learning Research 23:4.1-4.24 Available from https://proceedings.mlr.press/v23/balcan12b.html.

Related Material