1/2 - Approximate MMS Allocation for Separable Piecewise Linear Concave

The strongest positive case is a mirror of the paper’s central result, Theorem 4.2:

“There exists an algorithm which in polynomial time outputs an allocation that gives \(1/2\)-MMS to each agent.”

This is proved by the authors, with proof details deferred to their full version; it is not merely cited prior work.

Consider a large public allocation programme: millions of applicants receive bundles of repeated indivisible goods such as course seats, housing units, or aid items. Applicants fall into a small number \(\Theta\) of complete preference types. A type \(\theta\) includes its entire SPLC valuation schedule, so agents of the same type have identical marginal values for every good copy. Let \(\mu_\theta\) be the fraction of applicants of type \(\theta\), with \(\sum_\theta\mu_\theta=1\). There are \(t\) good types, with \(\sigma_j\) copies of good \(j\) per unit population. The intended regime is \(n\gg|\Theta|,t\): millions of agents, but perhaps dozens of valuation cohorts.

This is not a fractional-goods interpretation. Each individual still receives an integral bundle. Continuity enters through the mass of agents assigned each integral bundle. If \(B\in\mathbb Z_+^t\) is a bundle, then

\[ v_\theta(B)=\sum_{j=1}^t\sum_{r=1}^{B_j}a_{\theta,j,r}, \]

where the marginal values \(a_{\theta,j,r}\) are nonincreasing in \(r\).

To define the fair-share benchmark, let \(\operatorname{MMS}^{\infty}_\theta(\sigma)\) be the large-market MMS value:

\[ \operatorname{MMS}^{\infty}_\theta(\sigma) = \sup\left\{ z: \begin{array}{l} \text{there is a distribution }\lambda\text{ over integral bundles }B,\\ \mathbb E_\lambda[B_j]=\sigma_j\text{ for every }j,\\ v_\theta(B)\ge z\text{ for }\lambda\text{-almost every }B \end{array} \right\}. \]

This is the limit of the ordinary MMS definition. A distribution \(\lambda\) is simply a partition of an atomless cohort into subcohorts receiving different integral bundles; no individual receives a lottery or a fraction of a good.

The continuous problem, which I would call Continuous SPLC \(1/2\)-MMS Allocation, is:

Given \((\Theta,\mu,\sigma)\) and the SPLC valuation schedules, find masses \(y_{\theta,B}\ge0\), where \(y_{\theta,B}\) is the mass of type-\(\theta\) agents receiving bundle \(B\), satisfying

\[ \sum_B y_{\theta,B}=\mu_\theta \]

for every \(\theta\), and

\[ \sum_{\theta,B} y_{\theta,B}B_j=\sigma_j \]

for every good type \(j\), such that

\[ y_{\theta,B}>0 \quad\Longrightarrow\quad v_\theta(B)\ge \frac12\operatorname{MMS}^{\infty}_\theta(\sigma). \]

The optimization version maximizes the common factor \(\alpha\); the anchored decision version asks whether \(\alpha=1/2\) is attainable.

This is a genuine high-multiplicity mirror of Theorem 4.2. If \(\mu,\sigma\), and \(y\) are rational, multiplying by a common denominator produces a finite instance with \(N\mu_\theta\) agents of each type and \(N\sigma_j\) indivisible copies of each good type. Conversely, empirical distributions of allocations in such finite instances converge to \(y\). Thus the model is not replacing indivisible allocation by divisible allocation; it is forgetting the names of repeated agents and normalizing their counts.

I expect this problem to be Class A, at least under a compact piecewise-linear encoding of the marginal schedules. The paper already supplies the likely ingredients: the linear relaxation in (5), the one-good-loss rounding theorem in Lemma 4.2, cycle cancellation in Lemma 4.3, and the computable upper bounds used in Theorem 4.2 instead of exact MMS values. In the continuum, the individual-agent loop should become a bulk operation on masses of identical types. The aggregate allocation is naturally a configuration LP over integral bundles, while separability should make its pricing problem manageable. The target complexity would be polynomial in the number of valuation types, good types, marginal segments, and encoding length—not in the expanded number of agents or copies.

The main questions are whether the finite rounding argument can be aggregated without losing its one-good guarantee, whether \(\operatorname{MMS}^{\infty}_\theta\) can be computed or tightly bounded in that representation, and whether a continuum algorithm yields additive-error guarantees for large but finite instances. It is also worth asking whether the \(1/2\) factor improves in the limit, or whether the paper’s barrier persists.

The weakest point is that the finite theorem is already polynomial-time, so the mirror risks looking like a compressed restatement rather than a qualitatively new algorithmic phenomenon. More seriously, a literal atomless population with a fixed finite set of goods would be nonsensical: almost everyone would receive nothing. The proposed mirror therefore relies on a large-market regime in which goods scale with population and allocations are represented by masses of agents receiving integral bundles. I regard that as the natural high-multiplicity interpretation of this paper, but it is the modelling choice a sceptical referee would challenge first.

I would deliberately scope the positive case to Theorem 4.2. It is the paper’s clearest named computational result, and the SPLC structure gives a credible route to a continuous algorithm. The more general submodular APS result, Theorem 5.1, would require a less canonical representation of repeated goods and valuation types, so it is better left outside this mirror than used as a weaker second anchor.