{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T03:59:24Z","timestamp":1743134364234,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662489949"},{"type":"electronic","value":"9783662489956"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc\/2.5"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-662-48995-6_17","type":"book-chapter","created":{"date-parts":[[2015,12,8]],"date-time":"2015-12-08T18:37:29Z","timestamp":1449599849000},"page":"230-243","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Combinatorial Auctions with Conflict-Based Externalities"],"prefix":"10.1007","author":[{"given":"Yun Kuen","family":"Cheung","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Monika","family":"Henzinger","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Martin","family":"Hoefer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Martin","family":"Starnberger","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,12,30]]},"reference":[{"key":"17_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"621","DOI":"10.1007\/978-3-540-92185-1_68","volume-title":"Internet and Network Economics","author":"G Aggarwal","year":"2008","unstructured":"Aggarwal, G., Feldman, J., Muthukrishnan, S.M., P\u00e1l, M.: Sponsored search auctions with Markovian users. In: Papadimitriou, C., Zhang, S. (eds.) WINE 2008. LNCS, vol. 5385, pp. 621\u2013628. Springer, Heidelberg (2008)"},{"key":"17_CR2","doi-asserted-by":"crossref","unstructured":"Chan, S.O.: Approximation resistance from pairwise independent subgroups. In: 45th STOC, pp. 447\u2013456 (2013)","DOI":"10.1145\/2488608.2488665"},{"key":"17_CR3","unstructured":"Cheung, Y.K., Henzinger, M., Hoefer, M., Starnberger, M.: Combinatorial auctions with conflict-based externalities. CoRR abs\/1509.09147 (2015). http:\/\/arxiv.org\/abs\/1509.09147"},{"issue":"1","key":"17_CR4","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/j.jcss.2011.02.009","volume":"78","author":"V Conitzer","year":"2012","unstructured":"Conitzer, V., Sandholm, T.: Computing optimal outcomes under an expressive representation of settings with externalities. J. Comput. Syst. Sci. 78(1), 2\u201314 (2012)","journal-title":"J. Comput. Syst. Sci."},{"volume-title":"Combinatorial Auctions","year":"2006","key":"17_CR5","unstructured":"Cramton, P., Shoham, Y., Steinberg, R. (eds.): Combinatorial Auctions. MIT Press, Cambridge (2006)"},{"issue":"1","key":"17_CR6","doi-asserted-by":"publisher","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":"17_CR7","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parametrized Complexity","author":"R Downey","year":"1999","unstructured":"Downey, R., Fellows, M.: Parametrized Complexity. Springer, New York (1999)"},{"issue":"1","key":"17_CR8","doi-asserted-by":"publisher","first-page":"247","DOI":"10.4086\/toc.2010.v006a011","volume":"6","author":"U Feige","year":"2010","unstructured":"Feige, U., Vondr\u00e1k, J.: The submodular welfare problem with demand queries. Theory Comput. 6(1), 247\u2013290 (2010)","journal-title":"Theory Comput."},{"key":"17_CR9","doi-asserted-by":"crossref","unstructured":"Ghosh, A., Mahdian, M.: Externalities in online advertising. In: 17th WWW, pp. 161\u2013168 (2008)","DOI":"10.1145\/1367497.1367520"},{"key":"17_CR10","doi-asserted-by":"crossref","unstructured":"Ghosh, A., Sayedi, A.: Expressive auctions for externalities in online advertising. In: 19th WWW, pp. 371\u2013380 (2010)","DOI":"10.1145\/1772690.1772729"},{"key":"17_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1007\/978-3-642-10841-9_17","volume-title":"Internet and Network Economics","author":"R Gomes","year":"2009","unstructured":"Gomes, R., Immorlica, N., Markakis, E.: Externalities in keyword auctions: an empirical and theoretical assessment. In: Leonardi, S. (ed.) WINE 2009. LNCS, vol. 5929, pp. 172\u2013183. Springer, Heidelberg (2009)"},{"issue":"2","key":"17_CR12","doi-asserted-by":"publisher","first-page":"13:1","DOI":"10.1145\/2465769.2465778","volume":"1","author":"N Haghpanah","year":"2013","unstructured":"Haghpanah, N., Immorlica, N., Mirrokni, V., Munagala, K.: Optimal auctions with positive network externalities. ACM Trans. Econ. Comput. 1(2), 13:1\u201313:24 (2013)","journal-title":"ACM Trans. Econ. Comput."},{"key":"17_CR13","unstructured":"Halld\u00f3rsson, M.: A survey on independent set approximations. In: 1st APPROX, pp. 1\u201314 (1998)"},{"issue":"1","key":"17_CR14","first-page":"1","volume":"4","author":"MM Halld\u00f3rsson","year":"2000","unstructured":"Halld\u00f3rsson, M.M.: Approximations of weighted independent set and hereditary subset problems. J. Graph Alg. Appl. 4(1), 1\u201316 (2000)","journal-title":"J. Graph Alg. Appl."},{"issue":"5","key":"17_CR15","doi-asserted-by":"publisher","first-page":"1608","DOI":"10.1137\/S0097539700381097","volume":"31","author":"E Halperin","year":"2002","unstructured":"Halperin, E.: Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs. SIAM J. Comput. 31(5), 1608\u20131623 (2002)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"17_CR16","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/BF02392825","volume":"182","author":"J H\u00e5stad","year":"1999","unstructured":"H\u00e5stad, J.: Clique is hard to approximate within $$n^{1-\\varepsilon }$$. Acta Math. 182(1), 105\u2013142 (1999)","journal-title":"Acta Math."},{"key":"17_CR17","doi-asserted-by":"crossref","unstructured":"Hoefer, M., Kesselheim, T.: Secondary spectrum auctions for symmetric and submodular bidders. In: 13th EC, pp. 657\u2013671 (2012)","DOI":"10.1145\/2229012.2229062"},{"key":"17_CR18","doi-asserted-by":"crossref","unstructured":"Hoefer, M., Kesselheim, T.: Brief announcement: universally truthful secondary spectrum auctions. In: 25th SPAA, pp. 99\u2013101 (2013)","DOI":"10.1145\/2486159.2486163"},{"issue":"2\u20133","key":"17_CR19","first-page":"16","volume":"14","author":"M Hoefer","year":"2014","unstructured":"Hoefer, M., Kesselheim, T., V\u00f6cking, B.: Approximation algorithms for secondary spectrum auctions. ACM Trans. Internet Techn. 14(2\u20133), 16 (2014)","journal-title":"ACM Trans. Internet Techn."},{"key":"17_CR20","first-page":"814","volume":"86","author":"P Jehiel","year":"1996","unstructured":"Jehiel, P., Moldovanu, B., Stacchetti, E.: How (not) to sell nuclear weapons. Am. Econ. Rev. 86, 814\u2013829 (1996)","journal-title":"Am. Econ. Rev."},{"key":"17_CR21","doi-asserted-by":"publisher","first-page":"258","DOI":"10.1006\/jeth.1998.2501","volume":"85","author":"P Jehiel","year":"1999","unstructured":"Jehiel, P., Moldovanu, B., Stacchetti, E.: Multidimensional mechanism design for auctions with externalities. J. Econ. Theory 85, 258\u2013293 (1999)","journal-title":"J. Econ. Theory"},{"key":"17_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"585","DOI":"10.1007\/978-3-540-92185-1_65","volume-title":"Internet and Network Economics","author":"D Kempe","year":"2008","unstructured":"Kempe, D., Mahdian, M.: A cascade model for externalities in sponsored search. In: Papadimitriou, C., Zhang, S. (eds.) WINE 2008. LNCS, vol. 5385, pp. 585\u2013596. Springer, Heidelberg (2008)"},{"key":"17_CR23","unstructured":"Krysta, P., Michalak, T.P., Sandholm, T., Wooldridge, M.: Combinatorial auctions with externalities. In: 9th AAMAS, pp. 1471\u20131472 (2010)"},{"issue":"4","key":"17_CR24","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1561\/0400000009","volume":"1","author":"M Luby","year":"2005","unstructured":"Luby, M., Wigderson, A.: Pairwise independence and derandomization. Found. Trends Theor. Comput. Sci. 1(4), 237\u2013301 (2005)","journal-title":"Found. Trends Theor. Comput. Sci."},{"issue":"1","key":"17_CR25","doi-asserted-by":"publisher","first-page":"192","DOI":"10.1016\/j.jet.2004.10.007","volume":"129","author":"N Nisan","year":"2006","unstructured":"Nisan, N., Segal, I.: The communication requirements of efficient allocations and supporting prices. J. Econ. Theory 129(1), 192\u2013224 (2006)","journal-title":"J. Econ. Theory"},{"key":"17_CR26","doi-asserted-by":"crossref","unstructured":"Papadimitriou, P., Garcia-Molina, H.: Sponsored search auctions with conflict constraints. In: 5th WSDM, pp. 283\u2013292 (2012)","DOI":"10.1145\/2124295.2124332"},{"key":"17_CR27","unstructured":"Roughgarden, T., Tardos, \u00c9.: Do externalities degrade gsps efficiency. In: 8th Ad-Auctions Workshop (2012)"},{"key":"17_CR28","doi-asserted-by":"crossref","unstructured":"Zhou, X., Gandhi, S., Suri, S., Zheng, H.: eBay in the Sky: strategy-proof wireless spectrum auctions. In: 14th MobiCom, pp. 2\u201313 (2008)","DOI":"10.1145\/1409944.1409947"}],"container-title":["Lecture Notes in Computer Science","Web and Internet Economics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-48995-6_17","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,12,28]],"date-time":"2023-12-28T09:13:55Z","timestamp":1703754835000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-662-48995-6_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662489949","9783662489956"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-48995-6_17","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"30 December 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}