We consider optimal intervention in the Elliott-Golub-Jackson network model \cite{jackson14} and we show that it can be transformed into an influence maximization-like form, interpreted as the reverse of a default cascade. Our analysis of the optimal intervention problem extends well-established targeting results to the economic network setting, which requires additional theoretical steps. We prove several results about optimal intervention: it is NP-hard and cannot be approximated to a constant factor in polynomial time. In turn, we show that randomizing failure thresholds leads to a version of the problem which is monotone submodular, for which existing powerful approximations in polynomial time can be applied. In addition to optimal intervention, we also show practical consequences of our analysis to other economic network problems: (1) it is computationally hard to calculate expected values in the economic network, and (2) influence maximization algorithms can enable efficient importance sampling and stress testing of large failure scenarios. We illustrate our results on a network of firms connected through input-output linkages inferred from the World Input Output Database.
翻译:我们考虑了Elliott-Golub-Jackson网络模型\cite{jackson14}中的最优干预,并且我们表明它可以被转化为一个类似于影响最大化的形式,解释为反向的默认级联。我们的最优干预问题分析扩展了针对经济网络设置的已有定向结果,这需要额外的理论步骤。我们证明了关于最优干预的几个结果:它是NP-hard问题,在多项式时间内无法近似为常量因子。反过来,我们表明将随机失效阈值导致的问题版本是单调子模的,对于这种情况,多项式时间内的现有强有力近似可以应用。除了最优干预之外,我们还展示了我们的分析对于其他经济网络问题的实际影响:(1)在经济网络中计算预期值是计算上困难的,(2)影响最大化算法可以实现大型失效方案的有效重要性抽样和压力测试。我们将我们的结果展示在一个通过从世界输入输出数据库中推断的输入-输出联系组成的公司网络上。