---
_id: '11903'
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 \U0001D442(\U0001D45B√)-approximation
    algorithm for general concave externality functions, (ii) an O(log m)-approximation
    algorithm for linear externality functions, and (iii) a 518(1−1/\U0001D452)-approximation
    algorithm for 2-hop step function externalities. We also improve the result from
    [7] for 1-hop step function externalities by giving a 12(1−1/\U0001D452)-approximation
    algorithm."
article_processing_charge: No
article_type: original
author:
- first_name: Sayan
  full_name: Bhattacharya, Sayan
  last_name: Bhattacharya
- first_name: Wolfgang
  full_name: Dvořák, Wolfgang
  last_name: Dvořá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, Dvořák W, Henzinger M, Starnberger M. Welfare maximization
    with friends-of-friends network externalities. <i>Theory of Computing Systems</i>.
    2017;61(4):948-986. doi:<a href="https://doi.org/10.1007/s00224-017-9759-8">10.1007/s00224-017-9759-8</a>
  apa: Bhattacharya, S., Dvořák, W., Henzinger, M., &#38; Starnberger, M. (2017).
    Welfare maximization with friends-of-friends network externalities. <i>Theory
    of Computing Systems</i>. Springer Nature. <a href="https://doi.org/10.1007/s00224-017-9759-8">https://doi.org/10.1007/s00224-017-9759-8</a>
  chicago: Bhattacharya, Sayan, Wolfgang Dvořák, Monika Henzinger, and Martin Starnberger.
    “Welfare Maximization with Friends-of-Friends Network Externalities.” <i>Theory
    of Computing Systems</i>. Springer Nature, 2017. <a href="https://doi.org/10.1007/s00224-017-9759-8">https://doi.org/10.1007/s00224-017-9759-8</a>.
  ieee: S. Bhattacharya, W. Dvořák, M. Henzinger, and M. Starnberger, “Welfare maximization
    with friends-of-friends network externalities,” <i>Theory of Computing Systems</i>,
    vol. 61, no. 4. Springer Nature, pp. 948–986, 2017.
  ista: Bhattacharya S, Dvořák W, Henzinger M, Starnberger M. 2017. Welfare maximization
    with friends-of-friends network externalities. Theory of Computing Systems. 61(4),
    948–986.
  mla: Bhattacharya, Sayan, et al. “Welfare Maximization with Friends-of-Friends Network
    Externalities.” <i>Theory of Computing Systems</i>, vol. 61, no. 4, Springer Nature,
    2017, pp. 948–86, doi:<a href="https://doi.org/10.1007/s00224-017-9759-8">10.1007/s00224-017-9759-8</a>.
  short: S. Bhattacharya, W. Dvořák, M. Henzinger, M. Starnberger, Theory of Computing
    Systems 61 (2017) 948–986.
date_created: 2022-08-17T11:14:12Z
date_published: 2017-11-01T00:00:00Z
date_updated: 2024-11-06T12:24:23Z
day: '01'
doi: 10.1007/s00224-017-9759-8
extern: '1'
intvolume: '        61'
issue: '4'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.1007/s00224-017-9759-8
month: '11'
oa: 1
oa_version: Published Version
page: 948-986
publication: Theory of Computing Systems
publication_identifier:
  eissn:
  - 1433-0490
  issn:
  - 1432-4350
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
  record:
  - id: '11837'
    relation: earlier_version
    status: public
scopus_import: '1'
status: public
title: Welfare maximization with friends-of-friends network externalities
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 61
year: '2017'
...