We study the problem of fair allocation of a set of indivisible items among agents with additive valuations, under cardinality constraints. In this setting the items are partitioned into categories, each with its own limit on the number of items it may contribute to any bundle. One example of such a problem is allocating seats in a multitrack conference. We consider the fairness measure known as the maximin share (MMS) guarantee, and propose a novel polynomial-time algorithm for finding $1/2$-approximate MMS allocations. We extend the notions and algorithms related to ordered and reduced instances to work with cardinality constraints, and combine these with a bag filling style procedure. Our algorithm improves on that of Biswas and Barman (IJCAI-18), with its approximation ratio of $1/3$. We also present an optimizing algorithm, which for each instance, instead of fixing $\alpha = 1/2$, uses bisection to find the largest $\alpha$ for which our algorithm obtains a valid $\alpha$-approximate MMS allocation. Numerical tests show that our algorithm finds strictly better approximations than the guarantee of $1/2$ for most instances, in many cases surpassing $3/5$. The optimizing version of the algorithm produces MMS allocations in a comparable number of instances to that of Biswas and Barman's algorithm, on average achieving a better approximation when MMS is not obtained.


翻译:我们研究了在具有添加价值的代理商中公平分配一组不可分割项目的问题,在基本限制之下,我们研究了如何在具有添加价值的代理商中公平分配一组不可分割的项目的问题;在这种设置中,项目被分成类别,每个项目都对它可能帮助的任何捆绑的项目数量有其自己的限制;这种问题的一个例子是在多轨会议上分配席位;我们考虑所谓的最大份额保证(MMS)的公平度度量,并提议一个新颖的多元时间算法,以找到1/2美元接近MMS的分配额;我们把与订购和减少的事件有关的概念和算法扩大到与主要限制的工作,并将这些概念和算法与包装风格程序结合起来;我们的算法改进了Biswas和Barman(IJCAI-18)的算法,其近似比率为1/3美元;我们还提出了一种最优化的算法,即“最大份额”=1/2美元,用双倍算法找出我们算法获得有效美元-近似MMS的分配额;数字测试表明,我们的算法在最大比例1/2MS的公式中发现,比最高比例为1/5的比最高分配额。

0
下载
关闭预览

相关内容

专知会员服务
50+阅读 · 2020年12月14日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
【论文笔记】通俗理解少样本文本分类 (Few-Shot Text Classification) (1)
深度学习自然语言处理
7+阅读 · 2020年4月8日
CCF推荐 | 国际会议信息10条
Call4Papers
8+阅读 · 2019年5月27日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
CCF A类 | 顶级会议RTSS 2019诚邀稿件
Call4Papers
10+阅读 · 2019年4月17日
Call for Participation: Shared Tasks in NLPCC 2019
中国计算机学会
5+阅读 · 2019年3月22日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Ray RLlib: Scalable 降龙十八掌
CreateAMind
9+阅读 · 2018年12月28日
已删除
将门创投
5+阅读 · 2018年10月16日
分布式TensorFlow入门指南
机器学习研究会
4+阅读 · 2017年11月28日
Linear Constraints Learning for Spiking Neurons
Arxiv
0+阅读 · 2021年8月11日
Arxiv
6+阅读 · 2021年6月24日
VIP会员
相关资讯
【论文笔记】通俗理解少样本文本分类 (Few-Shot Text Classification) (1)
深度学习自然语言处理
7+阅读 · 2020年4月8日
CCF推荐 | 国际会议信息10条
Call4Papers
8+阅读 · 2019年5月27日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
CCF A类 | 顶级会议RTSS 2019诚邀稿件
Call4Papers
10+阅读 · 2019年4月17日
Call for Participation: Shared Tasks in NLPCC 2019
中国计算机学会
5+阅读 · 2019年3月22日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Ray RLlib: Scalable 降龙十八掌
CreateAMind
9+阅读 · 2018年12月28日
已删除
将门创投
5+阅读 · 2018年10月16日
分布式TensorFlow入门指南
机器学习研究会
4+阅读 · 2017年11月28日
Top
微信扫码咨询专知VIP会员