Ordinal Maximin Share Approximation for Goods

The strongest positive case is a high-multiplicity fair-division mirror, with Theorem 2 as the lead anchor. This is not a cake-cutting reformulation: goods remain indivisible for every individual agent. What becomes continuous is the population and the aggregate supply of repeated goods.

Take a finite catalogue \(G\) of \(m\) good types and a finite set \(T\) of complete valuation types, where type \(t\) has additive valuation \(v_t\). The society is a distribution \(\mu\in\Delta(T)\), with total population mass \(N\mu_t\) of type \(t\), where \(N\gg |T|=\tau\). Let \(q_g\) be the per-capita supply of good \(g\), so the aggregate inventory is \(Q_g=Nq_g\). Assume \(Q_g\) is integral; this is the ordinary high-multiplicity representation of many repeated copies.

An individual receives an integral bundle \(b\in\mathbb Z_{\ge0}^m\), while the continuum may split a type across different bundles. The allocation variable is \(x_{t,b}\ge0\), the mass of type \(t\) receiving bundle \(b\). Feasibility requires \(\sum_b x_{t,b}=N\mu_t\) for every \(t\), and \(\sum_{t,b}b_gx_{t,b}=Q_g\) for every good \(g\). Thus type-level averages can be fractional, but every unit of population mass receives an integral bundle.

For a type \(t\), define its high-multiplicity \(\ell\)-out-of-\(d\) MMS threshold by partitioning the aggregate inventory into integral bundles \(Q^1,\ldots,Q^d\) with \(\sum_jQ^j=Q\), and setting \(\operatorname{MMS}^{\ell,d}_t(Q)\) to the maximum, over such partitions, of the value of the \(\ell\) least-valued parts. A natural optimization objective is to maximize \(\eta\) such that every used bundle satisfies \(v_t(b)\ge \operatorname{MMS}^{\ell,d}_t(Q)+\eta\). The decision version asks whether \(\eta\ge0\) is attainable.

This is a genuine population continuization. A finite instance with \(n_t\) agents of each type is recovered by taking \(N=n\) and \(\mu_t=n_t/n\). The only compression is that indistinguishable agents are represented by mass rather than names. Scaling the item supply with \(N\) is forced by the continuum and preserves indivisibility at the individual level.

The regime is plausible in a large public or institutional allocation market: for example, a national programme distributing standardized aid, equipment, or educational bundles to millions of households, with perhaps dozens of complete preference types. The relevant types might encode household size, eligibility, and the full additive value vector. This is much stronger than claiming that every fair-division instance is high-multiplicity; the claim is that this repeated-catalogue regime is a sensible instance family for the paper’s problem.

The lead anchor is Theorem 2, proved in this paper. It states: for an additive-goods instance with \(n\) agents, there is an algorithm computing a \(1\)-out-of-\(\lceil 3n/2\rceil\) MMS allocation in time polynomial in the length of the binary representation of the instance. The proof avoids computing exact MMS values directly. It defines the bidirectional bag-filling share, proves in Lemma 4 that this share is at least the \(1\)-out-of-\(\lceil3n/2\rceil\) MMS value, proves in Lemma 5 that a BBFS-fair allocation always exists and can be found in polynomial time, and concludes Theorem 2.

The corresponding continuous problem is:

Continuous \(3/2\)-MMS Allocation. Given \((T,\mu,N,Q,(v_t)_{t\in T})\), let \(d=\lceil3N/2\rceil\) and \(\theta_t=\operatorname{MMS}^{1,d}_t(Q)\). Find a feasible mass allocation \(x_{t,b}\) such that \(x_{t,b}>0\) implies \(v_t(b)\ge\theta_t\) for every type \(t\).

The output is a sparse configuration list describing which mass of each type receives which integral bundle. The continuous computational question is whether this can be solved in time polynomial in \(m\), \(\tau\), the valuation and supply encoding length, and \(\log N\), rather than by expanding all \(N\) agents. This is the high-multiplicity analogue of Theorem 2, not a weaker average-utility problem: almost every individual in the population must receive an acceptable integral bundle.

I would expect this mirror to be tractable in the intended finite-type repeated-market regime, hence a Class A candidate. The paper already supplies the relevant structural idea: thresholds are type-specific, and the bidirectional bag-filling construction is based on repeated valuation patterns rather than on the names of agents. In the continuum, those repeated runs should be bulked into a configuration LP over bundle columns. The important unresolved part is the pricing problem over integral bundles. If that pricing problem is polynomial, the continuous theorem should follow by column generation; if arbitrary item types make pricing knapsack-hard, this mirror would expose a meaningful Class C boundary rather than collapse into a trivial fractional allocation.

A second useful anchor is Theorem 3, also proved in this paper. For every integer \(\ell\ge2\), with \(d=\lfloor(\ell+\tfrac12)n\rfloor\), the theorem gives an algorithm computing an allocation in which every agent receives value at least \(\operatorname{MMS}^{\ell,D}_i(M)\), where \(D=\lceil d+15d^{2/3}+\ell\rceil\), in time \(\tilde O(nm^4)\). The result is obtained through a bin-covering approximation, the Jansen–Solis-Oba algorithm, together with the paper’s comparison between \(1\)-out-of-\(d\) and \(\ell\)-out-of-\(d\) MMS.

Its continuous counterpart is:

Continuous \(\ell\)-MMS Bin-Covering Allocation. Given the same population, valuation types, and aggregate inventory, fix \(\ell\ge2\), let \(d=\lfloor(\ell+\tfrac12)N\rfloor\), \(D=\lceil d+15d^{2/3}+\ell\rceil\), and \(\theta_t=\operatorname{MMS}^{\ell,D}_t(Q)\). Find a feasible mass allocation \(x\) such that every used integral bundle for type \(t\) has value at least \(\theta_t\).

I would again expect a tractable high-multiplicity formulation, at least as an approximation problem. The \(15d^{2/3}\) additive term is sublinear in \(N\), so its per-capita effect vanishes as the repeated population grows. This raises a particularly natural follow-up: can the continuum permit the additive slack to be removed, yielding the exact \(\ell\)-out-of-\(\lfloor(\ell+\tfrac12)N\rfloor\) guarantee suggested by Theorem 1? The answer would distinguish genuine continuum power from merely bulk-applying the paper’s finite-instance algorithm.

The scope is deliberately limited. These mirrors cover the paper’s additive-goods algorithmic results, especially Theorems 2 and 3. They do not claim to continuize the responsive-valuation impossibility in Proposition 1, the chores setting, or the paper’s simulations. The paper contains no numbered NP-hardness theorem of its own; its statement that exact MMS computation is NP-hard appears in prose with external citations, so I would not present that as a formal anchor.

The weakest point is the dependence of the benchmark on the scale \(N\). A referee could object that a “true” continuum should have only \(\mu\) and per-capita supply \(q\), whereas \(d=\lceil3N/2\rceil\) still remembers a finite population scale. My answer is that high multiplicity is a regime, not merely a single limiting number: retaining \(N\) is what preserves the paper’s indivisible-bundle benchmark and prevents the model from degenerating into proportional cake division. The mirror is therefore best understood as a compact family of continuous-population instances, with \(N\) large and \(\tau\) small. That is a defensible continuous analogue of the authors’ problem, even if its exact complexity becomes the next question rather than an automatic corollary of Theorem 2.