When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2015.90
URN: urn:nbn:de:0030-drops-49066
URL: https://drops.dagstuhl.de/opus/volltexte/2015/4906/
 Go to the corresponding LIPIcs Volume Portal

### Welfare Maximization with Friends-of-Friends Network Externalities

 pdf-format:

### Abstract

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.

### BibTeX - Entry

@InProceedings{bhattacharya_et_al:LIPIcs:2015:4906,
author =	{Sayan Bhattacharya and Wolfgang Dvor{\'a}k and Monika Henzinger and Martin Starnberger},
title =	{{Welfare Maximization with Friends-of-Friends Network Externalities}},
booktitle =	{32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
pages =	{90--102},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-939897-78-1},
ISSN =	{1868-8969},
year =	{2015},
volume =	{30},
editor =	{Ernst W. Mayr and Nicolas Ollinger},
publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/4906},
URN =		{urn:nbn:de:0030-drops-49066},
doi =		{10.4230/LIPIcs.STACS.2015.90},
annote =	{Keywords: network externalities, welfare maximization, approximation algorithms}
}


 Keywords: network externalities, welfare maximization, approximation algorithms Collection: 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015) Issue Date: 2015 Date of publication: 26.02.2015

DROPS-Home | Fulltext Search | Imprint | Privacy