Improved Maximin Guarantees for Subadditive and Fractionally Subadditive Fair Allocation Problem

Theorem 4 is a named approximation/existence result, but it does not assert a computational result about solving a problem. The HM-XOS-MMS formulation is a coherent high-multiplicity extension that the authors would likely recognise, yet its optimization and pricing questions are new. Under the required computational-anchor gate, the paper therefore grades red.

The objection that survived

Theorem 4 only proves existence for finite instances, so the proposed mass optimization and its pricing problem are not computational results supplied by this paper.

What the mirror covers

The proposed mirror covers the fractionally subadditive MMS guarantee in Theorem 4; it leaves Theorem 1, the supporting probabilistic lemmas, and the configuration-LP implementation without a named computational mirror.

Open questions for a prover

The case FOR (proponent)

The strongest honest case is a narrow, provisional mirror anchored on Theorem 4, proved in this paper: “For any instance of the fair allocation problem with fractionally subadditive agents a \(0.219225\)-MMS allocation always exists.” Theorem 4 is an existence/approximation theorem, not a named \(P\), NP-hardness, or parameterized-complexity result. The paper contains no such qualifying complexity classification. Thus this is a positive mirror of the paper’s central allocation guarantee, not evidence that the paper already contributes to ChoCo’s complexity map.

Call the mirror \(\mathrm{HM\text{-}XOS\text{-}MMS}\). An instance contains a finite catalogue \(B\) of indivisible goods or good slots, a finite set of valuation types \(\Theta\), a rational population distribution \(\mu\in\Delta_\Theta\), and rational per-capita supplies \(q_b\) for \(b\in B\). A type \(\theta\) is a complete XOS valuation

\[ U_\theta(S)=\max_{\ell\in L_\theta}\sum_{b\in S}v_{\theta,\ell,b}. \]

The mass \(\mu_\theta\) is the fraction of the population having exactly this valuation. In an \(N\)-agent realization, there are \(N\mu_\theta\) agents of type \(\theta\) and \(Nq_b\) indivisible copies of good \(b\). Hence \(N\gg |\Theta|\) is the intended regime.

Define the high-multiplicity MMS benchmark of type \(\theta\) by

\[ r_\theta=\max\left\{r: \begin{array}{l} p_{\theta,S}\ge 0,\quad \sum_Sp_{\theta,S}=1,\\ \sum_{S\ni b}p_{\theta,S}\le q_b\quad\forall b,\\ p_{\theta,S}>0\Rightarrow U_\theta(S)\ge r \end{array} \right\}. \]

Here \(p_{\theta,S}\) is a distribution over whole indivisible bundles. It is the limiting empirical distribution of bundles in an MMS partition, not a fractional bundle assigned to one person.

A solution is a mass allocation \(x_{\theta,S}\ge0\) satisfying

\[ \sum_Sx_{\theta,S}=\mu_\theta\quad\forall\theta, \qquad \sum_{\theta,S\ni b}x_{\theta,S}\le q_b\quad\forall b. \]

It is an \(\alpha\)-MMS solution if

\[ x_{\theta,S}>0\Rightarrow U_\theta(S)\ge \alpha r_\theta \]

for every type \(\theta\). The problem asks for the largest achievable \(\alpha\), together with the mass allocation \(x\). Each individual still receives one indivisible bundle; only the population assignment is continuous.

This is recognizable to the authors as their problem. The valuation class is unchanged, the MMS benchmark is unchanged after high-multiplicity normalization, and the fairness predicate is still bundle-by-bundle. The natural regime is large course-allocation, residency, or public-service cohorts in which many agents share one of a small number of complete XOS valuation templates. Clearing denominators in \(\mu\) and \(q\) recovers a finite replicated instance, while empirical bundle frequencies produce \(x\) in the other direction.

The expected target is that the \(0.219225\) guarantee of Theorem 4 survives this rational-clone limit. The proof route suggested by the paper is the bounded-welfare configuration program with \(t=0.438447\),

\[ \max_x\sum_{\theta,S}x_{\theta,S}\min\{U_\theta(S),t\}. \]

With an explicit finite bundle catalogue, the mirror is plainly Class A: it is a finite LP. With the natural implicit catalogue \(2^B\), it becomes the interesting configuration-LP question. I would expect the exact unrestricted version to sit near the Class-C boundary: its pricing problem may require finding a cheapest bundle satisfying \(U_\theta(S)\ge \alpha r_\theta\), which can resemble knapsack-cover even for additive valuations. A polynomial pricing theorem would yield a Class-A result; hardness would be genuinely continuum-specific because this paper supplies no discrete hardness anchor.

The main unresolved questions are whether the \(0.219225\) guarantee transfers without a limit-rounding loss, whether \(r_\theta\) is efficiently computable from an XOS representation, and whether the implicit configuration pricing problem is polynomial or hard. The paper’s Theorem 1 is a weaker secondary possibility, but I would not use it as an anchor: its \(\Omega(1/(\log n\log\log n))\) guarantee depends on finite \(n\) and tends to zero in a literal continuum.

My weakest point is substantial: the paper never studies repeated valuation types, population measures, replicated goods, or computation of the resulting mass problem. The supply scaling and the definition of \(r_\theta\) are a genuine extension, not a theorem already present in the paper. If one insists on a strict computational-anchor gate, the correct verdict is that the paper does not qualify. The positive case survives only as an author-recognizable, technically precise high-multiplicity research problem whose constant-factor fairness guarantee is a credible target for continuization.

The case AGAINST (opponent, writing after the proponent)

The decisive objection is that this paper has no qualifying computational anchor. Its numbered results are existence and approximation guarantees: the \(0.219225\)-MMS theorem, the \(\Omega(1/(\log n\log\log n))\)-MMS theorem, and the supporting lemmas. Algorithms 1 and 2 have no complexity theorem, input model, runtime bound, or parameterized classification. The discussion that a configuration LP is solvable under demand queries concerns a proof relaxation, not the computational complexity of finding an MMS allocation. Under ChoCo’s stated gate, there is therefore no paper result whose complexity landscape can be continuized.

The strongest proposed repair, HM-XOS-MMS, is nevertheless a coherent high-multiplicity allocation model. It has plausible repeated types, no identity-dependent objective, and no collision with analytic continuous fair division. Those are not valid objections. The problem is what it contributes as a mirror of this paper.

For any fixed symmetric lift of goods to \(N\) copies, the existence part of the mirror is essentially automatic. Take \(N\mu_\theta\) clones of each type and \(Nq_b\) copies of each good. Apply the paper’s \(0.219225\)-MMS theorem to every finite replicated instance. Since there are finitely many bundle patterns, normalized allocation frequencies have a convergent subsequence; its limit is an \(x_{\theta,S}\) satisfying the proposed mass constraints. Conversely, rational \(x\) can be realized by clearing denominators. Thus “does the constant guarantee survive?” is not an open continuization question: it follows mechanically from the finite theorem once the replication model is fixed.

If one instead asks for the largest achievable \(\alpha\), or for an efficient algorithm constructing \(x\), that may be a worthwhile new configuration-LP problem. But it is no longer a computational result mirrored from the paper. The paper neither defines that optimization problem nor studies its representation, complexity, or pricing oracle. With an explicit bundle catalogue, the LP is finite but potentially exponential in \(|B|\); with the implicit catalogue \(2^B\), the pricing problem is a new knapsack-cover-style question. The proponent’s “Class A or Class C” claim is therefore a research proposal, not a consequence of this paper. Its difficult part remains even when \(\mu\) has one type, so the population continuum is not what the paper’s theorem is computationally about.

There is also no canonical nondegenerate limit without that extra modelling choice. Keeping the original finite ground set while \(N\) grows makes the usual MMS benchmark collapse: with \(U(\varnothing)=0\), at least \(N-|M|\) bundles are empty, so \(\operatorname{MMS}\) tends to zero. Scaling supplies by \(N\) avoids this, but then one must define a new family of valuations on repeated copies—additive copies, substitute copies, or slot-specific copies—which produce different limiting benchmarks \(r_\theta\). That is a sensible extension, but it is not supplied by the paper.

The subadditive theorem is weaker still as an anchor: under literal replication its \(\Omega(1/(\log N\log\log N))\) guarantee tends to zero. A nonvanishing bound indexed by the number of valuation types would be a new theorem, not a continuization of Theorem 1.

So the negative case is strong at the programme’s eligibility test: this is a fair-allocation paper with no named computational complexity result. The honest weakness is that HM-XOS-MMS itself is well-posed and could be valuable. What it establishes is a new high-multiplicity fair-allocation programme, not that this particular paper supplies a worthwhile continuous computational mirror.

The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.