Residual Maximin Share: Exact Finite-Agent Frontier, Sparse Extremizers, and Threshold Cuts

• RMMS addresses dynamic allocation by requiring a threshold to remain feasible after any removed bundles valued below it; it is the supremum of such thresholds.Static MMS is the value guaranteed by partitioning all goods into n bundles and receiving the least favorable one.Source: §1 · p. 2
• The finite-agent additive lower bounds are exact, and the frontier has consecutive odd-even plateaus that converge monotonically to 2/3.For example, the exact ratio is 3/4 for n = 3, 4; 5/7 for n = 5, 6; and 7/10 for n = 7, 8.Source: §1 · p. 2, Figure 1 · p. 3
• The sparse three-valued extremal instance matches λn with linear support, making the Θ(n²)-item bi-valued construction unnecessary; for even n, it uses (5n − 4)/2 items.Source: §1 · p. 2
• The sparse instance's low-valued block has two exact partitions that certify the MMS benchmark and create the residual obstruction.After q obstruction bundles are removed, exceeding value d would require 2p high goods for p agents, but only 2p − 1 remain.Source: §1 · pp. 2–3
• A bipartite transportation graph proves the low-valued block's minimum support is q + d − 1 = 3q; at that support, any two-valued filler is unique up to relabeling.Coprimality forces the graph to be connected, and the construction meets the resulting edge bound.Source: §1 · p. 3
• RMMS has a finite min–max representation for finite monotone valuations and a threshold packing-covering characterization for integer additive valuations.The representation minimizes, over removal histories, the maximum of the costliest removed bundle and the residual MMS; the cut uses packing below T and covering bundles of value at least T.Source: §1 · p. 3
• Because RMMS is pointwise maximal among residual self-feasible shares, the exact frontier is an upper bound on MMS guarantees for share-based lone-divider algorithms.Source: §1 · p. 3

2 Preliminaries

• For additive valuations, the value of a bundle is the sum of the values of its goods.Source: §2 · p. 4
• A share threshold is residual self-feasible when, after any k disjoint bundles below it are removed, the remainder can be partitioned into n − k bundles meeting it.The definition applies to every instance and every integer 0 ≤ k < n.Source: §2 · p. 4
• RMMS is the supremum of all residual self-feasible thresholds for an instance.Source: §2 · p. 4

3 A Finite Min–Max Representation

• For every finite monotone valuation, RMMS has a finite min–max representation over collections of removed bundles.For a collection B, the representation’s inner quantity Φ(B) takes the maximum of the highest removed-bundle value and the residual MMS; when no bundles are removed, max ∅ = 0.Source: §3 · p. 4
• RMMS is at most MMS and at most the instance’s minimax share for every monotone valuation.Source: §3 · p. 4

4.1 The Density-Balance Lower Bound

• The density-balance lower-bound result is attributed to [1], with λn defined using the largest odd integer d at most n.Source: §4 · p. 4, §4.1 · p. 5

4.2 A Finite Bi-Valued Exact Witness

• The bi-valued exact witness has MMS = d + q and RMMS = d, but requires Θ(n^2) goods.Its goods comprise 2p − 1 high-value goods and qd unit goods.Source: §4.2 · p. 5

4.3 A Linear-Support Sparse Exact Witness

• RMMS / MMS = d/(d + q) = λn for the sparse witness, whose low-valued block supports both the MMS benchmark and the residual obstruction.The construction uses 2p − 1 high goods of value d, 2q goods of value q, and q unit goods.Source: §4.3 · p. 5
• λ2r+1 = λ2r+2 = (2r + 1)/(3r + 1), and the frontier decreases to 2/3.Source: §4.3 · p. 5
• The sparse construction achieves the exact frontier with Θ(n) items, compared with Θ(n^2) for uniform low-valued goods.Source: Figure 2 · p. 6

5 Minimum Support and Rigidity

• Any filler admitting partitions into d bundles of value q and q bundles of value d needs at least q + d − 1 items, or 3q when d = 2q + 1.The construction meets the bound with equality.Source: §5 · p. 6
• At minimum support 3q, any qualifying multiset with at most two positive values is uniquely isomorphic to 2q goods of value q and q goods of value 1.Source: §5 · p. 6
• Each row has two a-edges and one b-edge, so 2a + b = 2q + 1; a ≤ q/2 would imply b ≥ q + 1 > q, hence a = q and b = 1.Source: §5 · pp. 6–7
• If every good has the same value, support must be at least qd = Θ(n^2).Source: §5 · p. 7

6 Optimality among Residual Self-Feasible Shares

• The same supremum domination factor holds when the share is additionally required to be self-maximizing.The general result applies to classes of finite monotone valuations.Source: §6 · p. 7
• For additive valuations, RMMS λ_n-dominates MMS, and no residual self-feasible share can guarantee a larger factor.The exact additive frontier also limits share-based lone-divider guarantees to λ_n.Source: §6 · p. 7
• Among the listed valuation classes, the best MMS domination factors are 1 for unit-demand, λ_n for additive, and 1/n for submodular and subadditive valuations.The table compares the best factors among residual self-feasible shares.Source: §6 · p. 7
• For additive valuations, there exists a partial allocation that is EFX and λ_n-MMS, and a complete allocation that is EFL (hence EF1) and λ_n-MMS.These are simultaneous fairness guarantees.Source: §6 · p. 7

7 Threshold Packing-Covering Cuts

• For U ⊆ M, bp_T(U) is the fewest sub-T bundles partitioning U, while cov_T(R) is the most disjoint bundles in R worth at least T.These quantities define the packing and covering sides of the cut condition.Source: §7 · p. 7
• A threshold T is residual self-feasible exactly when every subset U satisfies bp_T(U) + cov_T(M \ U) ≥ n.The condition applies to integer additive instances and integer T > 0.Source: §7 · p. 7
• If a cut has packing and covering counts summing to at most n − 1, removing its sub-T bundles leaves too few threshold bundles to meet the residual requirement.Conversely, failure of residual self-feasibility yields such a cut.Source: §7 · p. 7

8 Related Work

• Prior work introduced MMS, established RMMS and its connection to lone-divider algorithms and simultaneous fairness [6] [1] [2], and analyzed MMS extensively [3].The cited work also includes simultaneous EFX/EFL and MMS guarantees.Source: §8 · p. 8
• This work establishes the exact finite-agent frontier λ_n, support minimality and rigidity, and structural cut characterizations.Source: §8 · p. 8

9 Conclusion

• For every finite n ≥ 2, the additive RMMS-to-MMS lower bound is exact: λ_n = 2d_n/(3d_n − 1), where d_n is the largest odd integer at most n.The frontier has consecutive odd-even plateaus and converges monotonically to 2/3.Source: §9 · p. 8
• An explicit three-valued extremal family uses (5n − 3)/2 items for odd n and (5n − 4)/2 for even n, improving on standard bi-valued constructions requiring Θ(n^2) items.Its dual partitions form a bipartite transportation graph; 3q items is the absolute minimum support, and the two-valued (q, q, 1) configuration is uniquely rigid.Source: §9 · p. 8
• RMMS is pointwise maximal and self-maximizing among residual self-feasible shares, making λ_n the exact upper bound for recursive fair-division algorithms certified by residual self-feasibility.Source: §9 · p. 8
• A finite min–max representation applies to general monotone valuations, while integer additive valuations admit an exact threshold packing-covering cut characterization.The cut condition is bp_T(U) + cov_T(M \ U) ≥ n.Source: §9 · p. 8
• Whether threshold cuts yield pseudo-polynomial or parameterized RMMS approximation algorithms, and whether alternative dynamic invariants bypass the share-based barrier, remain open directions.Source: §9 · p. 8

A Appendix A: Algebraic Identities for the Exact Ratio

• For n = 2r + 1 or n = 2r + 2, the exact ratio shares the plateau (2r + 1)/(3r + 1).Source: A Appendix A: Algebraic Identities for… · p. 9

B Appendix B: First Sparse Exact Witnesses

• Table 1 lists explicit parameters of the sparse exact witness for n ≤ 8.Source: Table 1 · p. 9, B Appendix B: First Sparse Exact… · p. 9