We consider the problem of fairly allocating indivisible goods, among agents,
under cardinality constraints and additive valuations. In this setting, we are
given a partition of the entire set of goods---i.e., the goods are
categorized---and a limit is specified on the number of goods that can be
allocated from each category to any agent. The objective here is to find a fair
allocation in which the subset of goods assigned to any agent satisfies the
given cardinality constraints. This problem naturally captures a number of
resource-allocation applications, and is a generalization of the well-studied
(unconstrained) fair division problem.
The two central notions of fairness, in the context of fair division of
indivisible goods, are envy freeness up to one good (EF1) and the (approximate)
maximin share guarantee (MMS). We show that the existence and algorithmic
guarantees established for these solution concepts in the unconstrained setting
can essentially be achieved under cardinality constraints. Specifically, we
develop efficient algorithms which compute EF1 and approximately MMS
allocations in the constrained setting.
Furthermore, focusing on the case wherein all the agents have the same
additive valuation, we establish that EF1 allocations exist and can be computed
efficiently even under laminar matroid constraints.

本论文主要研究如何在给定的特定限制条件下，实现资源公平配置问题，提出了一种有效的算法来计算两个中心公平概念，即 EF1 和 MMS，在满足限制条件的状态下，特别地，证明了在所有代理具有相同加性估值的情况下，即使存在限制条件，仍然可以有效地计算出 EF1 分配。

基数限制下的公平分配

Fair Division Under Cardinality Constraints

We study the problem of allocating a set of indivisible goods among a set of
agents in a fair and efficient manner. An allocation is said to be fair if it
is envy-free up to one good (EF1), which means that each agent prefers its own
bundle over the bundle of any other agent up to the removal of one good. In
addition, an allocation is deemed efficient if it satisfies Pareto optimality
(PO). While each of these well-studied properties is easy to achieve
separately, achieving them together is far from obvious. Recently, Caragiannis
et al. (2016) established the surprising result that when agents have additive
valuations for the goods, there always exists an allocation that simultaneously
satisfies these two seemingly incompatible properties. Specifically, they
showed that an allocation that maximizes the Nash social welfare (NSW)
objective is both EF1 and PO. However, the problem of maximizing NSW is
NP-hard. As a result, this approach does not provide an efficient algorithm for
finding a fair and efficient allocation.
In this paper, we bypass this barrier, and develop a pseudopolynomial time
algorithm for finding allocations that are EF1 and PO; in particular, when the
valuations are bounded, our algorithm finds such an allocation in polynomial
time. Furthermore, we establish a stronger existence result compared to
Caragiannis et al. (2016): For additive valuations, there always exists an
allocation that is EF1 and fractionally PO.
Another contribution of our work is to show that our algorithm provides a
polynomial-time 1.45-approximation to the NSW objective. This improves upon the
best known approximation ratio for this problem (namely, the 2-approximation
algorithm of Cole et al. (2017)). Unlike many of the existing approaches, our
algorithm is completely combinatorial.

研究分配一组不可分割商品给一组代理商的公平和高效问题，当代理商对商品具有可加性评估时，存在一种同时满足 EF1 和 PO 的最大 Nash 社会福利目标的分配，并提出了一个类似于假多项式时间算法的方法用于寻找 EF1 和 PO。