[{"scopus_import":"1","_id":"11837","author":[{"full_name":"Bhattacharya, Sayan","last_name":"Bhattacharya","first_name":"Sayan"},{"full_name":"Dvorák, Wolfgang","last_name":"Dvorák","first_name":"Wolfgang"},{"orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","first_name":"Monika H","last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630"},{"last_name":"Starnberger","first_name":" Martin","full_name":"Starnberger,  Martin"}],"date_created":"2022-08-12T11:39:40Z","article_processing_charge":"No","publication_status":"published","intvolume":"        30","alternative_title":["LIPIcs"],"title":"Welfare maximization with friends-of-friends network externalities","quality_controlled":"1","page":"90-102","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","year":"2015","citation":{"ieee":"S. Bhattacharya, W. Dvorák, M. H. Henzinger, and  Martin Starnberger, “Welfare maximization with friends-of-friends network externalities,” in <i>32nd International Symposium on Theoretical Aspects of Computer Science</i>, Garching, Germany, 2015, vol. 30, pp. 90–102.","chicago":"Bhattacharya, Sayan, Wolfgang Dvorák, Monika H Henzinger, and  Martin Starnberger. “Welfare Maximization with Friends-of-Friends Network Externalities.” In <i>32nd International Symposium on Theoretical Aspects of Computer Science</i>, 30:90–102. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015. <a href=\"https://doi.org/10.4230/LIPICS.STACS.2015.90\">https://doi.org/10.4230/LIPICS.STACS.2015.90</a>.","ama":"Bhattacharya S, Dvorák W, Henzinger MH, Starnberger  Martin. Welfare maximization with friends-of-friends network externalities. In: <i>32nd International Symposium on Theoretical Aspects of Computer Science</i>. Vol 30. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2015:90-102. doi:<a href=\"https://doi.org/10.4230/LIPICS.STACS.2015.90\">10.4230/LIPICS.STACS.2015.90</a>","apa":"Bhattacharya, S., Dvorák, W., Henzinger, M. H., &#38; Starnberger,  Martin. (2015). Welfare maximization with friends-of-friends network externalities. In <i>32nd International Symposium on Theoretical Aspects of Computer Science</i> (Vol. 30, pp. 90–102). Garching, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPICS.STACS.2015.90\">https://doi.org/10.4230/LIPICS.STACS.2015.90</a>","ista":"Bhattacharya S, Dvorák W, Henzinger MH, Starnberger  Martin. 2015. Welfare maximization with friends-of-friends network externalities. 32nd International Symposium on Theoretical Aspects of Computer Science. STACS: Symposium on Theoretical Aspects of Computer Science, LIPIcs, vol. 30, 90–102.","mla":"Bhattacharya, Sayan, et al. “Welfare Maximization with Friends-of-Friends Network Externalities.” <i>32nd International Symposium on Theoretical Aspects of Computer Science</i>, vol. 30, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015, pp. 90–102, doi:<a href=\"https://doi.org/10.4230/LIPICS.STACS.2015.90\">10.4230/LIPICS.STACS.2015.90</a>.","short":"S. Bhattacharya, W. Dvorák, M.H. Henzinger,  Martin Starnberger, in:, 32nd International Symposium on Theoretical Aspects of Computer Science, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015, pp. 90–102."},"date_updated":"2023-02-21T16:32:37Z","day":"26","doi":"10.4230/LIPICS.STACS.2015.90","abstract":[{"text":"Online social networks allow the collection of large amounts of data about the influence between users connected by a friendship-like relationship. When distributing items among agents forming a social network, this information allows us to exploit network externalities that each agent receives from his neighbors that get the same item. In this paper we consider Friends-of-Friends (2-hop) network externalities, i.e., externalities that not only depend on the neighbors that get the same item but also on neighbors of neighbors. For these externalities we study a setting where multiple different items are assigned to unit-demand agents. Specifically, we study the problem of welfare maximization under different types of externality functions. Let n be the number of agents and m be the number of items. Our contributions are the following: (1) We show that welfare maximization is APX-hard; we show that even for step functions with 2-hop (and also with 1-hop) externalities it is NP-hard to approximate social welfare better than (1-1/e). (2) On the positive side we present (i) an O(sqrt n)-approximation algorithm for general concave externality functions,\r\n(ii) an O(\\log m)-approximation algorithm for linear externality functions, and (iii) an (1-1/e)\\frac{1}{6}-approximation algorithm for 2-hop step function externalities. We also improve the result from [6] for 1-hop step function externalities by giving a (1-1/e)/2-approximation algorithm.","lang":"eng"}],"volume":30,"extern":"1","publication":"32nd International Symposium on Theoretical Aspects of Computer Science","oa_version":"Published Version","month":"02","language":[{"iso":"eng"}],"conference":{"end_date":"2015-03-07","location":"Garching, Germany","start_date":"2015-03-04","name":"STACS: Symposium on Theoretical Aspects of Computer Science"},"type":"conference","date_published":"2015-02-26T00:00:00Z","publication_identifier":{"issn":["1868-8969"],"isbn":["978-3-939897-78-1"]},"oa":1,"main_file_link":[{"open_access":"1","url":"https://doi.org/10.4230/LIPICS.STACS.2015.90"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public","related_material":{"record":[{"id":"11903","relation":"later_version","status":"public"}]}}]