Parameterized Complexity of Envy-Free Resource Allocation in Social Networks
Parameterized Complexity of Envy-Free Resource Allocation in Social Networks
复制标题
社交网络中无嫉妒资源分配的参数化复杂性
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
S. Ordyniak
中科院分区：
文献类型：
--
作者：
E. Eiben;R. Ganian;Thekla Hamm;S. Ordyniak
我们考虑以无嫉妒（并且在适用的情况下按比例）方式在代理之间分配资源的经典问题。最近，通过引入社交网络的概念丰富了基本模型，该概念允许捕获代理可能不具有有关所有资源分配的完整信息的情况。我们通过考虑捕获网络结构特性以及代理和项目之间相似性的自然参数来开始研究这些资源分配问题的参数化复杂性。特别是，我们表明，只要社交网络具有有限的树宽或有限的派系宽度，即使是所考虑问题的非常普遍的片段也变得容易处理。我们用匹配下限来补充我们的结果，这表明我们的算法无法得到实质性改进。
We consider the classical problem of allocating resources among agents in an envy-free (and, where applicable, proportional) way. Recently, the basic model was enriched by introducing the concept of a social network which allows to capture situations where agents might not have full information about the allocation of all resources. We initiate the study of the parameterized complexity of these resource allocation problems by considering natural parameters which capture structural properties of the network and similarities between agents and items. In particular, we show that even very general fragments of the considered problems become tractable as long as the social network has bounded treewidth or bounded clique-width. We complement our results with matching lower bounds which show that our algorithms cannot be substantially improved.