{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T19:53:53Z","timestamp":1760298833542},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2013,11,23]],"date-time":"2013-11-23T00:00:00Z","timestamp":1385164800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2015,5]]},"DOI":"10.1007\/s00453-013-9854-4","type":"journal-article","created":{"date-parts":[[2013,11,22]],"date-time":"2013-11-22T20:28:18Z","timestamp":1385152098000},"page":"167-190","source":"Crossref","is-referenced-by-count":9,"title":["Incentive Compatible Mulit-Unit Combinatorial Auctions: A Primal Dual Approach"],"prefix":"10.1007","volume":"72","author":[{"given":"Niv","family":"Buchbinder","sequence":"first","affiliation":[]},{"given":"Rica","family":"Gonen","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2013,11,23]]},"reference":[{"issue":"2","key":"9854_CR1","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1080\/15427951.2004.10129086","volume":"1","author":"A. Archer","year":"2003","unstructured":"Archer, A., Papadimitriou, C., Talwar, K., Tardos, E.: An approximate truthful mechanism for combinatorial auctions with single parameter agents. Internet Math. 1(2), 129\u2013150 (2003)","journal-title":"Internet Math."},{"key":"9854_CR2","first-page":"503","volume-title":"Proceedings of the 35th ACM Symposium Theory of Computing, STOC","author":"B. Awerbuch","year":"2003","unstructured":"Awerbuch, B., Azar, Y., Meyerson, A.: Reducing truth-telling online mechanisms to online optimization. In: Proceedings of the 35th ACM Symposium Theory of Computing, STOC, pp. 503\u2013510 (2003)"},{"key":"9854_CR3","first-page":"32","volume-title":"Proceedings of the 34rd IEEE Symposium Foundations of Computer Science, FOCS","author":"B. Awerbuch","year":"1993","unstructured":"Awerbuch, B., Azar, Y., Plotkin, S.: Throughput-competitive on-line routing. In: Proceedings of the 34rd IEEE Symposium Foundations of Computer Science, FOCS, pp. 32\u201340 (1993)"},{"issue":"1","key":"9854_CR4","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1007\/s00453-005-1172-z","volume":"44","author":"Y. Azar","year":"2006","unstructured":"Azar, Y., Regev, O.: Combinatorial algorithms for the unsplittable flow problem. Algorithmica 44(1), 49\u201366 (2006)","journal-title":"Algorithmica"},{"key":"9854_CR5","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1462153.1462157","volume":"4","author":"M. Babaioff","year":"2009","unstructured":"Babaioff, M., Lavi, R., Pavlov, E.: Single-value combinatorial auctions and algorithmic implementation in undominated strategies. J. ACM 4, 1 (2009)","journal-title":"J. ACM"},{"key":"9854_CR6","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2339123.2339126","volume":"19","author":"N. Bansal","year":"2012","unstructured":"Bansal, N., Buchbinder, N., Naor, J.: A primal-dual randomized algorithm for weighted paging. J. ACM 19, 1 (2012)","journal-title":"J. ACM"},{"issue":"2","key":"9854_CR7","doi-asserted-by":"crossref","first-page":"391","DOI":"10.1137\/090779000","volume":"41","author":"N. Bansal","year":"2012","unstructured":"Bansal, N., Buchbinder, N., Naor, J.: Randomized competitive algorithms for generalized caching. SIAM J. Comput. 41(2), 391\u2013414 (2012)","journal-title":"SIAM J. Comput."},{"key":"9854_CR8","doi-asserted-by":"crossref","first-page":"72","DOI":"10.1145\/846241.846250","volume-title":"Proceedings of the 9th Conference on Theoretical Aspects of Rationality and Knowledge TARK IX","author":"Y. Bartal","year":"2003","unstructured":"Bartal, Y., Gonen, R., Nisan, N.: Incentive compatible multi-unit combinatorial auctions. In: Proceedings of the 9th Conference on Theoretical Aspects of Rationality and Knowledge TARK IX, pp. 72\u201387 (2003)"},{"issue":"4","key":"9854_CR9","doi-asserted-by":"crossref","first-page":"1109","DOI":"10.1111\/j.1468-0262.2006.00695.x","volume":"74","author":"S. Bikhchandani","year":"2006","unstructured":"Bikhchandani, S., Chatterji, S., Lavi, R., Mu\u2019alem, A., Nisan, N., Sen, A.: Weak monotonicity characterizes deterministic dominant strategy implementation. Econometrica 74(4), 1109\u20131132 (2006)","journal-title":"Econometrica"},{"issue":"6","key":"9854_CR10","doi-asserted-by":"crossref","first-page":"1587","DOI":"10.1137\/090772988","volume":"40","author":"P. Briest","year":"2011","unstructured":"Briest, P., Krysta, P., V\u00f6cking, B.: Approximation techniques for utilitarian mechanism design. SIAM J. Comput. 40(6), 1587\u20131622 (2011)","journal-title":"SIAM J. Comput."},{"key":"9854_CR11","first-page":"253","volume-title":"Proceedings of the 15th Annual European Symposium on Algorithms","author":"N. Buchbinder","year":"2007","unstructured":"Buchbinder, N., Jain, K., Naor, J.S.: Online primal-dual algorithms for maximizing ad-auctions revenue. In: Proceedings of the 15th Annual European Symposium on Algorithms, pp. 253\u2013264 (2007)"},{"key":"9854_CR12","first-page":"293","volume-title":"Proceeding of the 47th Annual IEEE Symposium on Foundations of Computer Science, FOCS","author":"N. Buchbinder","year":"2006","unstructured":"Buchbinder, N., Naor, J.: Improved bounds for online routing and packing via a primal-dual approach. In: Proceeding of the 47th Annual IEEE Symposium on Foundations of Computer Science, FOCS, pp. 293\u2013304 (2006)"},{"issue":"2\u20133","key":"9854_CR13","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1561\/0400000024","volume":"3","author":"N. Buchbinder","year":"2009","unstructured":"Buchbinder, N., Naor, J.: The design of competitive online algorithms via a primal-dual approach. Found. Trends Theor. Comput. Sci. 3(2\u20133), 93\u2013263 (2009)","journal-title":"Found. Trends Theor. Comput. Sci."},{"issue":"2","key":"9854_CR14","doi-asserted-by":"crossref","first-page":"270","DOI":"10.1287\/moor.1080.0363","volume":"34","author":"N. Buchbinder","year":"2009","unstructured":"Buchbinder, N., Naor, J.: Online primal-dual algorithms for covering and packing. Math. Oper. Res. 34(2), 270\u2013286 (2009)","journal-title":"Math. Oper. Res."},{"key":"9854_CR15","doi-asserted-by":"crossref","first-page":"518","DOI":"10.1137\/1.9781611973075.45","volume-title":"Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA","author":"D. Buchfuhrer","year":"2010","unstructured":"Buchfuhrer, D., Dughmi, S., Fu, H., Kleinberg, R., Mossel, E., Papadimitriou, C.H., Schapira, M., Singer, Y., Umans, C.: Inapproximability for vcg-based combinatorial auctions. In: Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 518\u2013536 (2010)"},{"key":"9854_CR16","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1007\/BF01726210","volume":"2","author":"E.H. Clarke","year":"1971","unstructured":"Clarke, E.H.: Multipart pricing of public goods. Public Choice 2, 17\u201333 (1971)","journal-title":"Public Choice"},{"key":"9854_CR17","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1613\/jair.2950","volume":"37","author":"S. Dobzinski","year":"2010","unstructured":"Dobzinski, S., Nisan, N.: Mechanisms for multi-unit auctions. J. Artif. Intell. Res. 37, 85\u201398 (2010)","journal-title":"J. Artif. Intell. Res."},{"key":"9854_CR18","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1145\/1993574.1993611","volume-title":"Proceedings of the 12th ACM Conference on Electronic Commerce, EC","author":"S. Dobzinski","year":"2011","unstructured":"Dobzinski, S., Nisan, N.: Multi-unit auctions: beyond Roberts. In: Proceedings of the 12th ACM Conference on Electronic Commerce, EC, pp. 233\u2013242 (2011)"},{"issue":"1","key":"9854_CR19","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1016\/j.jcss.2011.02.010","volume":"78","author":"S. Dobzinski","year":"2012","unstructured":"Dobzinski, S., Nisan, N., Schapira, M.: Truthful randomized mechanisms for combinatorial auctions. J. Comput. Syst. Sci. 78(1), 15\u201325 (2012)","journal-title":"J. Comput. Syst. Sci."},{"key":"9854_CR20","unstructured":"Dobzinski, S., Schapira, M.: Optimal upper and lower approximation bounds for k-duplicates combinatorial auctions. Manuscript (2005)"},{"key":"9854_CR21","doi-asserted-by":"crossref","first-page":"427","DOI":"10.2307\/1911219","volume":"45","author":"J.R. Green","year":"1977","unstructured":"Green, J.R., Laffont, J.-J.: Characterization of satisfactory mechanisms for the reveraltion of preferences in public goods. Econometrica 45, 427\u2013438 (1977)","journal-title":"Econometrica"},{"key":"9854_CR22","doi-asserted-by":"crossref","first-page":"617","DOI":"10.2307\/1914085","volume":"41","author":"T. Groves","year":"1973","unstructured":"Groves, T.: Incentives in teams. Econometrica 41, 617\u2013631 (1973)","journal-title":"Econometrica"},{"key":"9854_CR23","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1007\/BF02392825","volume":"182","author":"J. Hastad","year":"1999","unstructured":"Hastad, J.: Clique is hard to approximate to within n 1\u2212\u03f5 . Acta Math. 182, 105\u2013142 (1999)","journal-title":"Acta Math."},{"key":"9854_CR24","doi-asserted-by":"crossref","first-page":"104","DOI":"10.1016\/S0899-8256(03)00184-2","volume":"47","author":"R. Holzman","year":"2004","unstructured":"Holzman, R., Kfir-Dahav, N., Monderer, D., Tennenholtz, M.: Bundling equilibrium in combinatorial auctions. Games Econ. Behav. 47, 104\u2013123 (2004)","journal-title":"Games Econ. Behav."},{"key":"9854_CR25","first-page":"574","volume-title":"Proceedings of the 44rd IEEE Symposium Foundations of Computer Science, FOCS","author":"R. Lavi","year":"2003","unstructured":"Lavi, R., Mu\u2019alem, A., Nisan, N.: Towards a characterization of truthful combinatorial auctions. In: Proceedings of the 44rd IEEE Symposium Foundations of Computer Science, FOCS, pp. 574\u2013583 (2003)"},{"key":"9854_CR26","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2049697.2049699","volume":"25","author":"R. Lavi","year":"2011","unstructured":"Lavi, R., Swamy, C.: Truthful and near-optimal mechanism design via linear programming. J. ACM 25, 1 (2011)","journal-title":"J. ACM"},{"issue":"2","key":"9854_CR27","doi-asserted-by":"crossref","first-page":"270","DOI":"10.1016\/j.geb.2005.02.006","volume":"55","author":"B. Lehmann","year":"2006","unstructured":"Lehmann, B., Lehmann, D., Nisan, N.: Combinatorial auctions with decreasing marginal utilities. Games Econ. Behav. 55(2), 270\u2013296 (2006)","journal-title":"Games Econ. Behav."},{"issue":"5","key":"9854_CR28","doi-asserted-by":"crossref","first-page":"577","DOI":"10.1145\/585265.585266","volume":"49","author":"D. Lehmann","year":"2002","unstructured":"Lehmann, D., O\u2019Callaghan, L.I., Shoham, Y.: Truth revelation in rapid, approximately efficient combinatorial auctions. J. ACM 49(5), 577\u2013602 (2002)","journal-title":"J. ACM"},{"issue":"2","key":"9854_CR29","doi-asserted-by":"crossref","first-page":"612","DOI":"10.1016\/j.geb.2007.12.009","volume":"64","author":"A. Mu\u2019alem","year":"2008","unstructured":"Mu\u2019alem, A., Nisan, N.: Truthful approximation mechanisms for restricted combinatorial auctions. Games Econ. Behav. 64(2), 612\u2013631 (2008)","journal-title":"Games Econ. Behav."},{"key":"9854_CR30","doi-asserted-by":"crossref","first-page":"58","DOI":"10.1287\/moor.6.1.58","volume":"6","author":"R. Myerson","year":"1981","unstructured":"Myerson, R.: Optimal auction design. Math. Oper. Res. 6, 58\u201373 (1981)","journal-title":"Math. Oper. Res."},{"key":"9854_CR31","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1006\/game.1999.0790","volume":"35","author":"N. Nisan","year":"2001","unstructured":"Nisan, N., Ronen, A.: Algorithmic mechanism design. Games Econ. Behav. 35, 166\u2013196 (2001)","journal-title":"Games Econ. Behav."},{"key":"9854_CR32","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1613\/jair.2046","volume":"29","author":"N. Nisan","year":"2007","unstructured":"Nisan, N., Ronen, A.: Computationally feasible vcg-based mechanisms. J. Artif. Intell. Res. 29, 19\u201347 (2007)","journal-title":"J. Artif. Intell. Res."},{"key":"9854_CR33","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511800481","volume-title":"Algorithmic Game Theory","author":"N. Nisan","year":"2007","unstructured":"Nisan, N., Roughgarden, T., Tardos, E., Vazirani, V.V.: Algorithmic Game Theory. Cambridge University Press, New York (2007)"},{"key":"9854_CR34","first-page":"749","volume-title":"Proceedings of the 33rd ACM Symposium on Theory of Computing","author":"C.H. Papadimitriou","year":"2001","unstructured":"Papadimitriou, C.H.: Algorithm, games, and the internet. In: Proceedings of the 33rd ACM Symposium on Theory of Computing, pp. 749\u2013753 (2001)"},{"key":"9854_CR35","first-page":"321","volume-title":"Aggregation and Revelation of Preferences","author":"K. Roberts","year":"1979","unstructured":"Roberts, K.: The characterization of implementable choice rules. In: Laffont, J.-J. (ed.) Aggregation and Revelation of Preferences, pp. 321\u2013348 (1979)"},{"issue":"8","key":"9854_CR36","doi-asserted-by":"crossref","first-page":"1131","DOI":"10.1287\/mnsc.44.8.1131","volume":"44","author":"M.H. Rothkhof","year":"1998","unstructured":"Rothkhof, M.H., Pekec, A., Harstad, R.M.: Computationally manageable combinatorial auctions. Manag. Sci. 44(8), 1131\u20131147 (1998)","journal-title":"Manag. Sci."},{"key":"9854_CR37","first-page":"542","volume-title":"Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence IJCAI","author":"T. Sandholm","year":"1999","unstructured":"Sandholm, T.: An algorithm for optimal winner determination in combinatorial auctions. In: Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence IJCAI, pp. 542\u2013547 (1999)"},{"issue":"1","key":"9854_CR38","doi-asserted-by":"crossref","first-page":"8","DOI":"10.1111\/j.1540-6261.1961.tb02789.x","volume":"16","author":"W. Vickrey","year":"1961","unstructured":"Vickrey, W.: Counterspeculation, auctions, and competitive sealed tenders. J. Finance 16(1), 8\u201337 (1961)","journal-title":"J. Finance"},{"issue":"3","key":"9854_CR39","doi-asserted-by":"crossref","first-page":"284","DOI":"10.1287\/ijoc.15.3.284.16077","volume":"15","author":"R.V. Vohra","year":"2003","unstructured":"Vohra, R.V., de Vries, S.: Combinatorial auctions: a survey. INFORMS J. Comput. 15(3), 284\u2013309 (2003)","journal-title":"INFORMS J. Comput."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-013-9854-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-013-9854-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-013-9854-4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,4]],"date-time":"2019-08-04T00:22:02Z","timestamp":1564878122000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-013-9854-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,11,23]]},"references-count":39,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2015,5]]}},"alternative-id":["9854"],"URL":"https:\/\/doi.org\/10.1007\/s00453-013-9854-4","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,11,23]]}}}