[{"date_published":"2017-11-01T00:00:00Z","type":"journal_article","publication_identifier":{"issn":["1432-4350"],"eissn":["1433-0490"]},"oa":1,"main_file_link":[{"url":"https://doi.org/10.1007/s00224-017-9759-8","open_access":"1"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","related_material":{"record":[{"status":"public","relation":"earlier_version","id":"11837"}]},"status":"public","publication":"Theory of Computing Systems","oa_version":"Published Version","month":"11","language":[{"iso":"eng"}],"date_updated":"2023-02-21T16:29:58Z","citation":{"short":"S. Bhattacharya, W. Dvořák, M.H. Henzinger, M. Starnberger, Theory of Computing Systems 61 (2017) 948–986.","mla":"Bhattacharya, Sayan, et al. “Welfare Maximization with Friends-of-Friends Network Externalities.” <i>Theory of Computing Systems</i>, vol. 61, no. 4, Springer Nature, 2017, pp. 948–86, doi:<a href=\"https://doi.org/10.1007/s00224-017-9759-8\">10.1007/s00224-017-9759-8</a>.","ista":"Bhattacharya S, Dvořák W, Henzinger MH, Starnberger M. 2017. Welfare maximization with friends-of-friends network externalities. Theory of Computing Systems. 61(4), 948–986.","ama":"Bhattacharya S, Dvořák W, Henzinger MH, Starnberger M. Welfare maximization with friends-of-friends network externalities. <i>Theory of Computing Systems</i>. 2017;61(4):948-986. doi:<a href=\"https://doi.org/10.1007/s00224-017-9759-8\">10.1007/s00224-017-9759-8</a>","apa":"Bhattacharya, S., Dvořák, W., Henzinger, M. H., &#38; Starnberger, M. (2017). Welfare maximization with friends-of-friends network externalities. <i>Theory of Computing Systems</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s00224-017-9759-8\">https://doi.org/10.1007/s00224-017-9759-8</a>","chicago":"Bhattacharya, Sayan, Wolfgang Dvořák, Monika H Henzinger, and Martin Starnberger. “Welfare Maximization with Friends-of-Friends Network Externalities.” <i>Theory of Computing Systems</i>. Springer Nature, 2017. <a href=\"https://doi.org/10.1007/s00224-017-9759-8\">https://doi.org/10.1007/s00224-017-9759-8</a>.","ieee":"S. Bhattacharya, W. Dvořák, M. H. Henzinger, and M. Starnberger, “Welfare maximization with friends-of-friends network externalities,” <i>Theory of Computing Systems</i>, vol. 61, no. 4. Springer Nature, pp. 948–986, 2017."},"year":"2017","doi":"10.1007/s00224-017-9759-8","day":"01","abstract":[{"lang":"eng","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 𝑂(𝑛√)-approximation algorithm for general concave externality functions, (ii) an O(log m)-approximation algorithm for linear externality functions, and (iii) a 518(1−1/𝑒)-approximation algorithm for 2-hop step function externalities. We also improve the result from [7] for 1-hop step function externalities by giving a 12(1−1/𝑒)-approximation algorithm."}],"volume":61,"extern":"1","_id":"11903","scopus_import":"1","author":[{"full_name":"Bhattacharya, Sayan","first_name":"Sayan","last_name":"Bhattacharya"},{"full_name":"Dvořák, Wolfgang","last_name":"Dvořák","first_name":"Wolfgang"},{"id":"540c9bbd-f2de-11ec-812d-d04a5be85630","full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530","last_name":"Henzinger","first_name":"Monika H"},{"first_name":"Martin","last_name":"Starnberger","full_name":"Starnberger, Martin"}],"issue":"4","publication_status":"published","article_processing_charge":"No","date_created":"2022-08-17T11:14:12Z","title":"Welfare maximization with friends-of-friends network externalities","intvolume":"        61","page":"948-986","quality_controlled":"1","publisher":"Springer Nature","article_type":"original"}]