On the Hardness of Opinion Dynamics Optimization with L_1-Budget on Varying Susceptibility to Persuasion
share
Recently, Abebe et al. (KDD 2018) and Chan et al. (WWW 2019) have considered an opinion dynamics optimization problem that is based on a popular model for social opinion dynamics, in which each agent has some fixed innate opinion, and a resistance that measures the importance it places on its innate opinion; moreover, the agents influence one another's opinions through an iterative process. Under certain conditions, this iterative process converges to some equilibrium opinion vector. Previous works gave an efficient local search algorithm to solve the unbudgeted variant of the problem, for which the goal is to modify the resistance of any number of agents (within some given range) such that the sum of the equilibrium opinions is minimized. On the other hand, it was proved that the L_0-budgeted variant is NP-hard, where the L_0-budget is a restriction given upfront on the number of agents whose resistance may be modified. Inspired by practical situations in which the effort to modify an agent's resistance increases with the magnitude of the change, we propose the L_1-budgeted variant, in which the L_1-budget is a restriction on the sum of the magnitudes of the changes over all agents' resistance parameters. In this work, we show that the L_1-budgeted variant is NP-hard via a reduction from vertex cover. However, contrary to the L_0-budgeted variant, a very technical argument is needed to show that the optimal solution can be achieved by focusing the given L_1-budget on as small a number of agents as possible, as opposed to spreading the budget over a large number of agents.
READ FULL TEXT