The Library
Welfare maximization with friends-of-friends network externalities
Tools
Tools
Tools
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.
|
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 |
Official URL: http://doi.org/10.4230/LIPIcs.STACS.2015.90
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: |
|
||||
| Volume: | 30 | ||||
| Page Range: | pp. 90-102 | ||||
| Status: | Peer Reviewed | ||||
| Publication Status: | Published | ||||
| 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: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
