Optimizing Social Welfare in Social Networks
Optimizing Social Welfare in Social Networks
复制标题
优化社交网络的社会福利
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
J. Rothe
中科院分区：
文献类型：
--
作者：
Pascal Lange;J. Rothe
研究了社交网络中无图嫉妒分配的嫉妒最小化和社会福利最大化的计算复杂性。除了已知的（mathrm {NP}）-完全性的最大功利主义的社会福利分配，我们证明（mathrm {NP}）-完全性一般也给出了平均主义的社会福利和纳什产品。此外，我们专注于一个扩展模型，基于有向社会关系图和无向社会交易图，并分析了计算复杂性，达到一个图形嫉妒免费分配的交易与所谓的不关心代理和没有钱。
We study the computational complexity of envy minimization and maximizing the social welfare of graph-envy-free allocations in social networks. Besides the already known (mathrm {NP})-completeness of finding allocations with maximal utilitarian social welfare we prove that (mathrm {NP})-completeness is in general also given for the egalitarian social welfare and the Nash product. Moreover, we focus on an extended model, based on directed social relationship graphs and undirected social trading graphs, and analyze the computational complexity of reaching a graph-envy-free allocation by trades with so-called don’t care agents and without money.