Asymptotic existence of fair divisions for groups

The strongest honest case is a narrow one led by Theorem 4. The paper contains no named NP-hardness result or classical complexity classification, so this is an algorithmic anchor rather than a hardness anchor.

Theorem 4, proved in this paper, says the following. Under [A2], every utility \(u_i(j)\in[0,1]\) is drawn independently from a distribution \(D_{i,j}\), with \(\mathbb{E}[u_i(j)]\ge \mu_{\min}>0\). For every \(\alpha\in[0,1)\), there is a constant \(C\), depending only on \(\alpha\) and \(\mu_{\min}\), such that if \(m>Cg\log n\), then the mechanism assigning every item independently and uniformly to one of the \(g\) groups produces an \(\alpha\)-approximately envy-free allocation with high probability. Here approximate envy-freeness means that every player \(i\) values her own group’s bundle at least \(\alpha\) times as much as every other group’s bundle. The paper obtains failure probability \(\exp(-\Omega(m/g))\). The mechanism is truthful because its outcome is independent of reported utilities.

My continuous problem is:

Continuous Truthful Approximate Group Envy-Freeness. An instance consists of \(g\) groups, \(m\) indivisible items, a parameter \(\alpha<1\), and a finitely supported continuous society \(\mu\) over complete types \(t=(k,v)\). The group label is \(k\in\{1,\ldots,g\}\), and \(v=(v_1,\ldots,v_m)\in[0,1]^m\) is the type’s additive valuation vector. The mass \(\mu_{k,v}\) is the fraction of the population having that group and valuation type; \(\tau\) is the number of positive-mass types. Assume every supported type satisfies \(\frac{1}{m}\sum_{j=1}^m v_j\ge \mu_{\min}\).

A feasible action is an integral assignment \(a:\{1,\ldots,m\}\to\{1,\ldots,g\}\): every item goes whole to one group. Let \(M_k(a)\) be group \(k\)’s bundle. The objective is to output a truthful randomized mechanism whose realized assignment satisfies

\[ \sum_{j\in M_k(a)}v_j \ge \alpha\sum_{j\in M_\ell(a)}v_j \]

for every positive-mass type \((k,v)\) and every group \(\ell\), with probability at least \(1-\varepsilon\). A natural solution is exactly the paper’s random-assignment mechanism: assign each item independently and uniformly to a group. It ignores reports, so it is universally truthful.

This is a genuine population continuization. The items remain indivisible, the group-level bundle comparison is unchanged, and the only replacement is that many indistinguishable players are represented by mass \(\mu_{k,v}\). For any large finite population \(N\), one can recover a discrete instance by taking \(N\mu_{k,v}\) copies of each type. The regime is a large organization or consortium with many members but relatively few recurring preference profiles: for example, departments containing large numbers of employees in standardized research or operational roles. Thus \(N\gg\tau\), while each positive-mass type may represent many agents.

The theorem’s proof transfers particularly cleanly at the type level. For a type \(v\), the utility assigned to any group has expectation \(\frac{1}{g}\sum_jv_j\). Chernoff bounds and a union bound over the \(\tau\) types give a sufficient condition of the form

\[ m\ge \frac{3g}{\mu_{\min}\delta_\alpha^2} \log\frac{2g\tau}{\varepsilon}, \qquad \delta_\alpha=\frac{1-\alpha}{1+\alpha}. \]

Thus the continuous mirror predicts a Class A result: the randomized mechanism is trivial to implement, and the required number of items depends on the number of distinct types \(\tau\), rather than on the potentially enormous number \(N\) of named agents. This is exactly the computational benefit expected from high multiplicity.

The original authors should recognize this as their problem rather than a softened substitute. It preserves their groups, additive valuations, indivisible items, group-level envy notion, approximate-fairness parameter, and truthful random-assignment mechanism. It does not replace the population by fractional goods or lotteries; randomization is already part of their Theorem 4. Existing multi-player fair-division work is therefore supporting evidence for the mirror’s plausibility, not a novelty collision: the paper still studies finite named players and does not formulate the type-mass mechanism problem.

I would not anchor on Theorem 1 in the same way. Its welfare advantage comes from finite-population fluctuations in group utility sums, and those fluctuations disappear in a literal continuum limit. Theorem 3 is likewise mainly a union bound over named players and discrete assignments. Theorem 4 is the cleanest result whose mechanism and concentration argument survive continuization.

The weak point is that this mirror covers approximate, not exact, envy-freeness, and it assumes an explicitly represented finite type support together with a uniform lower bound on total value. If the society has an uncountable support of genuinely distinct valuation vectors, or if one insists on \(\alpha=1\), the simple type-level concentration argument no longer suffices. That weakness leaves useful follow-up questions: whether deterministic assignments can replace randomization, whether exact envy-freeness is attainable, how to handle implicit or continuous type distributions, and whether welfare can be optimized subject to the same type-wise fairness guarantee.