On MMS allocations with few items

Abstract

We consider the problem of allocating $m$ indivisible items to $n$ agents. For $n\ge 2$, we define $\mu (n)$ as the largest $m$ for which every allocation instance with $n$ agents and $m$ items has an allocation that gives each agent at least her maximin share (MMS). We prove that for general monotone valuations, $\mu (n)=n+\Theta (\log n)$. This holds both for goods and for chores. For arbitrary valuations (not monotone), we prove that $\mu (n)=\log n+O(1)$.