{"id":186618,"date":"2011-08-03T00:00:00","date_gmt":"2011-08-04T17:38:58","guid":{"rendered":"https:\/\/www.microsoft.com\/en-us\/research\/msr-research-item\/learning-valuation-functions\/"},"modified":"2016-08-22T11:30:22","modified_gmt":"2016-08-22T18:30:22","slug":"learning-valuation-functions","status":"publish","type":"msr-video","link":"https:\/\/www.microsoft.com\/en-us\/research\/video\/learning-valuation-functions\/","title":{"rendered":"Learning Valuation Functions"},"content":{"rendered":"<div class=\"asset-content\">\n<p>A core element of microeconomics and game theory is that consumers have valuation<br \/>\nfunctions over bundles of goods and that these valuation functions drive their<br \/>\npurchases. In particular, the value given to a bundle need not be the sum of values on<br \/>\nthe individual items but rather can be a more complex function of how the items<br \/>\nrelate. Common valuation classes considered in the literature include OXS,<br \/>\nsubmodular, and XOS valuations. Typically it is assumed that these valuations are<br \/>\nknown to the center or come from a known distribution. In this work we initiate the<br \/>\nstudy of the approximate learnability of valuation classes in a distributional learning<br \/>\nsetting. We prove upper and lower bounds on the approximation guarantees<br \/>\nachievable for learning over general data distributions by using only a polynomial<br \/>\nnumber of examples. Our work combines central issues in economics with central<br \/>\nissues in optimization (submodular functions and matroids) with central issues in<br \/>\nlearning (learnability of natural but complex classes of functions in a distributional<br \/>\nsetting).<\/p>\n<\/div>\n<p><!-- .asset-content --><\/p>\n","protected":false},"excerpt":{"rendered":"<p>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 [&hellip;]<\/p>\n","protected":false},"featured_media":196299,"template":"","meta":{"msr-url-field":"","msr-podcast-episode":"","msrModifiedDate":"","msrModifiedDateEnabled":false,"ep_exclude_from_search":false,"footnotes":""},"research-area":[13561,13556,13548],"msr-video-type":[],"msr-locale":[268875],"msr-impact-theme":[],"msr-pillar":[],"class_list":["post-186618","msr-video","type-msr-video","status-publish","has-post-thumbnail","hentry","msr-research-area-algorithms","msr-research-area-artificial-intelligence","msr-research-area-economics","msr-locale-en_us"],"msr_download_urls":"","msr_external_url":"https:\/\/youtu.be\/1qX_oVfL1b4","msr_secondary_video_url":"","msr_video_file":"","_links":{"self":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-video\/186618"}],"collection":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-video"}],"about":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/types\/msr-video"}],"version-history":[{"count":0,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-video\/186618\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media\/196299"}],"wp:attachment":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media?parent=186618"}],"wp:term":[{"taxonomy":"msr-research-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/research-area?post=186618"},{"taxonomy":"msr-video-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-video-type?post=186618"},{"taxonomy":"msr-locale","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-locale?post=186618"},{"taxonomy":"msr-impact-theme","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-impact-theme?post=186618"},{"taxonomy":"msr-pillar","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-pillar?post=186618"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}