The Fair Division of Hereditary Set Systems

The strongest honest positive case is a high-multiplicity mirror of the paper’s hereditary maximin-share problem. It is unusually credible because the paper’s own sharp upper-bound construction already has identical agents and item quantities proportional to the population size.

Let \(T\) be a finite set of agent types, with population masses \(\mu_t\) satisfying \(\sum_t\mu_t=1\). A type specifies the complete valuation vector and hence is exactly the paper’s notion of an agent for all purposes used by the problem. Let \(J\) be finitely many item classes, with per-capita supplies \(q_j\). A bundle remains integral: if \(b\) is a feasible bundle, an individual receives the whole bundle \(b\), never a fractional item. The hereditary constraint is represented by a downward-closed family of integral bundle patterns.

The decision variable is \(x_{t,b}\), the mass of type \(t\) receiving bundle \(b\). It must satisfy \(\sum_b x_{t,b}=\mu_t\) and \(\sum_{t,b}b_jx_{t,b}\le q_j\) for every item class \(j\). Thus \(x\) is fractional only at the aggregate level: it partitions each type’s mass into measurable groups receiving integral bundles.

For type \(t\), define its continuous maximin share \(M_t\) as the largest \(\lambda\) for which the per-capita item supply can be decomposed into total mass \(1\) of feasible bundles, every bundle used having value at least \(\lambda\). Equivalently, \(M_t\) is given by a configuration LP over bundle patterns. The continuous fair-division objective is to maximize \(\alpha\) subject to every positive-mass type receiving only bundles of value at least \(\alpha M_t\). This is stronger than merely requiring a type’s average value to meet the threshold, and therefore preserves the paper’s individual-agent guarantee.

The regime is a large course-registration, shift-assignment, or workforce-allocation market: \(N\) agents, \(N\to\infty\), but only \(\tau=|T|\) valuation and eligibility types. Item supplies scale with \(N\), so \(N\mu_t\) agents of type \(t\) and \(Nq_j\) copies of item class \(j\) form the corresponding finite instance. For rational data, clearing denominators gives an exact finite realization; conversely, every finite high-multiplicity instance yields such a mass distribution. This is population continuization, not outcome-space divisibility: each individual still receives an integral feasible bundle.

My lead anchor is Theorem 4.1, proved in the paper. It states that the performance guarantee of the paper’s greedy procedure is at most \(\frac{40}{107}=0.3738\). The proof uses \(n\) identical agents and six item classes \(A,\ldots,F\), with quantities per agent

\(q=(1,\frac13,\frac23,\frac23,\frac13,40)\),

values

\((\frac{40}{107},\frac{23}{107},\frac{17}{107},\frac{10}{107},\frac{4}{107},\frac{1}{107})\),

and hereditary capacities \((2,1,2,5,11,40)\). There is a maximin partition consisting of mass \(\frac23\) of bundles \(A,C,D,40F\) and mass \(\frac13\) of bundles \(A,B,E,40F\); every such bundle has value exactly \(1\), so the continuous MMS is \(1\).

At target \(\alpha=\frac{40}{107}+\varepsilon\), the greedy procedure can allocate mass \(\frac12\) to \(A^2\), mass \(\frac13\) to \(BC^2\), mass \(\frac{2}{15}\) to \(D^5\), and mass \(\frac1{33}\) to \(E^{11}\). These allocations consume all classes except \(F\), and their total allocated population mass is \(\frac{329}{330}\). The remaining \(F\)-only bundles have value exactly \(\frac{40}{107}\), so the final mass \(\frac1{330}\) cannot be allocated.

This gives the precise problem Continuous Greedy-HMMS Threshold:

Given \(T,\mu\), the hereditary bundle system, per-capita supplies \(q\), valuations \(v_t\), and a target \(\alpha\), run the mass version of the paper’s minimum-cardinality greedy procedure. The output is either a mass allocation \(x\) covering all of \(\mu\), or a positive residual population mass together with the remaining supplies. The associated optimization problem asks for the largest universal \(\alpha\) for which the procedure covers every admissible continuous instance.

The theorem’s construction is already an exact continuous witness: with one agent type and the normalized supplies above, every individual receives an integral bundle, but the aggregate procedure leaves mass \(\frac1{330}\) unserved. Thus any continuous theorem promising more than \(\frac{40}{107}\) for this greedy procedure is false. I expect this fixed-procedure problem to be Class A in the programme’s sense: its per-instance execution is mass bookkeeping and configuration selection, not continuum-specific hardness. The interesting unresolved question is the sharp worst-case constant between the paper’s lower and upper bounds.

The lower-side anchor is Theorem 3.1, also proved in the paper. It states that the procedure allocates every agent a bundle of value at least \(\alpha=\frac{4}{11}\) times that agent’s maximin share. Its continuous counterpart is Continuous Greedy-HMMS Allocation:

Given the typed mass society and item supplies above, output \(x_{t,b}\) satisfying the supply constraints and \(x_{t,b}=0\) whenever \(v_t(b)<\frac{4}{11}M_t\). The solution is the aggregate mass allocation itself, not a fractional bundle.

For rational masses, this guarantee follows directly by replication: clear denominators, apply Theorem 3.1 to the resulting finite high-multiplicity instance, and aggregate identical agents and bundles. For arbitrary masses, one can ask for a limiting argument or a direct mass-flow proof. I expect this mirror to be Class A under a finite-type, valuation-oracle representation. The main technical work is to express the paper’s phase and auxiliary-graph accounting for bundle masses rather than named agents.

The implementation anchor is Theorem 5.3, proved in the paper. It states that for every \(\delta>0\), there is a \((1-\delta)\frac{4}{11}\)-approximation algorithm for the maximin-share problem on hereditary set families. Section 5 explains that the algorithm uses valuation queries, estimates each MMS value by multiplicative search, handles bundles of size at most three explicitly, and handles larger bundles through the MinimalSet procedure.

Its continuous version is Continuous HMMS Approximation:

Given \(T,\mu,q\), the hereditary bundle system, valuations, and \(\delta>0\), output a feasible mass allocation \(x\) such that every type \(t\) receives only bundles of value at least \((1-\delta)\frac{4}{11}M_t\). The expected algorithm should operate on types and bundle masses rather than on the \(N\) individual agents. For fixed \(\delta\), bounded item-class structure, and the same oracle model, I expect this to remain Class A. If the hereditary system is given only by a highly succinct representation, the configuration pricing problem may itself be hard; that is a representation issue worth studying, not a reason to reject the mirror.

The paper contains no named NP-hardness, coNP-hardness, parameterized-hardness, or counting-hardness theorem. I therefore would not sell this as a case where discrete hardness dissolves. Its positive value is different: the paper supplies a genuine high-multiplicity regime, an exact continuous formulation, a mass version of the greedy algorithm, a concrete continuum witness at \(\frac{40}{107}\), and an algorithmic approximation target at \((1-\delta)\frac{4}{11}\).

The weakest point is that the mirror must scale the inventory with the population. If a referee insists on a fixed finite set of unique items while making the agent population atomless, the MMS benchmark ceases to be the paper’s object. The defence is that this scaling is not an ad hoc relaxation: the paper’s own Theorem 4.1 already uses identical agents, repeated item classes, and quantities linear in \(n\). The continuous model simply makes that high-multiplicity structure explicit.

The natural follow-up questions are whether the continuous greedy guarantee can close the gap \(\frac{4}{11}\le\alpha\le\frac{40}{107}\), whether exact continuous MMS admits a configuration-LP or pricing algorithm for partition matroids, and whether succinct hereditary representations can make the continuous problem genuinely hard.