Complexity Results and Exact Algorithms for Fair Division of Indivisible Items: A Survey

The strongest positive case is a single, direct anchor: the MMF part of Theorem 2. The theorem is stated in this paper and its MMF case is proved in Section 5.2, using the integer-cone result of Goemans and Rothvoß (2014). It says that MMF is polynomial-time solvable when the numbers of agent types and item types are fixed. This is precisely the paper’s high-multiplicity regime, which is supporting evidence for a continuous mirror rather than a novelty collision.

I would call the mirror Continuous High-Multiplicity Max-Min Fair Allocation. An instance has agent types \(a\in[p]\), item types \(b\in[q]\), a rational population distribution \(\mu\in\mathbb{Q}_{\ge0}^p\) with \(\sum_a\mu_a=1\), a rational per-capita supply vector \(\rho\in\mathbb{Q}_{\ge0}^q\), and an integer valuation matrix \(v_{a,b}\). An agent of type \(a\) values a bundle \(z\in\mathbb{Z}_{\ge0}^q\) at \(v_a\cdot z=\sum_b v_{a,b}z_b\).

The decision variable is a finite-support family \(x_{a,z}\ge0\), where \(x_{a,z}\) is the mass of type-\(a\) agents receiving the integral bundle \(z\). It must satisfy \(\sum_z x_{a,z}=\mu_a\) for every \(a\), and \(\sum_{a,z}z_bx_{a,z}=\rho_b\) for every item type \(b\). Thus each individual receives an indivisible bundle; only the population is represented by mass. The problem asks for the largest \(T\) such that \(x_{a,z}>0\) implies \(v_a\cdot z\ge T\). A solution is \(T\) together with such an allocation plan.

This is not merely fractional fair division. If \(N\mu_a\), \(N\rho_b\), and \(Nx_{a,z}\) are integral, the plan is exactly a finite allocation of \(N\mu_a\) agents and \(N\rho_b\) indivisible items. Conversely, every finite high-multiplicity allocation induces such an \(x\). Rational plans can be scaled in this way. The continuous formulation is therefore the normalized aggregate form of the paper’s own high-multiplicity model.

A convincing scenario is national-scale allocation of standardized relief or public-service packages: millions of households, but only a small number \(p\) of need profiles and \(q\) standardized item types such as food, water, medicine, and heating units. Households sharing a profile have identical additive valuations, and item units of one type are interchangeable. Here \(N\) is enormous while \(p\) and \(q\) may be single digits. The authors should recognize this immediately, since their Section 2 defines exactly these agent and item types.

For fixed \(p\) and \(q\), I expect this problem to be in Class A. At a candidate threshold \(T\), each agent type may receive only integer configurations \(z\) satisfying \(v_a\cdot z\ge T\). The remaining task is to combine those configurations with the prescribed population and item multiplicities. That is the configuration/integer-cone structure used in the proof of Theorem 2: fixed dimension compresses the relevant bundle configurations, after which a small integer program handles their multiplicities. The expected result is an exact algorithm polynomial in the encoded rational data under the same high-multiplicity conventions as Theorem 2.

This mirror deliberately covers only the MMF assertion of Theorem 2. I am not claiming that the same formulation automatically settles the paper’s MNSW or EF results, and I would not use Theorem 1 or Theorem 4 as additional anchors: their parameters include the number of individual agents, so their algorithms do not directly establish a population-continuum result. The paper’s MMS statement may support a second mirror, but a faithful continuum definition of MMS requires taking care with the limiting notion of an indivisible partition, so I would not pad the case with it.

The natural follow-up questions are whether the exact equivalence with high-multiplicity allocations holds for every rational \(\mu\) and \(\rho\), whether one can obtain useful dependence on \(p+q\) rather than merely fixed-parameter polynomiality, and what happens when only one of \(p\) or \(q\) is fixed. One could also define continuous analogues of MNSW using a weighted geometric mean, or of MMS using a carefully specified high-multiplicity limit.

The weakest point is that this mirror is very close to an existing high-multiplicity result: the paper has already proved the fixed-type case. Also, the mass distribution \(x_{a,z}\) convexifies the aggregate allocation, so an opponent could argue that the continuous problem is easier because it permits fractional mixtures of whole bundles. The answer is that this is exactly the intended high-multiplicity relaxation: no individual receives a fractional item, and the theorem’s own type regime validates the scenario. The positive claim is therefore modest but strong: this paper supplies unusually good evidence that its MMF problem has a sensible continuous-population mirror, and that mirror is tractable for structural reasons rather than because the problem has been stripped of its fair-division content.