| paper | On the Hardness of Fair Allocation under Ternary Valuations |
| authors | — |
| venue | AAMAS 2025 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 3.2
statement extracted from the paper’s text layer
For finite type and item-class sets \(T\) and \(Q\), rational type masses \(\mu_\theta\) with \(\sum_{\theta\in T}\mu_\theta=1\), rational per-capita supplies \(\rho_q\), and values \(v_\theta(q)\in\{0,1,2\}\), choose \(x_{\theta,B}\ge0\) for whole bundles \(B\subseteq Q\) such that \(\sum_{B\subseteq Q}x_{\theta,B}=\mu_\theta\) and \(\sum_{\theta\in T,\,B\ni q}x_{\theta,B}=\rho_q\); maximize \(\exp\left(\sum_{\theta\in T,\,B\subseteq Q}x_{\theta,B}\log u_\theta(B)\right)\), where \(u_\theta(B)=\sum_{q\in B}v_\theta(q)\), with any positive-mass zero-utility bundle yielding welfare \(0\).
A typed high-multiplicity market with agent masses \(\mu\), recurring indivisible item classes \(Q\) with per-capita supplies \(\rho\), configuration masses \(x_{\theta,B}\), and mass-weighted logarithmic utility for whole bundles.
For the original fixed item set \(O\), a nonatomic population leaves almost all agents with utility \(0\), and the proponent does not fully justify why scaling recurring item supplies alongside the population remains strictly population continuization.
fatal: False
The mirror covers the additive all-goods ternary MNW and MEW results, anchored by Theorems 3.2 and 3.9, while leaving mixed-manna and submodular results such as Theorem 4.7 outside scope.
The strongest honest case is a typed, repeated-item high-multiplicity mirror of the paper’s additive all-goods problem. My lead anchor is Theorem 3.2, proved in this paper: “When agents have \(\{0,1,2\}\)-valuations, computing an MNW allocation is APX-hard.”
The natural regime is a large course-seat or shift-allocation market. There are \(N\) students or workers, but only \(\tau\ll N\) complete agent types: for example, programme, campus, qualification, schedule, and preference profile. There is also a finite catalogue \(Q\) of recurring item classes, such as course sections or shift slots. Class \(q\) has many indistinguishable copies, and an agent may receive at most one copy of each class. Values are \(0,1,\) or \(2\), representing unavailable, useful, and especially valuable. The number of copies of class \(q\) scales with \(N\), rather than remaining fixed while the population grows.
This is a genuine high-multiplicity scenario. An agent type includes the complete valuation vector over \(Q\), as well as any eligibility or bundle constraints. Agents with different preferences for even one item class are different types. A plausible instance might have \(N=10^6\) students, \(\tau=10^2\) or \(10^3\) cohort types, and a few hundred recurring item classes.
Call the continuous problem \(\mathrm{Typed\text{-}Ternary\text{-}MNW}_\infty\). An instance consists of rational type masses \(\mu_\theta\), with \(\sum_{\theta\in T}\mu_\theta=1\), rational per-capita item supplies \(\rho_q\), and values \(v_\theta(q)\in\{0,1,2\}\). A bundle is a whole subset \(B\subseteq Q\), not a fractional bundle, with utility \(u_\theta(B)=\sum_{q\in B}v_\theta(q)\).
A solution is a nonnegative mass \(x_{\theta,B}\) of type-\(\theta\) agents receiving bundle \(B\), satisfying \(\sum_B x_{\theta,B}=\mu_\theta\) for every \(\theta\), and \(\sum_{\theta,B:q\in B}x_{\theta,B}=\rho_q\) for every item class \(q\). The objective is to maximize the per-capita Nash welfare \(\mathrm{NSW}_\infty(x)=\exp\!\left(\sum_{\theta,B}x_{\theta,B}\log u_\theta(B)\right)\), with zero-utility allocations treated in the usual way.
This is not averaging utilities and then taking a logarithm. It is the mass-weighted logarithm of the utilities of whole bundles. If all masses are rational and their denominators divide \(D\), clearing denominators produces \(D\mu_\theta\) cloned agents and \(D\rho_q\) indivisible item copies. The quantity above is then exactly the finite allocation’s geometric mean of utilities. Conversely, any allocation of such a cloned instance aggregates into an \(x\)-table. Thus rational instances have a precise two-way high-multiplicity dictionary.
The intended continuous change is therefore population multiplicity. Items remain indivisible at finite scale, and the continuum variable records how much agent mass receives each discrete bundle. A mass split \(x_{\theta,B}>0\) and \(x_{\theta,B'}>0\) means that different cloned agents of the same type receive different whole bundles; it does not mean that one agent receives a fractional item.
I expect this mirror to be Class A in the repeated-item regime, although the unrestricted boundary is an important open question. The configuration formulation has exponentially many bundle variables, but its pricing problem is unusually structured. The dual pricing problem for type \(\theta\) asks for a bundle maximizing an expression of the form \(\log(\sum_{q\in B}v_\theta(q))-\sum_{q\in B}\beta_q\). For \(\{0,1,2\}\)-values, one can enumerate the number of selected value-\(1\) and value-\(2\) items and choose the cheapest items in each class. This suggests a polynomial separation oracle and hence a column-generation LP. The exact bit complexity of comparing products of integer utilities needs to be written carefully, but that is a technical issue rather than a conceptual obstacle.
This would be an informative Class-A continuation of Theorem 3.2: the paper’s APX-hardness comes from the finely interlocked incidence pattern of individual agents and individual items. Repeated cohorts and repeated item classes remove that granularity while preserving the MNW objective, additive valuations, ternary values, and indivisible bundles. If a gap-preserving reduction survives type splitting, the unrestricted version could instead be Class B; determining whether that happens is itself a worthwhile question.
A second, closely related anchor is Theorem 3.9, proved by the authors here: “When agents have \(\{a,b,c\}\)-valuations with \(0\le a<b<c\), computing an MEW allocation is APX-hard.” Its continuous counterpart is \(\mathrm{Typed\text{-}Ternary\text{-}MEW}_\infty\), with exactly the same instance and feasibility constraints. It asks for the largest \(z\) for which there is a feasible \(x\) satisfying \(x_{\theta,B}=0\) whenever \(u_\theta(B)<z\). Equivalently, \(z\) is the essential minimum utility among the positive-mass agents. For the \(\{0,1,2\}\) case, threshold feasibility again has a configuration-LP form, and ternary pricing suggests a tractable continuous version. This companion is less central than the MNW mirror, but it shows that the construction is not tied to the logarithmic objective.
The mirror covers only the paper’s additive all-goods results, especially Theorem 3.2 and, secondarily, Theorem 3.9. It does not claim to continuize the arbitrary submodular valuations of Theorem 4.7. There, a type is a complete set function rather than a short valuation vector, and the representation and pricing issues are substantially less credible.
The weakest point is that the paper’s own hardness instances do not establish a many-clone regime: their agents and items are largely incidence-specific. The continuous model also requires repeated item classes and allows a type’s mass to split across bundles, so APX-hardness does not automatically transfer. If every item is unique, or every agent has idiosyncratic values, then \(\tau\) approaches \(N\) and the mirror loses its intended population compression. I would therefore present this as a strong, author-recognizable high-multiplicity extension with a plausible Class-A conjecture—not as a theorem that Theorem 3.2’s APX-hardness survives unchanged.
The key follow-up questions are whether ternary pricing is polynomial under richer repeated-item semantics, whether rational continuous optima admit controlled finite-clone rounding, and whether hardness persists when the number of item classes or agent types is allowed to grow.
The strongest negative argument is that neither anchor has a nondegenerate *population-only* limit while preserving indivisible items. In Theorem 3.2, if the item set remains fixed while the number of agents grows, at most \(|O|\) agents can receive any item. Once \(N>|O|\), some agent has utility \(0\) in every allocation, so max Nash welfare is identically \(0\). In a nonatomic limit, the finitely many indivisible items can reach only a measure-zero set of agents. Theorem 3.9 has the same defect: the essential minimum utility is \(0\).
The proposed repair—repeated item classes with supply \(\rho_q N\)—is mathematically coherent, but it is no longer merely a continuization of the population. It simultaneously takes a large-market limit of the items and changes the feasibility structure by replacing named goods with recurring classes and imposing class-level bundle restrictions. Theorem 3.2’s reduction is built from item-specific incidence: literal items, clause-specific special items, and agents whose valuation vectors encode particular clauses. With fixed recurring classes, that structure either disappears or must be reintroduced by making essentially every gadget its own class, forfeiting the claimed multiplicity regime. Allowing fractional items instead would move the problem into outcome-space continuity, which the programme explicitly excludes.
This objection applies equally to Theorem 3.9. A fixed finite item set makes continuous MEW trivial, while scaling item supplies yields a new two-sided high-multiplicity allocation market. The essential-infimum formulation is not itself objectionable, and the proponent is right that rational mass allocations have an exact cloned-instance interpretation. But that dictionary is for the repaired market, not for the paper’s original indivisible-item problem with only the population continuized.
Unfortunately, this does not defeat the proponent’s best case. Their course-seat or recurring-shift scenario is genuinely plausible, and the typed additive model is author-recognizable. The suggested pricing problem also appears to have real structure: for ternary values, one can enumerate the numbers of value-\(1\) and value-\(2\) items selected and choose the cheapest items in each category. The MEW threshold problem has a similar formulation. Thus the negative argument establishes a modelling discontinuity, not that the repaired mirror is worthless.
I therefore cannot honestly sustain the universal claim. The proposed mirrors of Theorems 3.2 and 3.9 survive once repeated resources are admitted. The negative case is weak precisely because fair allocation supplies a credible high-multiplicity regime; the paper is a substantially better candidate for continuization than the original instances’ gadget structure suggests.
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.