{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,8]],"date-time":"2025-03-08T15:40:09Z","timestamp":1741448409858,"version":"3.38.0"},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642229343"},{"type":"electronic","value":"9783642229350"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-22935-0_22","type":"book-chapter","created":{"date-parts":[[2011,8,12]],"date-time":"2011-08-12T09:20:39Z","timestamp":1313140839000},"page":"254-265","source":"Crossref","is-referenced-by-count":2,"title":["Black-Box Reductions in Mechanism Design"],"prefix":"10.1007","author":[{"given":"Zhiyi","family":"Huang","sequence":"first","affiliation":[]},{"given":"Lei","family":"Wang","sequence":"additional","affiliation":[]},{"given":"Yuan","family":"Zhou","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"22_CR1","first-page":"1054","volume-title":"Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithm (SODA)","author":"M. Babaioff","year":"2006","unstructured":"Babaioff, M., Lavi, R., Pavlov, E.: Single-value combinatorial auctions and implementation in undominated strategies. In: Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithm (SODA), pp. 1054\u20131063. ACM, New York (2006)"},{"key":"22_CR2","doi-asserted-by":"crossref","unstructured":"Balcan, M.-F., Blum, A., Hartline, J.D., Mansour, Y.: Mechanism design via machine learning. In: Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 605\u2013614 (2005)","DOI":"10.1109\/SFCS.2005.50"},{"key":"22_CR3","doi-asserted-by":"crossref","unstructured":"Bei, X., Huang, Z.: Bayesian incentive compatibility via fractional assignments. In: Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ( to appear, 2011)","DOI":"10.1137\/1.9781611973082.57"},{"key":"22_CR4","first-page":"39","volume-title":"Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC)","author":"P. Briest","year":"2005","unstructured":"Briest, P., Krysta, P., V\u00f6cking, B.: Approximation techniques for utilitarian mechanism design. In: Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC), pp. 39\u201348. ACM, New York (2005)"},{"key":"22_CR5","doi-asserted-by":"crossref","unstructured":"Buchfuhrer, D., Dughmi, S., Fu, H., Kleinberg, R., Mossel, E., Papadimitriou, C., Schapira, M., Singer, Y., Umans, C.: Inapproximability for vcg-based combinatorial auctions. In: Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA (2010)","DOI":"10.1137\/1.9781611973075.45"},{"key":"22_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1541885.1541893","volume":"5","author":"M. Charikar","year":"2009","unstructured":"Charikar, M., Makarychev, K., Makarychev, Y.: Near-optimal algorithms for maximum constraint satisfaction problems. ACM Trans. Algorithms\u00a05, 1\u201332 (2009)","journal-title":"ACM Trans. Algorithms"},{"key":"22_CR7","doi-asserted-by":"crossref","unstructured":"Clarke, E.H.: Multipart pricing of public goods. Public Choice\u00a011(1) (September 1971)","DOI":"10.1007\/BF01726210"},{"key":"22_CR8","doi-asserted-by":"crossref","unstructured":"Diakonikolas, I., Kane, D.M., Nelson, J.: Bounded independence fools degree-2 threshold functions. In: Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science, FOCS (2010)","DOI":"10.1109\/FOCS.2010.8"},{"key":"22_CR9","unstructured":"Shaddin, D., Tim, R.: Black-box randomized reductions in algorithmic mechanism design. In: Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science, FOCS (2010)"},{"key":"22_CR10","doi-asserted-by":"crossref","unstructured":"Dughmi, S., Roughgarden, T., Yan, Q.: From convex optimization to randomized mechanisms: Toward optimal combinatotial auctions for submodular bidders. In: Proceedings of the 43rd Annual ACM Symposium on Theory of Computing, STOC (2011)","DOI":"10.1145\/1993636.1993657"},{"issue":"4","key":"22_CR11","doi-asserted-by":"publisher","first-page":"497","DOI":"10.1002\/rsa.20226","volume":"33","author":"L. Engebretsen","year":"2008","unstructured":"Engebretsen, L., Holmerin, J.: More efficient queries in PCPs for NP and improved approximation hardness of maximum CSP. Random Structures & Algorithms\u00a033(4), 497\u2013514 (2008)","journal-title":"Random Structures & Algorithms"},{"key":"22_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"234","DOI":"10.1007\/978-3-642-16170-4_21","volume-title":"Algorithmic Game Theory","author":"G. Goel","year":"2010","unstructured":"Goel, G., Karande, C., Wang, L.: Single-parameter combinatorial auctions with partially public valuations. In: Kontogiannis, S., Koutsoupias, E., Spirakis, P.G. (eds.) Algorithmic Game Theory. LNCS, vol.\u00a06386, pp. 234\u2013245. Springer, Heidelberg (2010)"},{"issue":"4","key":"22_CR13","doi-asserted-by":"publisher","first-page":"617","DOI":"10.2307\/1914085","volume":"41","author":"T. Groves","year":"1973","unstructured":"Groves, T.: Incentives in teams. Econometrica\u00a041(4), 617\u2013631 (1973)","journal-title":"Econometrica"},{"key":"22_CR14","doi-asserted-by":"crossref","unstructured":"Hartline, J., Kleinberg, R., Malekian, A.: Bayesian incentive compatibility via matchings. In: Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ( to appear, 2011)","DOI":"10.1137\/1.9781611973082.58"},{"key":"22_CR15","first-page":"301","volume-title":"Proceedings of the 42nd Annual ACM Symposium on Theory of Computing (STOC)","author":"J.D. Hartline","year":"2010","unstructured":"Hartline, J.D., Lucier, B.: Bayesian algorithmic mechanism design. In: Proceedings of the 42nd Annual ACM Symposium on Theory of Computing (STOC), pp. 301\u2013310. ACM, New York (2010)"},{"issue":"2","key":"22_CR16","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1002\/rsa.10068","volume":"22","author":"J. H\u00e5stad","year":"2003","unstructured":"H\u00e5stad, J., Wigderson, A.: Simple analysis of graph tests for linearity and pcp. Random Structures and Algorithms\u00a022(2), 139\u2013160 (2003)","journal-title":"Random Structures and Algorithms"},{"key":"22_CR17","unstructured":"Daniel, M.: Kane and Jelani Nelson. A derandomized sparse Johnson-Lindenstrauss transform. Arxiv preprint arXiv:1006.3585 (2010)"},{"key":"22_CR18","doi-asserted-by":"publisher","first-page":"595","DOI":"10.1109\/SFCS.2005.76","volume-title":"Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS)","author":"R. Lavi","year":"2005","unstructured":"Lavi, R., Swamy, C.: Truthful and near-optimal mechanism design via linear programming. In: Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 595\u2013604. IEEE Computer Society, Washington, DC, USA (2005)"},{"key":"22_CR19","doi-asserted-by":"crossref","unstructured":"Meka, R., Zuckerman, D.: Pseudorandom generators for polynomial threshold functions. In: Proceedings of the 42nd Annual ACM Symposium on Theory of Computing (STOC), pp. 427\u2013436 (2010)","DOI":"10.1145\/1806689.1806749"},{"issue":"1","key":"22_CR20","doi-asserted-by":"publisher","first-page":"58","DOI":"10.1287\/moor.6.1.58","volume":"6","author":"R. Myerson","year":"1981","unstructured":"Myerson, R.: Optimal auction design. Mathematics of Operations Research\u00a06(1), 58\u201373 (1981)","journal-title":"Mathematics of Operations Research"},{"key":"22_CR21","doi-asserted-by":"crossref","unstructured":"Nisan, N., Ronen, A.: Algorithmic mechanism design. In: Proceedings of the 31st Annual ACM Symposium on Theory of Computing (STOC), pp. 129\u2013140 (1999)","DOI":"10.1145\/301250.301287"},{"key":"22_CR22","doi-asserted-by":"crossref","unstructured":"Papadimitriou, C., Schapira, M., Singer, Y.: On the hardness of being truthful. In: In 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS (2008)","DOI":"10.1109\/FOCS.2008.54"},{"key":"22_CR23","first-page":"191","volume-title":"Proceedings of the 32nd Annual ACM Symposium on Theory of Computing (STOC)","author":"A. Samorodnitsky","year":"2000","unstructured":"Samorodnitsky, A., Trevisan, L.: A PCP characterization of NP with optimal amortized query complexity. In: Proceedings of the 32nd Annual ACM Symposium on Theory of Computing (STOC), pp. 191\u2013199. ACM, New York (2000)"},{"issue":"1","key":"22_CR24","doi-asserted-by":"publisher","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. The Journal of Finance\u00a016(1), 8\u201337 (1961)","journal-title":"The Journal of Finance"},{"key":"22_CR25","first-page":"67","volume-title":"Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC)","author":"J. Vondrak","year":"2008","unstructured":"Vondrak, J.: Optimal approximation for the submodular welfare problem in the value oracle model. In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC), pp. 67\u201374. ACM, New York (2008)"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-22935-0_22","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,8]],"date-time":"2025-03-08T15:18:29Z","timestamp":1741447109000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-22935-0_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642229343","9783642229350"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-22935-0_22","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}