{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:31:31Z","timestamp":1750221091048,"version":"3.41.0"},"reference-count":11,"publisher":"Association for Computing Machinery (ACM)","issue":"3-4","license":[{"start":{"date-parts":[[2018,10,23]],"date-time":"2018-10-23T00:00:00Z","timestamp":1540252800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Israeli Ministry of Science"},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1101215, CCF-1116892, CCF-1331175, and IIS-1065251","CCF-1116892, CCF-1331175, CCF-1415460"],"award-info":[{"award-number":["CCF-1101215, CCF-1116892, CCF-1331175, and IIS-1065251","CCF-1116892, CCF-1331175, CCF-1415460"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Simons Award for Graduate Students in Theoretical Computer Science"},{"DOI":"10.13039\/501100005386","name":"Israeli Centers of Research Excellence (I-CORE) program","doi-asserted-by":"crossref","award":["Center No. 4\/11"],"award-info":[{"award-number":["Center No. 4\/11"]}],"id":[{"id":"10.13039\/501100005386","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001742","name":"United States-Israel Binational Science Foundation","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100001742","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Econ. Comput."],"published-print":{"date-parts":[[2018,11,30]]},"abstract":"<jats:p>\n            We consider a setting where\n            <jats:italic>n<\/jats:italic>\n            buyers, with combinatorial preferences over\n            <jats:italic>m<\/jats:italic>\n            items, and a seller, running a priority-based allocation mechanism, repeatedly interact. Our goal, from observing limited information about the results of these interactions, is to reconstruct both the preferences of the buyers and the mechanism of the seller. More specifically, we consider an online setting where at each stage, a subset of the buyers arrive and are allocated items, according to some unknown priority that the seller has among the buyers. Our learning algorithm observes only which buyers arrive and the allocation produced (or some function of the allocation, such as just which buyers received positive utility and which did not), and its goal is to predict the outcome for future subsets of buyers. For this task, the learning algorithm needs to reconstruct both the priority among the buyers and the preferences of each buyer. We derive mistake bound algorithms for additive, unit-demand and single-minded buyers. We also consider the case where buyers\u2019 utilities for a fixed bundle can change between stages due to different (observed) prices. Our algorithms are efficient both in computation time and in the maximum number of mistakes (both polynomial in the number of buyers and items).\n          <\/jats:p>","DOI":"10.1145\/3274642","type":"journal-article","created":{"date-parts":[[2018,10,23]],"date-time":"2018-10-23T12:16:16Z","timestamp":1540296976000},"page":"1-20","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Learning What\u2019s Going on"],"prefix":"10.1145","volume":"6","author":[{"given":"Avrim","family":"Blum","sequence":"first","affiliation":[{"name":"Toyota Technological Institute at Chicago, USA"}]},{"given":"Yishay","family":"Mansour","sequence":"additional","affiliation":[{"name":"Tel Aviv University"}]},{"given":"Jamie","family":"Morgenstern","sequence":"additional","affiliation":[{"name":"Georgia Institute of Technology"}]}],"member":"320","published-online":{"date-parts":[[2018,10,23]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Online learning and profit maximization from revealed preferences. arXiv","author":"Amin Kareem","year":"2014","unstructured":"Kareem Amin , Rachel Cummings , Lili Dworkin , Michael Kearns , and Aaron Roth . 2014. Online learning and profit maximization from revealed preferences. arXiv ( 2014 ). Kareem Amin, Rachel Cummings, Lili Dworkin, Michael Kearns, and Aaron Roth. 2014. Online learning and profit maximization from revealed preferences. arXiv (2014)."},{"key":"e_1_2_1_2_1","volume-title":"Vazirani","author":"Balcan Maria-Florina","year":"2014","unstructured":"Maria-Florina Balcan , Amit Daniely , Ruta Mehta , Ruth Urner , and Vijay V . Vazirani . 2014 . Learning economic parameters from revealed preferences. arXiv abs\/1407.7937 (2014). Maria-Florina Balcan, Amit Daniely, Ruta Mehta, Ruth Urner, and Vijay V. Vazirani. 2014. Learning economic parameters from revealed preferences. arXiv abs\/1407.7937 (2014)."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1134707.1134712"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022696716689"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00385809"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/174644.174647"},{"key":"e_1_2_1_7_1","unstructured":"Wolfgang Maass and Gy\u00f6rgy Tur\u00e1n. 1990. How Fast Can a Threshold Gate Learn? International Computer Science Institute.  Wolfgang Maass and Gy\u00f6rgy Tur\u00e1n. 1990. How Fast Can a Threshold Gate Learn? International Computer Science Institute."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1019126406181"},{"key":"e_1_2_1_9_1","volume-title":"A note on the pure theory of consumer\u2019s behaviour. Economica","author":"Samuelson Paul A.","year":"1938","unstructured":"Paul A. Samuelson . 1938. A note on the pure theory of consumer\u2019s behaviour. Economica ( 1938 ), 61--71. Paul A. Samuelson. 1938. A note on the pure theory of consumer\u2019s behaviour. Economica (1938), 61--71."},{"key":"e_1_2_1_10_1","volume-title":"Revealed preference. Samuelsonian Economics and the Twenty-first Century","author":"Varian Hal R.","year":"2006","unstructured":"Hal R. Varian . 2006. Revealed preference. Samuelsonian Economics and the Twenty-first Century ( 2006 ), 99--115. Hal R. Varian. 2006. Revealed preference. Samuelsonian Economics and the Twenty-first Century (2006), 99--115."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-35311-6_9"}],"container-title":["ACM Transactions on Economics and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3274642","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3274642","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3274642","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T00:57:55Z","timestamp":1750208275000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3274642"}},"subtitle":["Reconstructing Preferences and Priorities from Opaque Transactions"],"short-title":[],"issued":{"date-parts":[[2018,10,23]]},"references-count":11,"journal-issue":{"issue":"3-4","published-print":{"date-parts":[[2018,11,30]]}},"alternative-id":["10.1145\/3274642"],"URL":"https:\/\/doi.org\/10.1145\/3274642","relation":{},"ISSN":["2167-8375","2167-8383"],"issn-type":[{"type":"print","value":"2167-8375"},{"type":"electronic","value":"2167-8383"}],"subject":[],"published":{"date-parts":[[2018,10,23]]},"assertion":[{"value":"2016-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-10-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}