Bhattacharya, Sayan ;
Dvorák, Wolfgang ;
Henzinger, Monika ;
Starnberger, Martin
Welfare Maximization with FriendsofFriends Network Externalities
Abstract
Online social networks allow the collection of large amounts of data about the influence between users connected by a friendshiplike 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 FriendsofFriends (2hop) 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 unitdemand 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 APXhard; we show that even for step functions with 2hop (and also with 1hop) externalities it is NPhard to approximate social welfare better than (11/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 (11/e)\frac{1}{6}approximation algorithm for 2hop step function externalities. We also improve the result from [6] for 1hop step function externalities by giving a (11/e)/2approximation 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 FriendsofFriends Network Externalities}},
booktitle = {32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
pages = {90102},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897781},
ISSN = {18688969},
year = {2015},
volume = {30},
editor = {Ernst W. Mayr and Nicolas Ollinger},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/4906},
URN = {urn:nbn:de:0030drops49066},
doi = {10.4230/LIPIcs.STACS.2015.90},
annote = {Keywords: network externalities, welfare maximization, approximation algorithms}
}
2015
Keywords: 

network externalities, welfare maximization, approximation algorithms 
Seminar: 

32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)

Issue date: 

2015 
Date of publication: 

2015 