Intervention problems in the Linear Threshold Model: A general formulation and new results
Abstract
We study an optimal intervention problem for linear threshold models. This is a popular class of dynamical network systems whereby a number of agents, identified with the nodes of a graph, strategically change their binary action (0 or 1) according to a threshold rule. Specifically, an agent adopts action 1 if and only if the fraction of its neighbors in the interaction graph that do so is greater than or equal to a prescribed threshold. Assuming that a planner can modify the agents' thresholds at a cost equal to the aggregate threshold increase, we study the minimum intervention cost needed to ensure global convergence to the all-1 configuration. Our main contribution is the introduction of a new graph-theoretic quantity, called oriented path number, that is the minimum number of disjoint paths needed to cover the graph that can be oriented to form a directed acyclic graph. When thresholds are all equal to 1/2, the optimal cost is shown to coincide with the oriented path number, whereas, in the general case, it turns out to be the main ingredient of a bound on the optimal intervention cost.
Related
- Fixed-Point Formulation and Parallel Averaged Operator Algorithms for Generalized Variational Inclusion Problems
- Local Multiple Traces Formulation for Transmission Problems in Linear Elasticity
- Apriori Estimates and Nonexistence Results for Some Quasilinear Problems in a Half-Space
- Generic Machine Learning-Based Sparsification for Arc Flow Formulation of Combinatorial Optimization Problems
- Numerical investigation of a Navier-Stokes-Korteweg system through an extended Lagrangian formulation: nonclassical waves and phase transition problems
BibTeX
@misc{como2026intervention,
title = {{Intervention problems in the Linear Threshold Model: A general formulation and new results}},
author = {Giacomo Como and Fabio Fagnani and Stephane Durand},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.17146},
eprint = {2609.17146},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.17146},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Intervention problems in the Linear Threshold Model: A general formulation and new results
AU - Giacomo Como
AU - Fabio Fagnani
AU - Stephane Durand
PY - 2026
DA - 2026/09/15
PB - arXiv
DO - 10.48550/arxiv.2609.17146
UR - https://arxiv.org/abs/2609.17146
AB - We study an optimal intervention problem for linear threshold models. This is a popular class of dynamical network systems whereby a number of agents, identified with the nodes of a graph, strategically change their binary action (0 or 1) according to a threshold rule. Specifically, an agent adopts action 1 if and only if the fraction of its neighbors in the interaction graph that do so is greater than or equal to a prescribed threshold. Assuming that a planner can modify the agents' thresholds at a cost equal to the aggregate threshold increase, we study the minimum intervention cost needed to ensure global convergence to the all-1 configuration. Our main contribution is the introduction of a new graph-theoretic quantity, called oriented path number, that is the minimum number of disjoint paths needed to cover the graph that can be oriented to form a directed acyclic graph. When thresholds are all equal to 1/2, the optimal cost is shown to coincide with the oriented path number, whereas, in the general case, it turns out to be the main ingredient of a bound on the optimal intervention cost.
ER -