Strategyproof mechanisms for competitive influence in networks

Allan Borodin, Mark Braverman, Brendan Lucier, Joel Oren

Research output: Chapter in Book/Report/Conference proceedingConference contribution

12 Scopus citations

Abstract

Motivated by applications to word-of-mouth advertising, we consider a game-theoretic scenario in which competing advertisers want to target initial adopters in a social network. Each advertiser wishes to maximize the resulting cascade of influence, modeled by a general network diffusion process. However, competition between products may adversely impact the rate of adoption for any given firm. The resulting framework gives rise to complex preferences that depend on the specifics of the stochastic diffusion model and the network topology. We study this model from the perspective of a central mechanism, such as a social networking platform, that can optimize seed placement as a service for the advertisers. We ask: given the reported demands of the competing firms, how should a mechanism choose seeds to maximize overall efficiency? Beyond the algorithmic problem, competition raises issues of strategic behaviour: rational agents should not be incentivized to underreport their budget demands. We show that when there are two players, the social welfare can be 2-approximated by a polynomial-time strategyproof mechanism. Our mechanism is defined recursively, randomizing the order in which advertisers are allocated seeds according to a particular greedy method. For three or more players, we demonstrate that under additional assumptions (satisfied by many existing models of influence spread) there exists a simpler strategyproof e/e-1 -approximation mechanism; notably, this second mechanism is not necessarily strategyproof when there are only two players. Copyright is held by the International World Wide Web Conference Committee (IW3C2).

Original languageEnglish (US)
Title of host publicationWWW 2013 - Proceedings of the 22nd International Conference on World Wide Web
PublisherAssociation for Computing Machinery
Pages141-151
Number of pages11
ISBN (Print)9781450320351
DOIs
StatePublished - 2013
Event22nd International Conference on World Wide Web, WWW 2013 - Rio de Janeiro, Brazil
Duration: May 13 2013May 17 2013

Publication series

NameWWW 2013 - Proceedings of the 22nd International Conference on World Wide Web

Other

Other22nd International Conference on World Wide Web, WWW 2013
CountryBrazil
CityRio de Janeiro
Period5/13/135/17/13

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications

Keywords

  • Influence spread
  • Mechanism design
  • Social networks

Fingerprint Dive into the research topics of 'Strategyproof mechanisms for competitive influence in networks'. Together they form a unique fingerprint.

Cite this