{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:34:29Z","timestamp":1787340869883,"version":"build-2736575974"},"reference-count":31,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>Algorithmic mechanism design (AMD) studies the delicate interplay between computational efficiency, truthfulness, and optimality. We focus on AMD's paradigmatic problem: combinatorial auctions. We present a new generalization of the Vapnik--Chervonenkis (VC) dimension to multivalued collections of functions, which encompasses the classical VC dimension, Natarajan dimension, and Steele dimension. We present a corresponding generalization of the Sauer--Shelah lemma and harness this VC machinery to establish inapproximability results for deterministic truthful mechanisms. Our results essentially unify all inapproximability results for deterministic truthful mechanisms for combinatorial auctions to date and establish new separation gaps between truthful and nontruthful algorithms.<\/jats:p>","DOI":"10.1137\/15m1045971","type":"journal-article","created":{"date-parts":[[2018,1,11]],"date-time":"2018-01-11T13:28:21Z","timestamp":1515677301000},"page":"96-120","source":"Crossref","is-referenced-by-count":2,"title":["Inapproximability of Truthful Mechanisms via Generalizations of the Vapnik--Chervonenkis Dimension"],"prefix":"10.1137","volume":"47","author":[{"given":"Amit","family":"Daniely","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michael","family":"Schapira","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gal","family":"Shahaf","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2018,1,11]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1145\/263867.263927"},{"key":"atypb2","first-page":"250","author":"Bansal N.","year":"2010","journal-title":"Berlin"},{"key":"atypb3","first-page":"72","author":"Bartal Y.","year":"2003","journal-title":"New York"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1008"},{"key":"atypb5","doi-asserted-by":"crossref","unstructured":"D. Buchfuhrer, S. Dughmi, H. Fu, R. Kleinberg, E. Mossel, C. Papadimitriou, M. Schapira, Y. Singer, and C. Umans,\n                      Inapproximability for VCG-based combinatorial auctions\n                      , in Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 2010} , pp. 518-536.","DOI":"10.1137\/1.9781611973075.45"},{"key":"atypb6","doi-asserted-by":"crossref","unstructured":"D. Buchfuhrer, M. Schapira, and Y. Singer,\n                      Computation and incentives in combinatorial public projects\n                      , in Proceedings of the 11th ACM Conference on Electronic Commerce, ACM, New York, 2010} , pp. 33-42.","DOI":"10.1145\/1807342.1807348"},{"key":"atypb7","unstructured":"D. Buchfuhrer and C. Umans,\n                      Limits on the social welfare of maximal-in-range auction mechanisms\n                      , in Electronic Colloquium on Computational Complexity (ECCC), Technical report, TR09-068, 2009."},{"key":"atypb8","first-page":"1","author":"Chen W.","year":"2013","journal-title":"GA"},{"key":"atypb9","first-page":"287","author":"Daniely A.","year":"2014","journal-title":"Proceedings of Machine Learning Rrsearch"},{"key":"atypb10","first-page":"207","volume":"19","author":"Daniely A.","year":"2011","journal-title":"JMLR Workshop Conf. Proc."},{"key":"atypb11","first-page":"139","author":"Dobzinski S.","year":"2011","journal-title":"New York"},{"key":"atypb12","doi-asserted-by":"crossref","unstructured":"S. Dobzinski and S. Dughmi,\n                      On the power of randomization in algorithmic mechanism design\n                      , in 50th Annual IEEE Symposium on Foundations of Computer Science, 2009. FOCS'09, IEEE, IEEE Computer Society, Los Alamitos, CA, 2009, pp. 505-514.","DOI":"10.1109\/FOCS.2009.42"},{"key":"atypb13","first-page":"338","author":"Dobzinski S.","year":"2007","journal-title":"New York"},{"key":"atypb14","unstructured":"S. Dobzinski and M. Schapira,\n                      Optimal Upper and Lower Approximation Bounds for k-Duplicates Combinatorial Auctions\n                      , Technical report, Hebrew University of Jerusalem, Jerusalem, 2005."},{"key":"atypb15","first-page":"405","author":"Dobzinski S.","year":"2012","journal-title":"New York"},{"key":"atypb16","first-page":"610","author":"Dobzinski S.","year":"2005","journal-title":"New York"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2011.02.010"},{"key":"atypb18","unstructured":"S. Dughmi, H. Fu, and R. Kleinberg,\n                      Amplified Hardness of Approximation for VCG-Based Mechanisms\n                      , preprint, arXiv:0907.1948, 2009."},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(95)90001-2"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1016\/S0899-8256(03)00184-2"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1145\/585265.585266"},{"key":"atypb22","unstructured":"E. Mossel, C. Papadimitriou, M. Schapira, and Y. Singer,\n                      VC v. VCG: Inapproximability of Combinatorial Auctions Via Generalizations of the VC Dimension\n                      , preprint, arXiv:0905.1995, 2009."},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022605311895"},{"key":"atypb24","first-page":"868","author":"Nisan N.","year":"2002","journal-title":"Berlin"},{"key":"atypb25","doi-asserted-by":"crossref","unstructured":"N. Nisan,\n                      Algorithmic Game Theory\n                      , Cambridge University Press, Cambridge, 2007.","DOI":"10.1017\/CBO9780511800481"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1016\/j.jet.2004.10.007"},{"key":"atypb27","first-page":"250","author":"Papadimitriou C.","year":"2008","journal-title":"NJ, IEEE"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(72)90019-2"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1972.41.247"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(78)90046-8"},{"key":"atypb31","doi-asserted-by":"crossref","unstructured":"V. N. Vapnik,\n                      The Nature of Statistical Learning Theory\n                      , Springer, New York, 1995.","DOI":"10.1007\/978-1-4757-2440-0"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/15M1045971","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:53:39Z","timestamp":1787338419000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/15M1045971"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":31,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1137\/15M1045971"],"URL":"https:\/\/doi.org\/10.1137\/15m1045971","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}