We study the computational complexity of finding fair allocations of indivisible goods in the setting where a social network on the agents is given. Notions of fairness in this context are "localized", that is, agents are only concerned about the bundles allocated to their neighbors, rather than every other agent in the system. We comprehensively address the computational complexity of finding locally envy-free and Pareto efficient allocations in the setting where the agents have binary valuations for the goods and the underlying social network is modeled by an undirected graph. We study the problem in the framework of parameterized complexity. We show that the problem is computationally intractable even in fairly restricted scenarios, for instance, even when the underlying graph is a path. We show NP-hardness for settings where the graph has only two distinct valuations among the agents. We demonstrate W-hardness with respect to the number of goods or the size of the vertex cover of the underlying graph. We also consider notions of proportionality that respect the structure of the underlying graph and show that two natural versions of this notion have different complexities: allocating according to the notion that accounts for locality to the greatest degree turns out to be computationally intractable, while for other notions, the allocation problem can be modeled as a structured ILP which can be solved efficiently.
翻译:我们研究了在代理商社会网络上找到公平分配不可分割货物的计算复杂性。 在给代理商提供社会网络的环境下找到公平分配不可分割货物的计算复杂性。 在这种背景下的公平性是“地方化的 ”, 也就是说, 代理商只关注分配给其邻居的捆包, 而不是系统中的所有其他代理商。 我们全面解决在代理商对货物进行二进制估值和基础社会网络的模型中找到当地无嫉妒和Pareto高效分配的计算复杂性。 我们还在参数化复杂度框架内研究这一问题。 我们表明,即使在基本图表是一种路径的情况下, 这一问题在计算上也是难以解决的。 我们显示, 在图表中,在代理商对货物数量或底图的顶层覆盖大小进行W- 硬性分析。 我们还考虑了尊重基本图表结构的相称性概念, 并表明, 这个概念的两个自然版本具有不同的复杂性: 我们根据一个概念, 将地点账户划分为最大程度的路径, 例如, 基本图表是一种路径。 我们显示该图只有两种不同的环境, 表明, 其环境的NP- 硬性, 在代理商中, 结构上可以解决其它的分类问题。