Improved Maximin Share Approximations for Chores by Bin Packing

The strongest honest case is a narrow but credible high-multiplicity mirror of the paper’s fair-division problem. It is not “a continuum of agents sharing a fixed finite pile of chores”: that would make almost everyone receive nothing. The sensible regime has many clone-like agents and a proportionally recurring supply of indivisible chore types.

My lead anchor is Theorem 3, proved in this paper:

“In chore allocation with factored cost functions, HFFD with the thresholds of all agents equal to their maximin share always allocates all chores.”

The paper derives this from its Corollary 1 and the factored-size FFD theorem cited as Theorem 2 of Coffman, Garey, and Johnson (1987). I am not using that cited Theorem 2 as an anchor.

Call the mirror Factored High-Multiplicity MMS Allocation\(_\infty\). An instance contains:

• finitely many complete agent types \(t\in T\), with rational masses \(\mu_t\ge 0\), \(\sum_t\mu_t=1\);
• finitely many recurring chore classes \(j\in[r]\), with rational per-capita supplies \(q_j\);
• rational costs \(v_t(j)>0\), where a type-\(t\) agent receiving bundle \(b\in\mathbb Z_{\ge0}^r\) pays

\[ v_t(b)=\sum_j v_t(j)b_j. \]

A chore class is complete: two chores in the same class are indistinguishable to every agent type. For the lead problem, each type’s distinct costs form the paper’s divisibility chain: every smaller value divides the next larger value by an integer factor. The universal ordering assumption from the paper can also be retained.

The decision variable is a finite-support rational distribution \(x_{t,b}\). It is the mass of type-\(t\) agents receiving the integral bundle \(b\). It must satisfy

\[ \sum_b x_{t,b}=\mu_t\quad\text{for every }t, \]

and

\[ \sum_{t,b} b_jx_{t,b}=q_j\quad\text{for every chore class }j. \]

Thus the individual outcome remains an indivisible bundle. We are not allowing one agent to receive half a chore. We are only recording what fraction of a large clone population receives each possible integral bundle.

For each type \(t\), define its high-multiplicity MMS threshold \(\theta_t\) as the minimum \(\theta\) for which there are nonnegative bundle frequencies \(y_b\) with

\[ \sum_b y_b=1,\qquad \sum_b b_jy_b=q_j, \]

and every bundle in the support of \(y\) has \(v_t(b)\le\theta\). This is the configuration version of partitioning the entire chore inventory into one bundle per unit of population. The continuous problem asks for an \(x\) satisfying the supply constraints and

\[ x_{t,b}>0\implies v_t(b)\le \theta_t. \]

Equivalently, one can minimize the maximum MMS ratio

\[ \alpha(x)=\max_{t,b:x_{t,b}>0}\frac{v_t(b)}{\theta_t} \]

and ask whether \(\alpha(x)\le1\).

This is a genuine high-multiplicity model. If all masses and supplies are rational, clearing denominators produces a finite instance with \(N\mu_t\) agents of type \(t\) and \(Nq_j\) chores of class \(j\). Conversely, every finite repeated instance gives such a rational mass allocation. The regime I have in mind is a large organization, municipality, hospital network, or residential system assigning recurring unpleasant tasks to millions of people, with perhaps tens of agent profiles and tens of chore classes. Factored costs can represent workload units or hierarchical difficulty levels. Personalized costs are still preserved inside the type definition.

I expect Factored High-Multiplicity MMS Allocation\(_\infty\) to be Class A. The configuration formulation is linear, and the paper’s central structural ingredient—divisible item sizes plus the FFD exchange property—looks precisely like the kind of structure that should make pricing or separation manageable. A compressed HFFD/MultiFit algorithm would need to operate on chore multiplicities rather than enumerate every clone. The natural target is polynomial time in \(\tau=|T|\), the number \(r\) of chore classes, and the rational encoding length, independent of the expanded population \(N\).

The required theorem is not automatic: running HFFD on the denominator-expanded instance could be only pseudo-polynomial. The continuous result would have to prove bit-polynomial batching or give a configuration-LP separation algorithm. That is a worthwhile ChoCo question rather than a defect in the mirror.

The secondary anchor is Theorem 4, asserted in this paper and supported by the detailed case analysis in the authors’ full version:

“For personalized bivalued instances of chores, the HFFD algorithm achieves a tight approximation ratio of \(15/13\) for MMS.”

Its mirror is Personalized-Bivalued \(15/13\)-MMS Allocation\(_\infty\). The instance and allocation variables are exactly as above, except that for every agent type \(t\),

\[ v_t(j)\in\{a_t,b_t\}, \]

where \(a_t\) and \(b_t\) may differ across types. The question is to output a rational finite-support allocation \(x\) satisfying the supply constraints and

\[ x_{t,b}>0\implies v_t(b)\le \frac{15}{13}\theta_t. \]

The expected classification is again Class A, probably via a configuration or flow formulation in which a bundle is summarized by its number of large and small chores. The paper’s swapping proof should become a type-level exchange argument. In many high-multiplicity instances the continuous problem may actually admit an exact MMS allocation, so \(15/13\) need not remain tight for the relaxed problem. That does not invalidate the mirror: it is the continuous counterpart of the paper’s guaranteed approximation task, while the paper’s finite lower-bound example records an obstruction that may disappear when recurring supplies become abundant.

The authors would recognise both formulations as their problem: same additive costs, same MMS benchmark, same HFFD/bin-packing structure, same indivisible bundles, and the same special cost classes. The change is the instance regime—rational masses of complete types and recurring supplies—rather than a replacement of fair division by fractional utility or lotteries.

The mirror covers the paper’s exact factored-cost result and its personalized-bivalued \(15/13\) approximation result. I would not claim that it automatically covers the general \(1\)-out-of-\(\lfloor9n/11\rfloor\)-MMS theorem; the floor, finite-bin effects, and compressed implementation would require a separate ordinal formulation.

The weakest point is that this is an extension involving joint population-and-supply scaling. If “continuization” is interpreted so strictly that chores must remain a fixed finite set while only the number of agents grows, then the model degenerates and no honest fair-division mirror exists. But for indivisible allocation, per-capita supply is unavoidable: it is the only way to obtain a meaningful large population without turning fairness into an empty-bundle statement. The rational-clone correspondence and support-wise integral bundles keep the model recognisably about the paper’s question rather than silently changing it into divisible fair division.

The main follow-up questions are whether the configuration LP has a polynomial-time pricing oracle for factored costs, whether binary-encoded supplies create continuum-specific hardness, whether the \(15/13\) bound improves to \(1\) in the atomless limit, and whether hardness returns when the number of chore classes or cost levels is unrestricted.