Ordinal Maximin Share Approximation for Goods (Extended Abstract)

There is a credible mirror, but it must be an extension with repeated goods, not a literal atomless population facing a fixed finite set of goods. My lead anchor is Theorem 2, proved in this paper: “There is an algorithm that computes a \(1\)-out-of-\(\lceil 3n/2\rceil\) MMS allocation in time polynomial in the length of the binary representation of the problem.”

A plausible regime is a large recurring allocation market: many households receive bundles assembled from a finite catalogue of repeated goods, such as standard housing, school-seat, food, or public-benefit packages. A type is a complete additive valuation vector over the catalogue: two households have the same type exactly when they value every good category identically. There are \(N\) units of population, but only \(\tau\) valuation types and \(r\) good categories, with \(N\gg \tau,r\). Category \(g\) has \(q_g=N\sigma_g\) indivisible copies, where \(\sigma_g\) is its per-capita supply. Thus the goods scale with the population; otherwise almost everyone would receive the empty bundle and MMS would become vacuous.

I would call the resulting problem Typed Repeated-Goods \(1.5\)-MMS\(_\infty\). Its input is a finite type set \(T\), rational type masses \(\mu_t\) with \(\sum_t\mu_t=1\), additive valuations \(v_t(g)\), a population scale \(N\), and an integer supply vector \(q\). Put \(d=\lceil 3N/2\rceil\). For type \(t\), define

\[ \theta_t=\max_{\mathcal P=(B_1,\ldots,B_d)} \min_{j\in[d]} v_t(B_j), \]

where \(\mathcal P\) ranges over partitions of the multiset containing \(q_g\) copies of each good \(g\), and \(v_t(B_j)\) is the additive value of bundle \(B_j\).

A solution is a finite-support rational allocation law \(y_{t,b}\), where \(b\in\mathbb Z_{\ge 0}^{r}\) is an indivisible bundle configuration and \(y_{t,b}\) is the fraction of the population of type \(t\) receiving that whole bundle. It must satisfy

\[ \sum_b y_{t,b}=\mu_t \]

for every type \(t\),

\[ \sum_{t,b}y_{t,b}b_g=\sigma_g \]

for every good category \(g\), and

\[ y_{t,b}>0\quad\Longrightarrow\quad v_t(b)\ge\theta_t. \]

The output is a compact list of the nonzero configurations and their masses, not a fractional bundle: a positive mass of type \(t\) receives copies of the complete indivisible bundle \(b\). A basic feasible solution would need only polynomially many supported configurations. On the rational clone subfamily, clearing denominators recovers an ordinary allocation of repeated agents and repeated goods.

This is recognisably the authors’ problem. It preserves the same MMS benchmark, the same \(\lceil3N/2\rceil\) relaxation, additive valuations, and an individual guarantee for every agent—not merely an average utility guarantee. The continuous object is the population census and the allocation mass, while goods and bundles remain indivisible. The authors’ bidirectional bag-filling construction is especially promising here: one can compute one threshold per valuation type, process repeated goods in runs, and assign type mass through a compressed configuration or flow formulation. I would expect this mirror to be Class A, provided the repeated-good representation admits a polynomial-time compressed version of their bag-filling routine. The relevant target would be a runtime polynomial in \(\tau\), \(r\), \(\log N\), and the valuation encoding length.

This is not a claim that Theorem 2 already proves that compressed result. The paper’s algorithm is polynomial in the explicitly listed agents and goods; extending it to binary-encoded multiplicities requires proving that its threshold computation and bag construction can be aggregated over types and repeated goods. That is precisely the computational question the mirror creates. It also avoids the paper’s separate NP-hardness warning about computing exact MMS values: as in Theorem 2, the algorithm may use a computable surrogate such as the bidirectional-bag-filling share while still proving that the resulting allocation meets the true MMS threshold.

The natural follow-up questions are whether the type-level bag-filling procedure is polynomial for arbitrary repeated-good supplies, whether the mass allocation can always be rounded to a finite clone allocation with only additive loss, and whether the large-market limit

\[ \theta_t^\infty(\sigma) = \liminf_{N\to\infty} \operatorname{MMS}^{1\text{-out-of-}\lceil3N/2\rceil}_t(N\sigma) \]

exists and has a compact optimization formulation. I would not use Theorem 3 as a second anchor: its \(15d^{2/3}\) term and the \(\ell>1\) benchmark require a separate population-scale dictionary.

The weakest point is unavoidable: scaling the goods and allowing \(y_{t,b}\) to be nonintegral changes the model beyond a literal replacement of named agents by masses. If the opponent insists on fixed goods, the limit degenerates; if they interpret \(y_{t,b}\) as fractional goods, the problem becomes ordinary divisible fair division; and if every good remains individually idiosyncratic, there is little type compression. But the repeated-catalogue regime is a sensible high-multiplicity instance regime, and the proposed problem preserves the paper’s distinctive object—an MMS guarantee for indivisible bundles. That is enough for a serious, though explicitly extension-level, continuous mirror of Theorem 2.