{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,6]],"date-time":"2026-06-06T07:54:02Z","timestamp":1780732442596,"version":"3.54.1"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2021,1,6]],"date-time":"2021-01-06T00:00:00Z","timestamp":1609891200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CCF-1350900"],"award-info":[{"award-number":["CCF-1350900"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2021,4,30]]},"abstract":"<jats:p>\n            We provide a polynomial time reduction from Bayesian incentive compatible mechanism design to Bayesian algorithm design for welfare maximization problems. Unlike prior results, our reduction achieves exact incentive compatibility for problems with multi-dimensional and continuous type spaces. The key technical barrier preventing exact incentive compatibility in prior black-box reductions is that repairing violations of incentive constraints requires understanding the distribution of the mechanism\u2019s output, which is typically #P-hard to compute. Reductions that instead estimate the output distribution by sampling inevitably suffer from sampling error, which typically precludes exact incentive compatibility. We overcome this barrier by employing and generalizing the computational model in the literature on\n            <jats:italic>Bernoulli Factories<\/jats:italic>\n            . In a Bernoulli factory problem, one is given a function mapping the bias of an \u201cinput coin\u201d to that of an \u201coutput coin,\u201d and the challenge is to efficiently simulate the output coin given only sample access to the input coin. This is the key ingredient in designing an incentive compatible mechanism for bipartite matching, which can be used to make the approximately incentive compatible reduction of Hartline et\u00a0al. [18] exactly incentive compatible.\n          <\/jats:p>","DOI":"10.1145\/3440988","type":"journal-article","created":{"date-parts":[[2021,1,6]],"date-time":"2021-01-06T13:25:38Z","timestamp":1609939538000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":11,"title":["Bernoulli Factories and Black-box Reductions in Mechanism Design"],"prefix":"10.1145","volume":"68","author":[{"given":"Shaddin","family":"Dughmi","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Southern California, Los Angeles, CA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jason","family":"Hartline","sequence":"additional","affiliation":[{"name":"Computer Science Department, Northwestern University, IL, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Robert D.","family":"Kleinberg","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Cornell University, NY, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5880-6221","authenticated-orcid":false,"given":"Rad","family":"Niazadeh","sequence":"additional","affiliation":[{"name":"Chicago Booth School of Business, University of Chicago, Chicago, IL, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,1,6]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Devanur","author":"Agrawal Shipra","year":"2015"},{"key":"e_1_2_1_2_1","volume-title":"A dynamic near-optimal algorithm for online linear programming. arXiv preprint arXiv:0911.2974","author":"Agrawal Shipra","year":"2009"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2004.10129086"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the 14th ACM Conference on Electronic Commerce. 35--52","author":"Babaioff Moshe","year":"2013"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2724705"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.30"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973082.57"},{"key":"e_1_2_1_8_1","volume-title":"Convex Optimization","author":"Boyd Stephen"},{"key":"e_1_2_1_9_1","volume-title":"Convex optimization: Algorithms and complexity. arXiv preprint arXiv:1405.4980","author":"Bubeck S\u00e9bastien","year":"2014"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214019"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2015.06.029"},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the 12th ACM Conference on Electronic Commerce. ACM, 29--38","author":"Devanur Nikhil R."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055492"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.2307\/1914085"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 42nd ACM Symposium on Theory of Computing. ACM, 301--310","author":"Jason"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1257\/aer.20130712"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973082.58"},{"key":"e_1_2_1_18_1","volume-title":"C","author":"Hartline Jason D.","year":"2015"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1561\/2400000013"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.36"},{"key":"e_1_2_1_21_1","volume-title":"Optimal linear Bernoulli factories for small mean problems. CoRR abs\/1507.00843","author":"Huber Mark","year":"2015"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.10.016"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/175007.175019"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591810"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the International Workshop for Applied Public Key Infrastructure. 1--5.","author":"\u0141atuszy\u0144ski Krzysztof","year":"2010"},{"key":"e_1_2_1_26_1","first-page":"148","article-title":"On the method of bounded differences","volume":"141","author":"McDiarmid Colin","year":"1989","journal-title":"Surv. Combinat."},{"key":"e_1_2_1_27_1","volume-title":"Randomized Algorithms","author":"Motwani Rajeev"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1214\/105051604000000549"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1006\/game.1999.0790"},{"key":"e_1_2_1_30_1","first-page":"107","article-title":"Online learning and online convex optimization. Found","volume":"4","author":"\u00a0al Shai","year":"2012","journal-title":"Trends\u00ae Mach. Learn."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3440988","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3440988","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3440988","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:02:51Z","timestamp":1750197771000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3440988"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1,6]]},"references-count":30,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,4,30]]}},"alternative-id":["10.1145\/3440988"],"URL":"https:\/\/doi.org\/10.1145\/3440988","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1,6]]},"assertion":[{"value":"2018-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-01-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}