2021/06/14 by Halvard Hummel, Hummel, Halvard, Magnus Lie Hetland +1
Decision Sciences · Economics, Econometrics and Finance · Social Sciences · #Auction Theory and Applications #Computer Science and Game Theory (cs.GT) #Data Structures and Algorithms (cs.DS) #Experimental Behavioral Economics Studies #FOS: Computer and information sciences #Game Theory and Voting Systems
paper · pdf · doi:10.48550/arxiv.2106.07300
openalex publication_date 2021/06/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 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 (√(n)/(2√(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.