{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:48:25Z","timestamp":1750308505217,"version":"3.41.0"},"reference-count":21,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2022,6,30]],"date-time":"2022-06-30T00:00:00Z","timestamp":1656547200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Econ. Comput."],"published-print":{"date-parts":[[2022,6,30]]},"abstract":"<jats:p>This article addresses the computational challenges of learning strong substitutes demand when given access to a demand (or valuation) oracle. Strong substitutes demand generalises the well-studied gross substitutes demand to a multi-unit setting. Recent work by Baldwin and Klemperer shows that any such demand can be expressed in a natural way as a finite list of weighted bid vectors. A simplified version of this bidding language has been used by the Bank of England.<\/jats:p>\n          <jats:p>Assuming access to a demand oracle, we provide an algorithm that computes the unique list of weighted bid vectors corresponding to a bidder\u2019s demand preferences. In the special case where their demand can be expressed using positive bids only, we have an efficient algorithm that learns this list in linear time. We also show super-polynomial lower bounds on the query complexity of computing the list of bids in the general case where bids may be positive and negative. Our algorithms constitute the first systematic approach for bidders to construct a bid list corresponding to non-trivial demand, allowing them to participate in \u201cproduct-mix\u201d auctions.<\/jats:p>","DOI":"10.1145\/3546604","type":"journal-article","created":{"date-parts":[[2022,8,4]],"date-time":"2022-08-04T11:58:50Z","timestamp":1659614330000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Learning Strong Substitutes Demand via Queries"],"prefix":"10.1145","volume":"10","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0604-2602","authenticated-orcid":false,"given":"Edwin","family":"Lock","sequence":"first","affiliation":[{"name":"University of Oxford, Oxford, UK"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5436-7890","authenticated-orcid":false,"given":"Paul W.","family":"Goldberg","sequence":"additional","affiliation":[{"name":"University of Oxford, Oxford, UK"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3219-7963","authenticated-orcid":false,"given":"Francisco","family":"Marmolejo-Coss\u00edo","sequence":"additional","affiliation":[{"name":"Harvard University, Cambridge, US"}]}],"member":"320","published-online":{"date-parts":[[2022,10,7]]},"reference":[{"key":"e_1_3_2_2_2","unstructured":"Elizabeth Baldwin Paul W. Goldberg Paul Klemperer and Edwin Lock. 2019. Solving strong-substitutes product-mix auctions.  arXiv:1909.07313. Retrieved from http:\/\/arxiv.org\/abs\/1909.07313."},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.3982\/ECTA13693"},{"key":"e_1_3_2_4_2","unstructured":"Elizabeth Baldwin and Paul Klemperer. 2021. Proof that the Product-Mix Bidding Language can represent any Substitutes Preferences Nuffield Discussion Papers (working paper). https:\/\/www.nuffield.ox.ac.uk\/economics\/Papers\/2021\/2021-W05_subsproof.pdf."},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.5555\/1005332.1005356"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/501158.501191"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-36378-5_3"},{"key":"e_1_3_2_8_2","first-page":"367","volume-title":"Proceedings of the 18th National Conference on Artificial Intelligence and 14th Conference on Innovative Applications of Artificial Intelligence","author":"Conen Wolfram","year":"2002","unstructured":"Wolfram Conen and Tuomas Sandholm. 2002. Partial-revelation VCG mechanism for combinatorial auctions. In Proceedings of the 18th National Conference on Artificial Intelligence and 14th Conference on Innovative Applications of Artificial Intelligence, Rina Dechter, Michael J. Kearns, and Richard S. Sutton (Eds.). AAAI Press\/The MIT Press, 367\u2013372."},{"key":"e_1_3_2_9_2","first-page":"1164","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA\u201905)","volume":"5","author":"Guruswami Venkatesan","year":"2005","unstructured":"Venkatesan Guruswami, Jason D. Hartline, Anna R. Karlin, David Kempe, Claire Kenyon, and Frank McSherry. 2005. On profit-maximizing envy-free pricing. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA\u201905), Vol. 5. 1164\u20131173."},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.5555\/1018409.1018771"},{"key":"e_1_3_2_11_2","doi-asserted-by":"crossref","unstructured":"Paul Klemperer. 2008. A New Auction for Substitutes: Central Bank Liquidity Auctions the U.S. TARP and Variable Product-Mix Auctions. Retrieved from https:\/\/www.nuffield.ox.ac.uk\/economics\/Papers\/2008\/substsauc.pdf. working paper Nuffield College.","DOI":"10.2139\/ssrn.1439043"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1111\/j.1542-4774.2010.tb00523.x"},{"key":"e_1_3_2_13_2","unstructured":"Paul Klemperer. 2018. Product-Mix Auctions. (2018). https:\/\/www.nuffield.ox.ac.uk\/economics\/Papers\/2018\/2018W07productmix.pdf."},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/988772.988800"},{"key":"e_1_3_2_15_2","volume-title":"Discrete Convex Analysis","author":"Murota Kazuo","year":"2013","unstructured":"Kazuo Murota. 2013. Discrete Convex Analysis. Society for Industrial and Applied Mathematics."},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/352871.352872"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jet.2004.10.007"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(03)00255-5"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.15807\/jorsj.58.61"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-004-0522-y"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.5555\/3524938.3525964"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/779928.779949"}],"container-title":["ACM Transactions on Economics and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3546604","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3546604","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T18:44:02Z","timestamp":1750272242000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3546604"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,30]]},"references-count":21,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,6,30]]}},"alternative-id":["10.1145\/3546604"],"URL":"https:\/\/doi.org\/10.1145\/3546604","relation":{},"ISSN":["2167-8375","2167-8383"],"issn-type":[{"type":"print","value":"2167-8375"},{"type":"electronic","value":"2167-8383"}],"subject":[],"published":{"date-parts":[[2022,6,30]]},"assertion":[{"value":"2021-01-29","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-06-30","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-10-07","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}