We study fairness in house allocation, where $m$ houses are to be allocated among $n$ agents so that every agent receives one house. We show that maximizing the number of envy-free agents is hard to approximate to within a factor of $n^{1-\gamma}$ for any constant $\gamma>0$, and that the exact version is NP-hard even for binary utilities. Moreover, we prove that deciding whether a proportional allocation exists is computationally hard, whereas the corresponding problem for equitability can be solved efficiently.


翻译:我们研究住房分配的公平性,在住房分配中,美元住房将由一美元代理商分配,这样,每个代理商都能得到一栋房屋。 我们证明,对于任何恒定的$\gamma>0美元来说,最大限度地增加无嫉妒的代理商数量很难接近于1-\gamma}美元这一系数,而准确的版本甚至对于二元公用事业来说也是坚硬的NP。 此外,我们证明,确定比例分配是否在计算上是困难的,而相应的公平性问题是可以有效解决的。

0
下载
关闭预览

相关内容

专知会员服务
26+阅读 · 2021年7月11日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
元学习与图神经网络逻辑推导,55页ppt
专知会员服务
128+阅读 · 2020年4月25日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
CCF C类 | DSAA 2019 诚邀稿件
Call4Papers
6+阅读 · 2019年5月13日
ICLR2019最佳论文出炉
专知
12+阅读 · 2019年5月6日
人工智能 | ISAIR 2019诚邀稿件(推荐SCI期刊)
Call4Papers
6+阅读 · 2019年4月1日
LibRec 精选:近期15篇推荐系统论文
LibRec智能推荐
5+阅读 · 2019年3月5日
动物脑的好奇心和强化学习的好奇心
CreateAMind
10+阅读 · 2019年1月26日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Arxiv
0+阅读 · 2021年8月12日
Arxiv
0+阅读 · 2021年8月12日
Arxiv
0+阅读 · 2021年8月10日
Arxiv
0+阅读 · 2021年8月10日
Arxiv
3+阅读 · 2018年2月24日
VIP会员
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
CCF C类 | DSAA 2019 诚邀稿件
Call4Papers
6+阅读 · 2019年5月13日
ICLR2019最佳论文出炉
专知
12+阅读 · 2019年5月6日
人工智能 | ISAIR 2019诚邀稿件(推荐SCI期刊)
Call4Papers
6+阅读 · 2019年4月1日
LibRec 精选:近期15篇推荐系统论文
LibRec智能推荐
5+阅读 · 2019年3月5日
动物脑的好奇心和强化学习的好奇心
CreateAMind
10+阅读 · 2019年1月26日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Top
微信扫码咨询专知VIP会员