Bhattacharya, Sayan, Dvorák, Wolfgang, Henzinger, Monika and Starnberger, Martin (2015) Welfare maximization with friends-of-friends network externalities. In: 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015), München, Germany , 4-7 Mar 2015. Published in: 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015), 30 pp. 90-102. ISBN 9783939897781.

Preview

PDF WRAP-welfare-maximization-friends-friends-Bhattacharya-2015.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (1006Kb) | Preview

Request Changes to record.

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.

Item Type:	Conference Item (Paper)
Subjects:	H Social Sciences > HM Sociology Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software
Divisions:	Faculty of Science, Engineering and Medicine > Science > Computer Science
Library of Congress Subject Headings (LCSH):	Online social networks -- Mathematical models, Approximation algorithms
Series Name:	Leibniz International Proceedings in Informatics (LIPIcs)
Journal or Publication Title:	32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)
Publisher:	Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
Place of Publication:	Dagstuhl, Germany
ISBN:	9783939897781
Official Date:	2015
Dates:	Date Event 2015 Published
Volume:	30
Page Range:	pp. 90-102
Status:	Peer Reviewed
Publication Status:	Published
Date of first compliant deposit:	26 September 2017
Date of first compliant Open Access:	26 September 2017
Funder:	Seventh Framework Programme (European Commission) (FP7), Wiener Wissenschafts, Forschungs und Technologiefonds [Vienna Science and Technology Fund] (WWTF)
Grant number:	Grant agreement no. 317532 (FP7), Project ICT10-002 (WWTF)
Conference Paper Type:	Paper
Title of Event:	32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)
Type of Event:	Other
Location of Event:	München, Germany
Date(s) of Event:	4-7 Mar 2015
Related URLs:	Publisher Organisation

Request changes or add full text files to a record

Repository staff actions (login required)

View Item

Downloads