{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:28:55Z","timestamp":1787340535177,"version":"build-2736575974"},"reference-count":23,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2013,1]]},"abstract":"<jats:p>In many settings the power of truthful mechanisms is severely bounded. In this paper we use randomization to overcome this problem in the multi-unit auction setting. In particular, we construct a fully polynomial-time approximation scheme (FPTAS) for multi-unit auctions that is truthful in expectation, whereas there is evidence that no polynomial-time truthful deterministic mechanism provides an approximation ratio better than 2. We leverage the FPTAS to show for the first time that truthful in expectation polynomial-time mechanisms are provably stronger than polynomial-time universally truthful mechanisms. Specifically, we show that there is a setting, related to multi-unit auctions, in which (1) there is a nonpolynomial time truthful mechanism that always outputs the optimal solution, and that (2) no universally truthful randomized mechanism can provide an approximation ratio better than 2 in polynomial time, but (3) an FPTAS that is truthful in expectation exists.<\/jats:p>","DOI":"10.1137\/090780146","type":"journal-article","created":{"date-parts":[[2013,12,17]],"date-time":"2013-12-17T11:45:59Z","timestamp":1387280759000},"page":"2287-2304","source":"Crossref","is-referenced-by-count":25,"title":["On the Power of Randomization in Algorithmic Mechanism Design"],"prefix":"10.1137","volume":"42","author":[{"given":"Shahar","family":"Dobzinski","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shaddin","family":"Dughmi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2013,12,17]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2004.10129086"},{"key":"atypb2","doi-asserted-by":"crossref","unstructured":"A. Archer and \u00c9. Tardos,\n                      Truthful mechanisms for one-parameter agents\n                      , in Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science, 2001, pp. 482-491.","DOI":"10.1109\/SFCS.2001.959924"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1145\/1386790.1386802"},{"key":"atypb4","doi-asserted-by":"crossref","unstructured":"P. Briest, P. Krysta, and B. V\u00f6cking,\n                      Approximation techniques for utilitarian mechanism design\n                      , in Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005, pp. 39-48.","DOI":"10.1145\/1060590.1060597"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973075.45"},{"key":"atypb6","doi-asserted-by":"crossref","unstructured":"P. Dhangwatnotai, S. Dobzinski, S. Dughmi, and T. Roughgarden,\n                      Truthful approximation schemes for single-parameter agents\n                      , in Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008, pp. 15-24.","DOI":"10.1109\/FOCS.2008.71"},{"key":"atypb7","doi-asserted-by":"crossref","unstructured":"S. Dobzinski,\n                      Two randomized mechanisms for combinatorial auctions\n                      , in Proceedings of the 10th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, 2007, pp. 89-103.","DOI":"10.1007\/978-3-540-74208-1_7"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-011-2528-4"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1145\/1250910.1250960"},{"key":"atypb10","doi-asserted-by":"crossref","unstructured":"S. Dobzinski, N. Nisan, and M. Schapira,\n                      Truthful randomized mechanisms for combinatorial auctions\n                      , in Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006, pp. 644-652.","DOI":"10.1145\/1132516.1132607"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1145\/1386790.1386798"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1137\/070680977"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1016\/j.dss.2004.08.009"},{"key":"atypb14","doi-asserted-by":"crossref","unstructured":"R. Lavi, A. Mu'alem, and N. Nisan,\n                      Towards a characterization of truthful combinatorial auctions\n                      , in Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, 2003, pp. 574-583.","DOI":"10.1109\/SFCS.2003.1238230"},{"key":"atypb15","doi-asserted-by":"crossref","unstructured":"R. Lavi and C. Swamy,\n                      Truthful and near-optimal mechanism design via linear programming\n                      , in Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, 2005, pp. 595-604.","DOI":"10.1109\/SFCS.2005.76"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1145\/988772.988791"},{"key":"atypb17","unstructured":"A. Mu'alem and N. Nisan,\n                      Truthful approximation mechanisms for restricted combinatorial auctions\n                      , in Proceedings of the 18th National Conference on Artificial Intelligence, 2002."},{"key":"atypb18","first-page":"209","author":"Nisan N.","year":"2007","journal-title":"UK"},{"key":"atypb19","doi-asserted-by":"crossref","unstructured":"N. Nisan and A. Ronen,\n                      Algorithmic Mechanism Design (extended abstract)\n                      , in Proceedings of the 31st Annual ACM Symposium on Theory of Computing, 1999, pp. 129-140.","DOI":"10.1145\/301250.301287"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1016\/j.jet.2004.10.007"},{"key":"atypb21","doi-asserted-by":"crossref","unstructured":"C. H. Papadimitriou, M. Schapira, and Y. Singer,\n                      On the hardness of being truthful\n                      , in Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008, pp. 250-259.","DOI":"10.1109\/FOCS.2008.54"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1111\/j.1540-6261.1961.tb02789.x"},{"key":"atypb23","doi-asserted-by":"crossref","unstructured":"J. Vondr\u00e1k,\n                      Optimal approximation for the submodular welfare problem in the value oracle model\n                      , in Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008, pp. 67-74.","DOI":"10.1145\/1374376.1374389"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/090780146","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:38:26Z","timestamp":1787337506000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/090780146"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,1]]},"references-count":23,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2013,1]]}},"alternative-id":["10.1137\/090780146"],"URL":"https:\/\/doi.org\/10.1137\/090780146","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,1]]}}}