Guaranteeing Half-Maximin Shares Under Cardinality Constraints

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 measure known as the maximin share (MMS) guarantee, and propose a novel polynomial-time algorithm for finding 1/2-approximate MMS allocations---an improvement from the previously best available guarantee of 11/30.