{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:50:29Z","timestamp":1750308629567,"version":"3.41.0"},"reference-count":26,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2012,5,1]],"date-time":"2012-05-01T00:00:00Z","timestamp":1335830400000},"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. Comput. Theory"],"published-print":{"date-parts":[[2012,5]]},"abstract":"<jats:p>\n            A\n            <jats:italic>truthful mechanism<\/jats:italic>\n            consists of an algorithm augmented with a suitable payment function that guarantees that the players cannot improve their utilities by cheating. Mechanism design approaches are particularly appealing for designing protocols that cannot be manipulated by rational players.\n          <\/jats:p>\n          <jats:p>We present new constructions of so-called mechanisms with verification introduced by Nisan and Ronen [2001]. We first show how to obtain mechanisms that, for single-parameter domains, are resistant to coalitions of colluding agents even if they can exchange compensations. Based on this result we derive a class of exact truthful mechanisms with verification for arbitrary bounded domains. This class of problems includes most of the problems studied in the algorithmic mechanism design literature and for which exact solutions cannot be obtained with truthful mechanisms without verification. This result is an improvement over all known previous constructions of exact mechanisms with verification.<\/jats:p>","DOI":"10.1145\/2189778.2189781","type":"journal-article","created":{"date-parts":[[2012,6,12]],"date-time":"2012-06-12T13:13:25Z","timestamp":1339506805000},"page":"1-17","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Collusion-Resistant Mechanisms with Verification Yielding Optimal Solutions"],"prefix":"10.1145","volume":"4","author":[{"given":"Paolo","family":"Penna","sequence":"first","affiliation":[{"name":"Universit\u00e0 di Salerno"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Carmine","family":"Ventre","sequence":"additional","affiliation":[{"name":"Teesside University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2012,5]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-31856-9_6"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/874063.875583"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/11786986_52"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2008.10.001"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060597"},{"volume-title":"Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithm (SODA). 1163--1170","author":"Christodoulou G.","key":"e_1_2_1_6_1","unstructured":"Christodoulou , G. , Koutsoupias , E. , and Vidali , A . 2007. A lower bound for scheduling mechanisms . In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithm (SODA). 1163--1170 . Christodoulou, G., Koutsoupias, E., and Vidali, A. 2007. A lower bound for scheduling mechanisms. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithm (SODA). 1163--1170."},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","unstructured":"Clarke E. H. 1971. Multipart pricing of public goods. Public Choice 17--33. Clarke E. H. 1971. Multipart pricing of public goods. Public Choice 17--33.","DOI":"10.1007\/BF01726210"},{"volume-title":"Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 701--709","author":"Elkind E.","key":"e_1_2_1_8_1","unstructured":"Elkind , E. , Sahai , A. , and Steiglitz , K . 2004. Frugality in path auctions . In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 701--709 . Elkind, E., Sahai, A., and Steiglitz, K. 2004. Frugality in path auctions. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 701--709."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/1787680.1787682"},{"volume-title":"Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 620--629","author":"Goldberg A. V.","key":"e_1_2_1_10_1","unstructured":"Goldberg , A. V. and Hartline , J. D . 2005. Collusion-resistant mechanisms for single-parameter agents . In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 620--629 . Goldberg, A. V. and Hartline, J. D. 2005. Collusion-resistant mechanisms for single-parameter agents. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 620--629."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.2307\/1914085"},{"volume-title":"Proceedings of the Annual Symposium on Theoretical Aspects of Computer Science (STACS). 404--413","author":"Koutsoupias E.","key":"e_1_2_1_12_1","unstructured":"Koutsoupias , E. and Papadimitriou , C. H . 1999. Worst-case equilibria . In Proceedings of the Annual Symposium on Theoretical Aspects of Computer Science (STACS). 404--413 . Koutsoupias, E. and Papadimitriou, C. H. 1999. Worst-case equilibria. In Proceedings of the Annual Symposium on Theoretical Aspects of Computer Science (STACS). 404--413."},{"volume-title":"Proceedings of the Symposium on Mathematical Foundations of Computer Science (MFCS). 454--464","author":"Koutsoupias E.","key":"e_1_2_1_13_1","unstructured":"Koutsoupias , E. and Vidali , A . 2007. A lower bound of 1&thinsp;+&thinsp;\u03c6 for truthful scheduling mechanisms . In Proceedings of the Symposium on Mathematical Foundations of Computer Science (MFCS). 454--464 . Koutsoupias, E. and Vidali, A. 2007. A lower bound of 1&thinsp;+&thinsp;\u03c6 for truthful scheduling mechanisms. In Proceedings of the Symposium on Mathematical Foundations of Computer Science (MFCS). 454--464."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250910.1250947"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374388"},{"volume-title":"Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 1143--1152","author":"Mu\u2019alem A.","key":"e_1_2_1_16_1","unstructured":"Mu\u2019alem , A. and Schapira , M . 2007. Setting lower bounds on truthfulness . In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 1143--1152 . Mu\u2019alem, A. and Schapira, M. 2007. Setting lower bounds on truthfulness. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 1143--1152."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1006\/game.1999.0790"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/1622606.1622608"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jet.2004.10.007"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380883"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1566374.1566396"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1073970.1073999"},{"volume-title":"J.-J","author":"Roberts K.","key":"e_1_2_1_23_1","unstructured":"Roberts , K. 1979. The characterization of implementable choice rules. Aggregation and Revelation of Preferences , J.-J . Laffont Ed., North-Holland , 321--348. Roberts, K. 1979. The characterization of implementable choice rules. Aggregation and Revelation of Preferences, J.-J. Laffont Ed., North-Holland, 321--348."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1006\/jeth.1999.2618"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/11944874_5"},{"key":"e_1_2_1_26_1","doi-asserted-by":"crossref","unstructured":"Vickrey W. 1961. Counterspeculation auctions and competitive sealed tenders. J. Finance 8--37. Vickrey W. 1961. Counterspeculation auctions and competitive sealed tenders. J. Finance 8--37.","DOI":"10.1111\/j.1540-6261.1961.tb02789.x"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2189778.2189781","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2189778.2189781","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T19:07:54Z","timestamp":1750273674000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2189778.2189781"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,5]]},"references-count":26,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2012,5]]}},"alternative-id":["10.1145\/2189778.2189781"],"URL":"https:\/\/doi.org\/10.1145\/2189778.2189781","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2012,5]]},"assertion":[{"value":"2011-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-05-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}