We study the problem of dynamically allocating indivisible items to a group of agents in a fair manner. We assume that the items are goods and the valuation functions are additive without specification. Due to the negative results to achieve fairness, we allow adjustments to make fairness attainable with the objective to minimize the number of adjustments. We obtain positive results to achieve EF1 for (1) two agents with mixed manna, (2) restricted additive or general identical valuations, and (3) the default setting. We further impose the contiguity constraint on the items and require that each agent obtains a consecutive block of items. We obtain both positive and negative results to achieve either EF1 or proportionality with an additive approximate factor. In particular, we establish matching lower and upper bounds to achieve approximate proportionality for identical valuations. Our results exhibit the large discrepancy between the identical model and nonidentical model in both contiguous and noncontiguous settings. All our positive results are computationally efficient.


翻译:我们以公平的方式研究将不可分割的物品动态分配给一组代理人的问题,我们假定这些物品是货物,估价功能是不加具体说明的附加物。由于实现公平的消极结果,我们允许作出调整,以达到公平,目的是尽量减少调整的数量。我们为(1) 两种混合曼纳、(2) 限制性添加物或一般相同估值以及(3) 默认设置获得1 EF1 的积极成果。我们进一步限制物品的毗连性,要求每个代理人获得连续的一整块物品。我们取得正和负结果,既要达到EF1,要达到EF1,又要达到比例性,加上一个相加的近因数。特别是,我们建立相应的下限和上限线,以达到相同估值的大致相称性。我们的结果显示,在相邻和不相毗连的环境下,相同的模型和非相同的模型之间有很大差异。我们所有的积极结果都是计算有效的。

0
下载
关闭预览

相关内容

机器学习组合优化
专知会员服务
108+阅读 · 2021年2月16日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
VCIP 2022 Call for Demos
CCF多媒体专委会
1+阅读 · 2022年6月6日
征稿 | CFP:Special Issue of NLP and KG(JCR Q2,IF2.67)
开放知识图谱
1+阅读 · 2022年4月4日
VCIP 2022 Call for Special Session Proposals
CCF多媒体专委会
1+阅读 · 2022年4月1日
ACM MM 2022 Call for Papers
CCF多媒体专委会
5+阅读 · 2022年3月29日
AIART 2022 Call for Papers
CCF多媒体专委会
1+阅读 · 2022年2月13日
【ICIG2021】Latest News & Announcements of the Industry Talk1
中国图象图形学学会CSIG
0+阅读 · 2021年7月28日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
Arxiv
20+阅读 · 2021年9月22日
Arxiv
11+阅读 · 2018年9月28日
VIP会员
相关资讯
VCIP 2022 Call for Demos
CCF多媒体专委会
1+阅读 · 2022年6月6日
征稿 | CFP:Special Issue of NLP and KG(JCR Q2,IF2.67)
开放知识图谱
1+阅读 · 2022年4月4日
VCIP 2022 Call for Special Session Proposals
CCF多媒体专委会
1+阅读 · 2022年4月1日
ACM MM 2022 Call for Papers
CCF多媒体专委会
5+阅读 · 2022年3月29日
AIART 2022 Call for Papers
CCF多媒体专委会
1+阅读 · 2022年2月13日
【ICIG2021】Latest News & Announcements of the Industry Talk1
中国图象图形学学会CSIG
0+阅读 · 2021年7月28日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
相关基金
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
Top
微信扫码咨询专知VIP会员