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)影响最大化算法可以实现大型失效方案的有效重要性抽样和压力测试。我们将我们的结果展示在一个通过从世界输入输出数据库中推断的输入-输出联系组成的公司网络上。

0
下载
关闭预览

相关内容

Networking:IFIP International Conferences on Networking。 Explanation:国际网络会议。 Publisher:IFIP。 SIT: http://dblp.uni-trier.de/db/conf/networking/index.html
【干货书】工程和科学中的概率和统计,
专知会员服务
57+阅读 · 2022年12月24日
【硬核书】稀疏多项式优化:理论与实践,220页pdf
专知会员服务
66+阅读 · 2022年9月30日
【硬核书】树与网络上的概率,716页pdf
专知会员服务
71+阅读 · 2021年12月8日
专知会员服务
25+阅读 · 2021年4月2日
NeurlPS2022推荐系统论文集锦
机器学习与推荐算法
1+阅读 · 2022年9月26日
动手实现推荐系统评价指标
机器学习与推荐算法
1+阅读 · 2022年6月1日
征稿 | International Joint Conference on Knowledge Graphs (IJCKG)
开放知识图谱
2+阅读 · 2022年5月20日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
vae 相关论文 表示学习 1
CreateAMind
12+阅读 · 2018年9月6日
【推荐】用Python/OpenCV实现增强现实
机器学习研究会
14+阅读 · 2017年11月16日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
【推荐】RNN/LSTM时序预测
机器学习研究会
25+阅读 · 2017年9月8日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
26+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2008年12月31日
Arxiv
19+阅读 · 2020年7月13日
VIP会员
相关资讯
NeurlPS2022推荐系统论文集锦
机器学习与推荐算法
1+阅读 · 2022年9月26日
动手实现推荐系统评价指标
机器学习与推荐算法
1+阅读 · 2022年6月1日
征稿 | International Joint Conference on Knowledge Graphs (IJCKG)
开放知识图谱
2+阅读 · 2022年5月20日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
vae 相关论文 表示学习 1
CreateAMind
12+阅读 · 2018年9月6日
【推荐】用Python/OpenCV实现增强现实
机器学习研究会
14+阅读 · 2017年11月16日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
【推荐】RNN/LSTM时序预测
机器学习研究会
25+阅读 · 2017年9月8日
相关基金
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
26+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2008年12月31日
Top
微信扫码咨询专知VIP会员