Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

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.

[img]
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
Official URL: http://doi.org/10.4230/LIPIcs.STACS.2015.90

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:
DateEvent
2015Published
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:
  • Publisher
  • Organisation

Request changes or add full text files to a record

Repository staff actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics

twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us