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- 硬性, 在代理商中, 结构上可以解决其它的分类问题。

0
下载
关闭预览

相关内容

CC在计算复杂性方面表现突出。它的学科处于数学与计算机理论科学的交叉点,具有清晰的数学轮廓和严格的数学格式。官网链接:https://link.springer.com/journal/37
专知会员服务
61+阅读 · 2021年6月22日
专知会员服务
25+阅读 · 2021年4月2日
2019年机器学习框架回顾
专知会员服务
35+阅读 · 2019年10月11日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
已删除
将门创投
4+阅读 · 2018年12月10日
Arxiv
0+阅读 · 2022年1月26日
Arxiv
0+阅读 · 2022年1月26日
Arxiv
0+阅读 · 2022年1月25日
Arxiv
30+阅读 · 2021年8月18日
Arxiv
3+阅读 · 2020年5月1日
Arxiv
9+阅读 · 2020年2月15日
Arxiv
3+阅读 · 2018年2月24日
VIP会员
相关资讯
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
已删除
将门创投
4+阅读 · 2018年12月10日
相关论文
Arxiv
0+阅读 · 2022年1月26日
Arxiv
0+阅读 · 2022年1月26日
Arxiv
0+阅读 · 2022年1月25日
Arxiv
30+阅读 · 2021年8月18日
Arxiv
3+阅读 · 2020年5月1日
Arxiv
9+阅读 · 2020年2月15日
Arxiv
3+阅读 · 2018年2月24日
Top
微信扫码咨询专知VIP会员