AI summaryⓘ
The authors study a fairness measure in dividing items called residual maximin share (RMMS), which ensures a fair share even as items are allocated and removed over time. They prove exact ratios comparing RMMS to the classical maximin share (MMS) for additive valuations, showing these ratios follow a specific pattern and approach 2/3 as the number of agents grows. They also describe smart ways to build examples that reach these exact limits using fewer items than previous methods. Additionally, they provide mathematical conditions that characterize when a share threshold is achievable in all situations. Their results clarify the precise limits of fairness guarantees for algorithms that allocate items fairly based on share values.
Residual maximin share (RMMS)Maximin share (MMS)Additive valuationsFair divisionDynamic allocationDensity-balance analysesCombinatorial structuresBipartite transportation graphPacking-covering conditionLone-divider algorithms
Abstract
Residual maximin share (RMMS) is the largest share threshold that remains guaranteeable throughout dynamic allocation processes, even after previously allocated, lower-valued bundles are removed from the item pool. For additive valuations, recent density-balance analyses established finite-agent lower bounds comparing RMMS with the classical maximin share (MMS). In this paper, we prove that these finite-agent lower bounds are exact. Specifically, if $d_n$ denotes the largest odd integer at most $n$, the worst-case ratio satisfies $\inf_{M,v:\operatorname{MMS}>0}\frac{\operatorname{RMMS}(M,v,n)}{\operatorname{MMS}(M,v,n)}=\frac{2d_n}{3d_n-1}$. Consequently, the exact additive frontier forms consecutive odd-even plateaus and converges monotonically to $2/3$. We then investigate the combinatorial structure of extremal instances. While naive witnesses require $Θ(n^2)$ items, we construct an explicit three-valued family achieving the exact boundary with only linear support: $(5n-3)/2$ items for odd $n$ and $(5n-4)/2$ items for even $n$. Its low-valued block supports two exact partitions that simultaneously certify the MMS benchmark and the residual obstruction. By modeling these dual partitions as a bipartite transportation graph, we prove that this block attains the absolute minimum support $q+d-1=3q$. At minimum support, any two-valued filler is uniquely rigid up to relabeling. Finally, we establish structural characterizations of RMMS. A general min--max representation applies to all finite monotone valuations. For integer additive valuations, we prove that a threshold $T$ is residual self-feasible if and only if every subset cut satisfies a packing-covering condition. Because RMMS is pointwise maximal among residual self-feasible shares, these exact constants establish a tight limitation on the fairness guarantees achievable by share-based lone-divider algorithms.