Scholarlink

<p>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. We consider the fairness criterion known as the <i>maximin share</i> (MMS) <i>guarantee</i>, and propose a novel polynomial-time algorithm for finding 1/2-approximate MMS allocations for goods—an improvement from the previously best available guarantee of 11/30. For single-category instances, we show that a modified variant of our algorithm is guaranteed to produce 2/3-approximate MMS allocations. Among various other existence and non-existence results, we show that a <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\((\sqrt{n}/(2\sqrt{n} - 1))\)</EquationSource> </InlineEquation>-approximate MMS allocation always exists for goods. For chores, we show similar results as for goods, with a 2-approximate algorithm in the general case and a 3/2-approximate algorithm for single-category instances. We extend the notions and algorithms related to <i>ordered</i> and <i>reduced instances</i> to work with cardinality constraints, and combine these with <i>bag filling</i> style procedures to construct our algorithms.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Maximin shares under cardinality constraints

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2026年2月17日

查看全文
  • Halvard Hummel,
  • Magnus Lie Hetland

摘要

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. We consider the fairness criterion known as the maximin share (MMS) guarantee, and propose a novel polynomial-time algorithm for finding 1/2-approximate MMS allocations for goods—an improvement from the previously best available guarantee of 11/30. For single-category instances, we show that a modified variant of our algorithm is guaranteed to produce 2/3-approximate MMS allocations. Among various other existence and non-existence results, we show that a \((\sqrt{n}/(2\sqrt{n} - 1))\) -approximate MMS allocation always exists for goods. For chores, we show similar results as for goods, with a 2-approximate algorithm in the general case and a 3/2-approximate algorithm for single-category instances. We extend the notions and algorithms related to ordered and reduced instances to work with cardinality constraints, and combine these with bag filling style procedures to construct our algorithms.