A Framework for Optimal Investment Strategies for Competing Camps in a Social Network

Abstract : Opinion dynamics is a natural and well-known phenomenon in a system of cognitive agents, and is a well-studied topic across several disciplines. We study the problem of optimally investing in nodes of a social network in a competitive setting, wherein two camps attempt to maximize adoption of their opinions by the population. This problem is highly relevant to applications such as elections, viral marketing, propagation of ideas or behaviors, etc. In particular, we propose an extension of the popular DeGroot-Friedkin model, show its convergence, and hence formulate the problem as a zero-sum game, where the players are the two camps and their strategies are the amounts to be invested on each node of the social network. We consider several settings, namely, when the influence of a camp on a node is a concave function of its investment on that node, when one of the camps has uncertain information about the values of the model parameters, and when a camp aims at maximizing competitor's investment required to drive the average opinion in its favor. We also study this game under common coupled constraints concerning the combined investment of the camps on each node, and analytically derive the optimal investment strategies of both the camps. The introduction of common coupled constraints results in maxmin value to be greater than or equal to the minmax value, an opposite inequality to the case of general functions; this can be perceived as a consequence of the first mover advantage in our game. We further study the possibility of campaigning in multiple phases, where the final opinion of a node in a phase acts as its initial bias for the next phase. We show that the utility functions of the two camps involve what can be interpreted as a multiphase version of Katz centrality. Focusing on opinion dynamics in two phases, we analyze their optimal investment strategies and derive the extent of loss that a camp would incur if it acted myopically. We then look at the setting in which a camp's influence on a node depends on the node's initial bias, for which we present a polynomial time algorithm for optimally splitting the budget between the two phases. We conduct a simulation study on real-world social networks for all the considered settings.
Complete list of metadatas

Cited literature [3 references]  Display  Hide  Download

https://hal.inria.fr/hal-01712293
Contributor : Swapnil Dhamal <>
Submitted on : Monday, February 19, 2018 - 12:49:26 PM
Last modification on : Thursday, October 17, 2019 - 12:35:25 PM
Long-term archiving on : Saturday, May 5, 2018 - 6:16:14 PM

File

pgmodays2017_dhamal.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01712293, version 1

Citation

Swapnil Dhamal, Walid Ben-Ameur, Tijani Chahed, Eitan Altman. A Framework for Optimal Investment Strategies for Competing Camps in a Social Network. PGMO Days 2017 – Gaspard Monge Program For Optimization, Operations Research and their Interactions with Data Sciences, Nov 2017, Paris, France. pp.1, 2017. ⟨hal-01712293⟩

Share

Metrics

Record views

436

Files downloads

48