Document Open Access Logo

Welfare Maximization with Friends-of-Friends Network Externalities

Authors Sayan Bhattacharya, Wolfgang Dvorák, Monika Henzinger, Martin Starnberger

PDF
Thumbnail PDF

File

LIPIcs.STACS.2015.90.pdf
  • Filesize: 0.66 MB
  • 13 pages

Document Identifiers

Author Details

Sayan Bhattacharya
Wolfgang Dvorák
Monika Henzinger
Martin Starnberger

Cite As Get BibTex

Sayan Bhattacharya, Wolfgang Dvorák, Monika Henzinger, and Martin Starnberger. Welfare Maximization with Friends-of-Friends Network Externalities. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 90-102, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://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.

Subject Classification

Keywords
  • network externalities
  • welfare maximization
  • approximation algorithms

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Hessameddin Akhlaghpour, Mohammad Ghodsi, Nima Haghpanah, Vahab S. Mirrokni, Hamid Mahini, and Afshin Nikzad. Optimal iterative pricing over social networks. In 6th WINE, pages 415-423, 2010. Google Scholar
  2. Noga Alon, Michal Feldman, Ariel D. Procaccia, and Moshe Tennenholtz. A note on competitive diffusion through social networks. Inf. Process. Lett., 110(6):221-225, 2010. Google Scholar
  3. Nima Anari, Shayan Ehsani, Mohammad Ghodsi, Nima Haghpanah, Nicole Immorlica, Hamid Mahini, and Vahab S. Mirrokni. Equilibrium pricing with positive externalities. Theor. Comput. Sci., 476:1-15, 2013. Google Scholar
  4. David Arthur, Rajeev Motwani, Aneesh Sharma, and Ying Xu. Pricing strategies for viral marketing on social networks. In 5th WINE, pages 101-112, 2009. Google Scholar
  5. Bernard Bensaid and Jean-Philippe Lesne. Dynamic monopoly pricing with network externalities. Int. J. of Industrial Organization, 14(6):837-855, 1996. Google Scholar
  6. Anand Bhalgat, Sreenivas Gollapudi, and Kamesh Munagala. Mechanisms and allocations with positive network externalities. In 13th EC, pages 179-196, 2012. Google Scholar
  7. Sayan Bhattacharya, Dmytro Korzhyk, and Vincent Conitzer. Computing a profit-maximizing sequence of offers to agents in a social network. In 8th WINE, pages 482-488, 2012. Google Scholar
  8. Pradeep Dubey, Rahul Garg, and Bernard De Meyer. Competing for customers in a social network: The quasi-linear case. In 2nd WINE, pages 162-173, 2006. Google Scholar
  9. Uriel Feige. On maximizing welfare when utility functions are subadditive. SIAM J. Comput., 39(1):122-142, 2009. Google Scholar
  10. Scott L. Feld. Why your friends have more friends than you do. American J. of Sociology, 96(6):1464-1477, 1991. Google Scholar
  11. Dimitris Fotakis and Paris Siminelakis. On the efficiency of influence-and-exploit strategies for revenue maximization under positive externalities. In 8th WINE, pages 270-283, 2012. Google Scholar
  12. Sanjeev Goyal and Michael Kearns. Competitive contagion in networks. In 44th STOC, pages 759-774, 2012. Google Scholar
  13. Nima Haghpanah, Nicole Immorlica, Vahab S. Mirrokni, and Kamesh Munagala. Optimal auctions with positive network externalities. ACM Trans. Economics and Comput., 1(2):13:1-13:24, 2013. Google Scholar
  14. Keith N. Hampton, Lauren Sessions Goulet, Cameron Marlow, and Lee Rainie. Why most facebook users get more than they give. Pew Internet & American Life Project, 2012. Google Scholar
  15. Jason Hartline, Vahab S. Mirrokni, and Mukund Sundararajan. Optimal marketing strategies over social networks. In 17th WWW, pages 189-198, 2008. Google Scholar
  16. Xinran He and David Kempe. Price of anarchy for the n-player competitive cascade game with submodular activation functions. In 9th WINE, pages 232-248, 2013. Google Scholar
  17. Matthew O. Jackson and Brian W. Rogers. Meeting strangers and friends of friends: How random are social networks? American Economic Review, 97(3):890-915, 2007. Google Scholar
  18. David Kempe, Jon M. Kleinberg, and Éva Tardos. Maximizing the spread of influence through a social network. In 9th KDD, pages 137-146, 2003. Google Scholar
  19. Vahab S. Mirrokni, Sebastien Roch, and Mukund Sundararajan. On fixed-price marketing for goods with positive network externalities. In 8th WINE, pages 532-538, 2012. Google Scholar
  20. Sunil Simon and Krzysztof R. Apt. Choosing products in social networks. In 8th WINE, pages 100-113, 2012. Google Scholar
  21. Reiko Takehara, Masahiro Hachimori, and Maiko Shigeno. A comment on pure-strategy nash equilibria in competitive diffusion games. Inf. Process. Lett., 112(3):59-60, 2012. Google Scholar
  22. Vasileios Tzoumas, Christos Amanatidis, and Evangelos Markakis. A game-theoretic analysis of a competitive diffusion process over social networks. In 8th WINE, pages 1-14, 2012. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact