{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:23:38Z","timestamp":1750220618418,"version":"3.41.0"},"reference-count":15,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2020,10,16]],"date-time":"2020-10-16T00:00:00Z","timestamp":1602806400000},"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":[[2020,11,30]]},"abstract":"<jats:p>We study black-box reductions from mechanism design to algorithm design for welfare maximization in settings of incomplete information. Given oracle access to an algorithm for an underlying optimization problem, the goal is to simulate an incentive compatible mechanism. The mechanism will be evaluated on its expected welfare, relative to the algorithm provided, and its complexity is measured by the time (and queries) needed to simulate the mechanism on any input. While it is known that black-box reductions are not possible in many prior-free settings, settings with priors appear more promising: there are known reductions for Bayesian incentive compatible (BIC) mechanism design for general classes of welfare maximization problems. This dichotomy begs the question: which mechanism design problems admit black-box reductions, and which do not?<\/jats:p>\n          <jats:p>\n            Our main result is that black-box mechanism design is impossible under two of the simplest settings not captured by known positive results. First, for the problem of allocating\n            <jats:italic>n<\/jats:italic>\n            goods to a single buyer whose valuation is additive and independent across the goods, subject to a downward-closed constraint on feasible allocations, we show that there is no polytime (in\n            <jats:italic>n<\/jats:italic>\n            ) BIC black-box reduction for expected welfare maximization. Second, for the setting of multiple single-parameter agents\u2014where polytime BIC reductions are known\u2014we show that no polytime reductions exist when the incentive requirement is tightened to Max-In-Distributional-Range. In each case, we show that achieving a sub-polynomial approximation to the expected welfare requires exponentially many queries, even when the set of feasible allocations is known to be downward-closed.\n          <\/jats:p>","DOI":"10.1145\/3417744","type":"journal-article","created":{"date-parts":[[2020,10,16]],"date-time":"2020-10-16T22:24:56Z","timestamp":1602887096000},"page":"1-19","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["The Complexity of Black-Box Mechanism Design with Priors"],"prefix":"10.1145","volume":"8","author":[{"given":"Evangelia","family":"Gergatsouli","sequence":"first","affiliation":[{"name":"University of Wisconsin-Madison, Madison, WI"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Brendan","family":"Lucier","sequence":"additional","affiliation":[{"name":"Microsoft Researchb, New England, One Memorial Drive, Cambridge, MA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christos","family":"Tzamos","sequence":"additional","affiliation":[{"name":"University of Wisconsin-Madison, Madison, WI, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,10,16]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1462153.1462157"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973082.57"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060597"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.88"},{"volume-title":"Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201913)","author":"Cai Yang","key":"e_1_2_1_5_1","unstructured":"Yang Cai , Constantinos Daskalakis , and S. Matthew Weinberg . 2013. Reducing revenue to welfare maximization: Approximation algorithms and other generalizations . In Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201913) . Society for Industrial and Applied Mathematics, Philadelphia, PA, 578--595. http:\/\/dl.acm.org\/citation.cfm?id=2627817.2627859. Yang Cai, Constantinos Daskalakis, and S. Matthew Weinberg. 2013. Reducing revenue to welfare maximization: Approximation algorithms and other generalizations. In Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201913). Society for Industrial and Applied Mathematics, Philadelphia, PA, 578--595. http:\/\/dl.acm.org\/citation.cfm?id=2627817.2627859."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214019"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/090780146"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055492"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/110843654"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2015.02.002"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1257\/aer.20130712"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.76"},{"volume-title":"On the impossibility of black-box transformations in mechanism design","author":"Pass Rafael","key":"e_1_2_1_13_1","unstructured":"Rafael Pass and Karn Seth . 2014. On the impossibility of black-box transformations in mechanism design . In Algorithmic Game Theory, Ron Lavi (Ed.). Springer , Berlin , 279--290. Rafael Pass and Karn Seth. 2014. On the impossibility of black-box transformations in mechanism design. In Algorithmic Game Theory, Ron Lavi (Ed.). Springer, Berlin, 279--290."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3105448"},{"key":"e_1_2_1_15_1","volume-title":"On black-box transformations in downward-closed environments. Theory of Computing Systems (Nov","author":"Suksompong Warut","year":"2018","unstructured":"Warut Suksompong . 2018. On black-box transformations in downward-closed environments. Theory of Computing Systems (Nov . 2018 ). DOI:https:\/\/doi.org\/10.1007\/s00224-018-9898-6 10.1007\/s00224-018-9898-6 Warut Suksompong. 2018. On black-box transformations in downward-closed environments. Theory of Computing Systems (Nov. 2018). DOI:https:\/\/doi.org\/10.1007\/s00224-018-9898-6"}],"container-title":["ACM Transactions on Economics and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3417744","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3417744","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:01:14Z","timestamp":1750197674000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3417744"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,10,16]]},"references-count":15,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2020,11,30]]}},"alternative-id":["10.1145\/3417744"],"URL":"https:\/\/doi.org\/10.1145\/3417744","relation":{},"ISSN":["2167-8375","2167-8383"],"issn-type":[{"type":"print","value":"2167-8375"},{"type":"electronic","value":"2167-8383"}],"subject":[],"published":{"date-parts":[[2020,10,16]]},"assertion":[{"value":"2019-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-10-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}