2026-08-15T16:55:54Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:4906 2024-03-06T10:35:31Z ddc:004 open_access

Welfare Maximization with Friends-of-Friends Network Externalities Bhattacharya, Sayan Dvorák, Wolfgang Henzinger, Monika Starnberger, Martin network externalities welfare maximization approximation algorithms 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, (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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sayan Bhattacharya and Wolfgang Dvorák and Monika Henzinger and Martin Starnberger 2015 Is Part Of LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2015.90 urn:nbn:de:0030-drops-49066 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.90 eng https://creativecommons.org/licenses/by/3.0/legalcode