{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T09:40:45Z","timestamp":1763458845496,"version":"3.45.0"},"reference-count":51,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2017,9,21]],"date-time":"2017-09-21T00:00:00Z","timestamp":1505952000000},"content-version":"vor","delay-in-days":365,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CCF-0448664"],"award-info":[{"award-number":["CCF-0448664"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Siebel Foundation Scholarship"},{"name":"Stanford Graduate Fellowship"},{"name":"NSF CAREER"},{"name":"AFOSR MURI grant"},{"name":"Alfred P. Sloan Fellowship"},{"name":"ONR Young Investigator Award"},{"name":"ONR PECASE Award"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2016,11,8]]},"abstract":"<jats:p>\n                    We design the first truthful-in-expectation, constant-factor approximation mechanisms for\n                    <jats:italic toggle=\"yes\">NP<\/jats:italic>\n                    -hard cases of the welfare maximization problem in combinatorial auctions with nonidentical items and in combinatorial public projects. Our results apply to bidders with valuations that are nonnegative linear combinations of gross-substitute valuations, a class that encompasses many of the most well-studied subclasses of submodular functions, including coverage functions and weighted matroid rank functions. Our mechanisms have an expected polynomial runtime and achieve an approximation factor of 1 \u2212 1\/\n                    <jats:italic toggle=\"yes\">e<\/jats:italic>\n                    . This approximation factor is the best possible for both problems, even for known and explicitly given coverage valuations, assuming\n                    <jats:italic toggle=\"yes\">P<\/jats:italic>\n                    \u2260\n                    <jats:italic toggle=\"yes\">NP<\/jats:italic>\n                    . Recent impossibility results suggest that our results cannot be extended to a significantly larger valuation class.\n                  <\/jats:p>\n                  <jats:p>\n                    Both of our mechanisms are instantiations of a new framework for designing approximation mechanisms based on randomized rounding algorithms. The high-level idea of this framework is to optimize\n                    <jats:italic toggle=\"yes\">directly over the (random) output of the rounding algorithm<\/jats:italic>\n                    , rather than the usual (and rarely truthful) approach of optimizing over the\n                    <jats:italic toggle=\"yes\">input<\/jats:italic>\n                    to the rounding algorithm. This framework yields truthful-in-expectation mechanisms, which can be implemented efficiently when the corresponding objective function is concave. For bidders with valuations in the cone generated by gross-substitute valuations, we give novel randomized rounding algorithms that lead to both a concave objective function and a (1 \u2212 1\/\n                    <jats:italic toggle=\"yes\">e<\/jats:italic>\n                    )-approximation of the optimal welfare.\n                  <\/jats:p>","DOI":"10.1145\/2908735","type":"journal-article","created":{"date-parts":[[2016,9,21]],"date-time":"2016-09-21T08:42:46Z","timestamp":1474447366000},"page":"1-33","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["Optimal Mechanisms for Combinatorial Auctions and Combinatorial Public Projects via Convex Rounding"],"prefix":"10.1145","volume":"63","author":[{"given":"Shaddin","family":"Dughmi","sequence":"first","affiliation":[{"name":"University of Southern California"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tim","family":"Roughgarden","sequence":"additional","affiliation":[{"name":"Stanford University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Qiqi","family":"Yan","sequence":"additional","affiliation":[{"name":"Google Research"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2016,9,21]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2229012.2229016"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/2133036.2133093"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","unstructured":"Aharon Ben-Tal and Arkadi Nemirovski. 2001. Lectures on Modern Convex Optimization: Analysis Algorithms and Engineering Applications. SIAM.","DOI":"10.5555\/502969"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/988772.988812"},{"volume-title":"Combinatorial auctions (a survey)","author":"Blumrosen Liad","key":"e_1_2_1_5_1","unstructured":"Liad Blumrosen and Noam Nisan. 2007. Combinatorial auctions (a survey). In Algorithmic Game Theory, Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay Vazirani (Eds.). Cambridge University Press."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/993483"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873646"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807342.1807348"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-72792-7_15"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","unstructured":"Peter Cramton Yoav Shoham and Richard Steinberg (Eds.). 2006. Combinatorial Auctions. MIT Press Cambridge MA.","DOI":"10.5555\/1076465"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-74208-1_7"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993656"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.42"},{"key":"e_1_2_1_14_1","unstructured":"Shahar Dobzinski Hu Fu and Robert Kleinberg. 2010. Truthfulness via proxies. arXiv:1011.3232."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250842"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060681"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132607"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109675"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1386790.1386798"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2229012.2229044"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993574.1993614"},{"key":"e_1_2_1_22_1","volume-title":"Mechanisms for risk averse agents, without loss. CoRR abs\/1206.2957","author":"Dughmi Shaddin","year":"2012","unstructured":"Shaddin Dughmi and Yuval Peres. 2012. Mechanisms for risk averse agents, without loss. CoRR abs\/1206.2957 (2012). http:\/\/arxiv.org\/abs\/1206.2957"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.79"},{"key":"e_1_2_1_24_1","unstructured":"Shaddin Dughmi Tim Roughgarden Jan Vondr\u00e1k and Qiqi Yan. 2011b. An approximately truthful-in-expectation mechanism for combinatorial auctions using value queries. CoRR abs\/1109.1053."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993657"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.64"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132523"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2422436.2422466"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2007.40"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.14"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1006\/jeth.1999.2531"},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the 22nd ACM Symposium on Discrete Algorithms (SODA\u201911)","author":"Hartline Jason","year":"2011","unstructured":"Jason Hartline, Robert Kleinberg, and Azarakhsh Malekian. 2011. Multi-parameter Bayesian algorithmic mechanism design. In Proceedings of the 22nd ACM Symposium on Discrete Algorithms (SODA\u201911). 734--747."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806732"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2229012.2229062"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.2307\/1913392"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.5555\/3118759.3119047"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.76"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2005.02.006"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/585265.585266"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1386790.1386805"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480195280009"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01588971"},{"volume-title":"Introduction to mechanism design (for computer scientists)","author":"Nisan Noam","key":"e_1_2_1_43_1","unstructured":"Noam Nisan. 2007. Introduction to mechanism design (for computer scientists). In Algorithmic Game Theory, Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay Vazirani (Eds.). Cambridge University Press, New York, NY."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1006\/game.1999.0790"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.5555\/1296179"},{"volume-title":"Matroid Theory","author":"Oxley J. G.","key":"e_1_2_1_46_1","unstructured":"J. G. Oxley. 1992. Matroid Theory. Oxford University Press, New York, NY."},{"volume-title":"Gross substitutability: an algorithmic survey. Technical paper. Microsoft Research","author":"Leme R. Paes","key":"e_1_2_1_47_1","unstructured":"R. Paes Leme. 2013. Gross substitutability: an algorithmic survey. Technical paper. Microsoft Research, Redmond, WA."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.54"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258641"},{"volume-title":"Combinatorial Optimization","author":"Schrijver Alexander","key":"e_1_2_1_50_1","unstructured":"Alexander Schrijver. 2003. Combinatorial Optimization. Springer, New York, NY."},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374389"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2908735","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2908735","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2908735","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T09:36:43Z","timestamp":1763458603000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2908735"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,9,21]]},"references-count":51,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2016,11,8]]}},"alternative-id":["10.1145\/2908735"],"URL":"https:\/\/doi.org\/10.1145\/2908735","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2016,9,21]]},"assertion":[{"value":"2014-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-03-01","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-09-21","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}