---
_id: '11837'
abstract:
- lang: eng
  text: "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,\r\n(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."
alternative_title:
- LIPIcs
article_processing_charge: No
author:
- first_name: Sayan
  full_name: Bhattacharya, Sayan
  last_name: Bhattacharya
- first_name: Wolfgang
  full_name: Dvorák, Wolfgang
  last_name: Dvorák
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
- first_name: ' Martin'
  full_name: Starnberger,  Martin
  last_name: Starnberger
citation:
  ama: 'Bhattacharya S, Dvorák W, Henzinger MH, Starnberger  Martin. Welfare maximization
    with friends-of-friends network externalities. In: <i>32nd International Symposium
    on Theoretical Aspects of Computer Science</i>. Vol 30. Schloss Dagstuhl - Leibniz-Zentrum
    für Informatik; 2015:90-102. doi:<a href="https://doi.org/10.4230/LIPICS.STACS.2015.90">10.4230/LIPICS.STACS.2015.90</a>'
  apa: 'Bhattacharya, S., Dvorák, W., Henzinger, M. H., &#38; Starnberger,  Martin.
    (2015). Welfare maximization with friends-of-friends network externalities. In
    <i>32nd International Symposium on Theoretical Aspects of Computer Science</i>
    (Vol. 30, pp. 90–102). Garching, Germany: Schloss Dagstuhl - Leibniz-Zentrum für
    Informatik. <a href="https://doi.org/10.4230/LIPICS.STACS.2015.90">https://doi.org/10.4230/LIPICS.STACS.2015.90</a>'
  chicago: Bhattacharya, Sayan, Wolfgang Dvorák, Monika H Henzinger, and  Martin Starnberger.
    “Welfare Maximization with Friends-of-Friends Network Externalities.” In <i>32nd
    International Symposium on Theoretical Aspects of Computer Science</i>, 30:90–102.
    Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015. <a href="https://doi.org/10.4230/LIPICS.STACS.2015.90">https://doi.org/10.4230/LIPICS.STACS.2015.90</a>.
  ieee: S. Bhattacharya, W. Dvorák, M. H. Henzinger, and  Martin Starnberger, “Welfare
    maximization with friends-of-friends network externalities,” in <i>32nd International
    Symposium on Theoretical Aspects of Computer Science</i>, Garching, Germany, 2015,
    vol. 30, pp. 90–102.
  ista: 'Bhattacharya S, Dvorák W, Henzinger MH, Starnberger  Martin. 2015. Welfare
    maximization with friends-of-friends network externalities. 32nd International
    Symposium on Theoretical Aspects of Computer Science. STACS: Symposium on Theoretical
    Aspects of Computer Science, LIPIcs, vol. 30, 90–102.'
  mla: Bhattacharya, Sayan, et al. “Welfare Maximization with Friends-of-Friends Network
    Externalities.” <i>32nd International Symposium on Theoretical Aspects of Computer
    Science</i>, vol. 30, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015,
    pp. 90–102, doi:<a href="https://doi.org/10.4230/LIPICS.STACS.2015.90">10.4230/LIPICS.STACS.2015.90</a>.
  short: S. Bhattacharya, W. Dvorák, M.H. Henzinger,  Martin Starnberger, in:, 32nd
    International Symposium on Theoretical Aspects of Computer Science, Schloss Dagstuhl
    - Leibniz-Zentrum für Informatik, 2015, pp. 90–102.
conference:
  end_date: 2015-03-07
  location: Garching, Germany
  name: 'STACS: Symposium on Theoretical Aspects of Computer Science'
  start_date: 2015-03-04
date_created: 2022-08-12T11:39:40Z
date_published: 2015-02-26T00:00:00Z
date_updated: 2023-02-21T16:32:37Z
day: '26'
doi: 10.4230/LIPICS.STACS.2015.90
extern: '1'
intvolume: '        30'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.4230/LIPICS.STACS.2015.90
month: '02'
oa: 1
oa_version: Published Version
page: 90-102
publication: 32nd International Symposium on Theoretical Aspects of Computer Science
publication_identifier:
  isbn:
  - 978-3-939897-78-1
  issn:
  - 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
related_material:
  record:
  - id: '11903'
    relation: later_version
    status: public
scopus_import: '1'
status: public
title: Welfare maximization with friends-of-friends network externalities
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 30
year: '2015'
...