| paper | Fair division with subjective divisibility |
| authors | Xiaohui Bei, Shengxin Liu, Xinhang Lu |
| venue | GEB 2025 |
| filed under | fairalloc · shares |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 4.7
statement extracted from the paper’s text layer
Given finite type set \(T\), good-class set \(G\), rational population distribution \(\mu\in\Delta(T)\), rational per-capita supplies \(q_g\), valuations \(v_t(g)\), and divisible-good sets \(D_t\), find a finite-support allocation \(x_{t,b}\) of type mass to bundles \(b\) satisfying \(\sum_b x_{t,b}=\mu_t\) and \(\sum_{t,b}x_{t,b}b_g=q_g\), with \(b_g\in[0,1]\) for \(g\in D_t\) and \(b_g\in\{0,1\}\) for \(g\notin D_t\). Require non-wastefulness and the paper's EF1M comparison for every pair of supported bundles, and find such an allocation in time polynomial in \(|T|\), \(|G|\), and the input bit length, independently of population denominators.
High-multiplicity subjective-divisibility fair division: type masses \(\mu\) are assigned to a distribution of integral or fractional bundles, with per-capita supplies \(q_g\); variables are type-bundle masses \(x_{t,b}\), constraints are mass and supply balance, and EF1M plus non-wastefulness hold ex post.
The proposed model must specify how replicated good classes, per-capita supply, copy capacities, and deletion of one good interact; Theorem 4.7 itself does not establish polynomial support compression for these choices.
fatal: False
It mirrors Theorem 4.7's polynomial-time EF1M and non-wasteful allocation guarantee, while leaving the MMS approximation results, EFM incompatibility, and Theorem 4.5's EFXM result outside the mirror.
The strongest honest case is a single anchor: Theorem 4.7, proved in this paper. It states:
For any number of agents, an EF1M and non-wasteful allocation always exists and can be found in polynomial time.
Here EF1M means that, for every pair of agents \(i,j\), either \(i\) does not envy \(j\), or \(j\)'s bundle contains a positively valued good that \(i\) regards as indivisible and removing one such good eliminates \(i\)'s envy. Non-wastefulness means that no agent receives a positive piece of a good from which she obtains zero utility. The theorem is proved here through the generalized round-robin construction for goods divisible for at most one agent, followed by equal splitting of goods divisible for at least two agents.
I would mirror Theorem 4.7 with the following problem, which I would call \( \mathrm{EF1M}\mbox{-}\mathrm{SD}_\infty \).
There is a finite set of good classes \(G\) and a finite set of agent types \(T\). A type \(t\) specifies the complete vector of values \(v_t(g)\) and the set \(D_t\subseteq G\) of goods it regards as divisible. The population is a distribution \(\mu\in\Delta(T)\). Good class \(g\) has per-capita supply \(q_g\), so the total supply scales with the population rather than remaining a fixed finite inventory.
An allocation assigns each type-mass slice \(\lambda_{t,k}\) to a bundle \(b^{t,k}\). For \(g\in D_t\), the coordinate \(b^{t,k}_g\) may be fractional; for \(g\notin D_t\), it must be either \(0\) or \(1\) in any non-wasteful allocation. The utility is
\[ u_t(b)=\sum_{g\in D_t}v_t(g)b_g+ \sum_{g\notin D_t}v_t(g)\mathbf 1[b_g=1]. \]
The mass and supply constraints are
\[ \sum_k \lambda_{t,k}=\mu_t \quad\text{and}\quad \sum_{t,k}\lambda_{t,k}b^{t,k}_g=q_g. \]
The allocation must be non-wasteful. It must also satisfy EF1M ex post: every bundle in the support of type \(t\) must satisfy the EF1M comparison with every bundle in the support of every type \(s\), using type \(t\)'s divisibility and utility. Thus this is not merely an average-utility relaxation. A solution is a finite-support, rational type-mass allocation, preferably with support polynomial in the description length.
The computational question is: given rational \(\mu\), \(q\), values, and divisibility patterns, find such an allocation in time polynomial in the number of types, good classes, and the encoding length of the masses—not in the common denominator representing the enormous underlying population. A natural optimization extension minimizes discarded supply if exact full allocation is infeasible.
This is a genuine population continuization. The goods remain physically discrete wherever a type regards them as indivisible. A fraction \(\lambda_{t,k}\) means that a fraction of the population receives a whole good, not that an indivisible good has been relaxed. Fractional \(b_g\) is allowed only where the original paper already allows that type to regard \(g\) as divisible.
The regime is plausible in a large university or computing platform: millions of course sections, student groups, or computational jobs, but only a few dozen recurring valuation/divisibility profiles. A lecture or examination type may need an entire time slot, while a flexible student group or batch workload can use a fraction of it. Good supplies—room slots or compute blocks—scale with the population. Here \(N\gg |T|\), and the type profile includes every feature relevant to the allocation problem.
The high-multiplicity bridge is exact for rational data. With a common denominator \(N\), \(\mu_t N\) becomes the number of agents of type \(t\), and \(q_gN\) becomes the number of copies of good class \(g\). Conversely, normalizing such a finite instance yields \((\mu,q)\). Thus the continuous problem is not an arbitrary fractional variant: it is the compressed, high-multiplicity form of the paper’s allocation problem.
I expect \( \mathrm{EF1M}\mbox{-}\mathrm{SD}_\infty \) to be Class A, although this is a new theorem rather than something already proved in the paper. The proof of Theorem 4.7 suggests the route. Equal allocation of goods with several positive-mass divisible recipient types can be performed directly at the mass level. The generalized round-robin part has a bounded-outdegree type graph, so identical agents and repeated goods may be processed in batches rather than individually, perhaps through a flow or configuration-LP formulation. The main unresolved issue is whether the supportwise EF1M constraints admit a polynomial-size compressed representation or a separation oracle.
This paper does not contain a numbered NP-hardness theorem of its own; its discussion of NP-hard MMS computation cites earlier work. I therefore would not manufacture a Class B anchor. The positive case rests on Theorem 4.7 and asks whether its polynomial finite-population algorithm has a genuinely high-multiplicity counterpart.
The weakest point is precisely the compressed-support issue. The paper proves polynomial time in the explicit number of agents and goods, whereas my mirror asks for complexity independent of huge multiplicities. If a fair allocation necessarily requires exponentially many distinct bundle types, the proposed problem could become continuum-specifically hard. That is a real vulnerability, but it is also a substantive continuization question rather than a cosmetic replacement of \(n\) by \(\mu\). Further natural questions are whether the EFM impossibility of Theorem 4.4 survives in this mass model, whether \( \mathrm{EFXM} \) admits a bounded-discard continuous analogue, and how accurately finite populations approximate the continuous allocation.
Theorem 4.7 is the strongest possible anchor, but I do not think its proposed mirror survives as a worthwhile continuous-population problem.
The natural limit of the paper keeps the \(m\) goods fixed while the number of agents grows. That limit collapses: only finitely many agents can receive indivisible goods, so almost the entire population receives nothing. EF1M does not prevent this degeneration, because an empty agent may eliminate envy toward a bundle by deleting its one indivisible good. Thus the continuum has no meaningful population-level fairness content; the mass of agents receiving useful allocations tends to zero.
The proposed repair—scaling each good into \(q_gN\) copies—is plausible in a room-booking or computing story, but it is not a harmless population continuization. It replaces each named good by a population-indexed supply of anonymous copies and requires new choices absent from the paper: whether an agent may receive several copies, whether copies have identical marginal value, and whether “remove one good” means removing one copy from a bundle or one unit of a class. Those choices define different allocation problems. The result is a capacitated assignment model inspired by subjective divisibility, rather than a continuous version of the paper’s finite-good problem.
There is also a deeper mismatch with EF1M. The theorem’s guarantee is ex post and pairwise: every agent must compare her own bundle with every other agent’s bundle. In the proposed model, changing \(\mu_t\) while keeping the same support of types does not change any of these comparisons. The distribution only affects how many copies of each bundle are required. A solution is therefore a mixture of finitely described bundle patterns subject to supply constraints; the population measure is bookkeeping, not the object on which fairness operates. Replacing those requirements by average or type-aggregate envy would make \(\mu\) central, but it would no longer mirror EF1M.
The support problem exposes the same issue. The generalized round-robin proof works because it orders named agents and processes individual goods. At the type level one must either reproduce that order through an artificial measurable ordering of identical agents, or solve a configuration problem over bundle types. In the first case, the continuum contributes no mathematical content. In the second, the substantive problem is the compatibility and support structure of bundles, while the population distribution merely supplies coefficients. A possible hardness result there could be interesting, but it would be a new capacitated configuration problem, not evidence that Theorem 4.7 has a natural continuous mirror.
This negative case is not airtight. A university with recurring agent types, recurring slots, and per-capita supply is a genuinely admissible high-multiplicity regime, and the exact rational dictionary to finite repeated instances is sound. If the authors explicitly want that replicated-resource model, a continuous formulation is defensible. But it is difficult to claim that no worthwhile mirror exists: Theorem 4.7 does provide one plausible computational anchor. The strongest honest conclusion is that the proposed mirror is substantially more artificial and less population-driven than the proponent suggests, not that it is impossible in every scenario.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.