  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.
