{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T17:56:26Z","timestamp":1725558986131},"publisher-location":"Berlin, Heidelberg","reference-count":31,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642141645"},{"type":"electronic","value":"9783642141652"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-14165-2_9","type":"book-chapter","created":{"date-parts":[[2010,7,5]],"date-time":"2010-07-05T13:26:02Z","timestamp":1278336362000},"page":"90-101","source":"Crossref","is-referenced-by-count":5,"title":["On the Limitations of Greedy Mechanism Design for Truthful Combinatorial Auctions"],"prefix":"10.1007","author":[{"given":"Allan","family":"Borodin","sequence":"first","affiliation":[]},{"given":"Brendan","family":"Lucier","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"9_CR1","doi-asserted-by":"crossref","unstructured":"Azar, Y., Gamzu, I., Gutner, S.: Truthful unsplittable flow for large capacity networks. In: Proc. 19th ACM Symp. on Parallel Algorithms and Architectures (2007)","DOI":"10.1145\/1248377.1248432"},{"key":"9_CR2","doi-asserted-by":"crossref","unstructured":"Babaioff, M., Blumrosen, L.: Computationally-feasible truthful auctions for convex bundles. In: Proc. 7th Intl. Workshop on Approximation Algorithms for Combinatorial Optimization Problems (2004)","DOI":"10.1007\/978-3-540-27821-4_3"},{"key":"9_CR3","doi-asserted-by":"publisher","first-page":"1069","DOI":"10.1145\/502102.502107","volume":"48","author":"A. Bar-Noy","year":"2001","unstructured":"Bar-Noy, A., Bar-Yehuda, R., Freund, A., Naor, J., Schieber, B.: A unified approach to approximating resource allocation and scheduling. Journal of the ACM\u00a048, 1069\u20131090 (2001)","journal-title":"Journal of the ACM"},{"key":"9_CR4","doi-asserted-by":"crossref","unstructured":"Bartal, Y., Gonen, R., Nisan, N.: Incentive compatible multi unit combinatorial auctions. In: Proc. 9th Conf. on Theoretical Aspects of Rationality and Knowledge (2003)","DOI":"10.1145\/846241.846250"},{"key":"9_CR5","doi-asserted-by":"crossref","unstructured":"Borodin, A., Cashman, D., Magen, A.: How well can primal-dual and local-ratio algorithms perform? In: Proc. 32nd Intl. Colloq. on Automata, Languages and Programming (2005)","DOI":"10.1007\/11523468_76"},{"key":"9_CR6","doi-asserted-by":"crossref","unstructured":"Borodin, A., Lucier, B.: Price of anarchy for greedy auctions. In: Proc. 21th ACM Symp. on Discrete Algorithms (2010)","DOI":"10.1137\/1.9781611973075.46"},{"key":"9_CR7","unstructured":"Borodin, A., Nielsen, M.N., Rackoff, C.: (incremental) priority algorithms. In: Proc. 13th ACM Symp. on Discrete Algorithms (2002)"},{"key":"9_CR8","doi-asserted-by":"crossref","unstructured":"Briest, P., Krysta, P., V\u00f6cking, B.: Approximation techniques for utilitarian mechanism design. In: Proc. 36th ACM Symp. on Theory of Computing (2005)","DOI":"10.1145\/1060590.1060597"},{"key":"9_CR9","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: Proc. 21st ACM Symp. on Discrete Algorithms (2010)","DOI":"10.1137\/1.9781611973075.45"},{"key":"9_CR10","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Gamzu, I.: Truthful mechanisms via greedy iterative packing. In: Proc. 12th Intl. Workshop on Approximation Algorithms for Combinatorial Optimization Problems (2009)","DOI":"10.1007\/978-3-642-03685-9_5"},{"key":"9_CR11","doi-asserted-by":"crossref","unstructured":"Christodoulou, G., Kov\u00e1cs, A., Schapira, M.: Bayesian combinatorial auctions. In: Proc. 35th Intl. Colloq. on Automata, Languages and Programming, pp. 820\u2013832 (2008)","DOI":"10.1007\/978-3-540-70575-8_67"},{"key":"9_CR12","doi-asserted-by":"crossref","unstructured":"Dobzinski, S., Nisan, N., Schapira, M.: Approximation algorithms for combinatorial auctions with complement-free bidders. In: Proc. 36th ACM Symp. on Theory of Computing (2005)","DOI":"10.1145\/1060590.1060681"},{"key":"9_CR13","doi-asserted-by":"crossref","unstructured":"Dobzinski, S., Schapira, M.: An improved approximation algorithm for combinatorial auctions with submodular bidders. In: Proc. 17th ACM Symp. on Discrete Algorithms (2006)","DOI":"10.1145\/1109557.1109675"},{"key":"9_CR14","doi-asserted-by":"crossref","unstructured":"Dobzinski, S., Sundararajan, M.: On characterizations of truthful mechanisms for combinatorial auctions and scheduling. In: Proc. 10th ACM Conf. on Electronic Commerce (2008)","DOI":"10.1145\/1386790.1386798"},{"key":"9_CR15","doi-asserted-by":"crossref","unstructured":"Gonen, R., Lehmann, D.: Optimal solutions for multi-unit combinatorial auctions: Branch and bound heuristics. In: Proc. 2nd ACM Conf. on Electronic Commerce (2000)","DOI":"10.1145\/352871.352873"},{"key":"9_CR16","unstructured":"Hastad, J.: Clique is hard to approximate within n 1\u2009\u2212\u2009\u03b5 . Electronic Colloquium on Computational Complexity\u00a038 (1997)"},{"key":"9_CR17","doi-asserted-by":"publisher","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 combinatiorial auctions. Games and Economic Behavior\u00a047, 104\u2013123 (2004)","journal-title":"Games and Economic Behavior"},{"key":"9_CR18","unstructured":"Horn, S.: One-pass algorithms with revocable acceptances for job interval selection. University of Toronto MSC thesis (2004)"},{"key":"9_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1007\/11600930_10","volume-title":"Internet and Network Economics","author":"S. Khot","year":"2005","unstructured":"Khot, S., Lipton, R., Markakis, E., Mehta, A.: Inapproximability results for combinatorial auctions with submodular utility functions. In: Deng, X., Ye, Y. (eds.) WINE 2005. LNCS, vol.\u00a03828, pp. 92\u2013101. Springer, Heidelberg (2005)"},{"key":"9_CR20","doi-asserted-by":"crossref","unstructured":"Krysta, P.: Greedy approximation via duality for packing, combinatorial auctions and routing. In: Proc. 30th Intl. Symp. on Mathematical Foundations of Computer Science (2005)","DOI":"10.1007\/11549345_53"},{"key":"9_CR21","doi-asserted-by":"crossref","unstructured":"Lavi, R., Mu\u2019alem, A., Nisan, N.: Towards a characterization of truthful combinatorial auctions. In: Proc. 44th IEEE Symp. on Foundations of Computer Science (2003)","DOI":"10.1109\/SFCS.2003.1238230"},{"key":"9_CR22","unstructured":"Lavi, R., Nisan, N.: Online ascending auctions for gradually expiring goods. In: Proc. 16th ACM Symp. on Discrete Algorithms (2005)"},{"key":"9_CR23","doi-asserted-by":"crossref","unstructured":"Lavi, R., Swamy, C.: Truthful and near-optimal mechanism design via linear programming. In: Proc. 46th IEEE Symp. on Foundations of Computer Science (2005)","DOI":"10.1109\/SFCS.2005.76"},{"key":"9_CR24","doi-asserted-by":"crossref","unstructured":"Lehmann, B., Lehmann, D., Nisan, N.: Combinatorial auctions with decreasing marginal utilities. In: Proc. 3rd ACM Conf. on Electronic Commerce (2001)","DOI":"10.1145\/501158.501161"},{"key":"9_CR25","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1145\/336992.337016","volume-title":"Proc. 1st ACM Conf. on Electronic Commerce","author":"D. Lehmann","year":"1999","unstructured":"Lehmann, D., O\u2019Callaghan, L.I., Shoham, Y.: Truth revelation in approximately efficient combinatorial auctions. In: Proc. 1st ACM Conf. on Electronic Commerce, pp. 96\u2013102. ACM Press, New York (1999)"},{"key":"9_CR26","unstructured":"Paes Leme, R., Tardos, E.: Sponsored search equilibria for conservative bidders. In: Fifth Workshop on Ad Auctions (2009)"},{"key":"9_CR27","doi-asserted-by":"crossref","unstructured":"Mahdian, M., Saberi, A.: Multi-unit auctions with unknown supply. In: Proc. 8th ACM Conf. on Electronic Commerce (2006)","DOI":"10.1145\/1134707.1134734"},{"key":"9_CR28","doi-asserted-by":"publisher","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 and Economic Behavior\u00a064, 612\u2013631 (2008)","journal-title":"Games and Economic Behavior"},{"key":"9_CR29","doi-asserted-by":"crossref","unstructured":"Nisan, N.: Bidding and allocation in combinatorial auctions. In: Proc. 2nd ACM Conf. on Electronic Commerce (2000)","DOI":"10.1145\/352871.352872"},{"key":"9_CR30","doi-asserted-by":"crossref","unstructured":"Papadimitriou, C., Schapira, M., Singer, Y.: On the hardness of being truthful. In: Proc. 49th IEEE Symp. on Foundations of Computer Science (2008)","DOI":"10.1109\/FOCS.2008.54"},{"key":"9_CR31","doi-asserted-by":"crossref","unstructured":"Zuckerman, D.: Linear degree extractors and the inapproximability of max clique and chromatic number. In: Proc. 37th ACM Symp. on Theory of Computing (2006)","DOI":"10.1145\/1132516.1132612"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-14165-2_9.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T02:48:24Z","timestamp":1606186104000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-14165-2_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642141645","9783642141652"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-14165-2_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}