| paper | d4-conf-aaai-2026-3600 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→P discrete result → its continuous mirror
Answer: Polynomial-time solvable. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 4.4
statement extracted from the paper’s text layer
Given a finite category set \(A\), supported types \(T\) with \(t=(S_{t1},S_{t2},S_{t3})\), rational masses \(\mu_t\ge 0\) summing to \(1\), and rational per-household supplies \(q_a\in[0,1]\), decide whether nonnegative masses \(x_{tB}\) exist for \(t\in T\) and \(B\subseteq A\) such that \(\sum_{B\subseteq A}x_{tB}=\mu_t\) for every \(t\), \(\sum_{t\in T}\sum_{B\ni a}x_{tB}=q_a\) for every \(a\), and every \(B\) with \(x_{tB}>0\) satisfies binary PROP1 for all three members of \(t\). Specifically, with \(p_{ti}=\sum_{a\in A}q_a\mathbf{1}[a\in S_{ti}]\), require \(|B\cap S_{ti}|+\max(\{0\}\cup\{1:a\in S_{ti}\setminus B,\ q_a>0\})\ge p_{ti}\) for each \(i\in\{1,2,3\}\).
A continuum of three-person household types \(t\), each with mass \(\mu_t\), receives integral category bundles \(B\subseteq A\); \(x_{tB}\) is the mass assigned bundle \(B\), and \(q_a\) is the per-household supply of category \(a\). Ask whether supply balance and per-household binary PROP1 can both be satisfied.
The paper’s one-off goods setting does not itself establish that categories are replicable across households while each household is limited to one copy, so the mirror’s practical fit still depends on accepting the standardized-benefit scenario.
fatal: False
It mirrors the binary PROP1 allocation-existence and decision component of Theorem 4.4; it leaves the EF1 decision result and the paper’s other results outside the proposed question.
Theorem 4.4 is the anchor I’d use. It is proved in this paper: for groups of three, PROP1 allocations can fail to exist even when utilities are binary and all groups are identical; and deciding whether a PROP1 allocation exists—or whether an EF1 allocation exists—is NP-complete, even with binary utilities. The paper’s hardness proof reduces from 3-Dimensional Matching. I’d lead with the PROP1 part of that result.
A plausible high-multiplicity setting is a large program that allocates standardized, indivisible benefit categories to three-person households. Each member approves some categories, the household receives one bundle that all three share, and many households have the same triple of approval sets. Let \(A=[m]\) be the categories, \(T\) the supported household types, and \(t=(S_{t1},S_{t2},S_{t3})\) the three approval sets for type \(t\). The mass \(\mu_t\) is the fraction of households of that type, with \(\sum_t\mu_t=1\). Let \(q_a\in[0,1]\) be the number of copies of category \(a\) available per household in the aggregate: each household can receive at most one copy of a category, but the population may receive many copies overall. This fits settings where, for example, many households compete for standardized slots or benefits. The intended regime is \(N\gg\tau\): many households, but relatively few distinct approval profiles.
Here is the continuous problem I would hand to a prover: Binary PROP1 Feasibility for Three-Person Households. An instance consists of \(A,T,\mu,q\) as above. A bundle is still an indivisible subset \(B\subseteq A\); \(x_{tB}\) is the mass of type-\(t\) households assigned exactly that bundle. Define the proportional share of member \(i\) of type \(t\) as
\[
p_{ti}=\sum_{a\in A}q_a\,\mathbf{1}[a\in S_{ti}].
\]
Ask whether there are nonnegative masses \(x_{tB}\) such that
\[
\sum_{B\subseteq A}x_{tB}=\mu_t
\quad\text{for every }t,
\qquad
\sum_t\sum_{B\ni a}x_{tB}=q_a
\quad\text{for every }a,
\]
and every bundle receiving positive mass is PROP1 for all three members of its type:
\[
x_{tB}>0\ \Longrightarrow\
|B\cap S_{ti}|+
\max\!\left(\{0\}\cup
\{1:a\in S_{ti}\setminus B,\ q_a>0\}\right)
\ge p_{ti}
\quad\text{for each }i.
\]
The solution is the mass assignment \(x\). Each household still gets an integral bundle; only the assignment of different bundles across the same type’s population is fractional.
This preserves the paper’s underlying question: can goods be allocated so that every member of every group reaches their proportional share up to one good? The change is to represent a large population by type masses and to scale supplies per household. For rational inputs, there is also a direct dictionary: a rational solution \(x\) can be scaled by a common denominator into a finite allocation instance with repeated households and goods; conversely, any such finite allocation gives \(x\) by dividing counts by the population size. That makes this a high-multiplicity version of the allocation problem, not a continuation of the goods or of the fairness axiom.
My expectation is Class A for this binary, three-member PROP1 mirror. Its configuration LP has up to \(\tau 2^m\) bundle variables, but its pricing problem looks manageable. For a fixed type, every category has one of seven nonzero approval patterns among the three members. A bundle is PROP1 when it meets three lower bounds on approved-category counts; because \(q_a\le1\), those thresholds are at most \(m\). A dynamic program over the three capped counts can find a minimum-priced qualifying bundle in polynomial time. That gives a pricing oracle for the configuration LP, and the ellipsoid/separation machinery gives a plausible weakly polynomial feasibility algorithm in \(m,\tau,L\).
This is a real change in the source of the difficulty. The paper’s 3DM reduction relies on integral group-to-bundle choices. In the mirror, mass of the same type may be split across qualifying bundles, so the matching obstruction may become a fractional one. The central prover question is whether the pricing argument yields the claimed algorithm and how to recover a finite rational mass assignment. Further questions are whether the approach extends to larger fixed group sizes, whether arbitrary additive utilities make pricing hard, and whether the EF1 version remains tractable despite its comparisons between bundles in the allocation’s support.
The paper’s NP-completeness result gives this mirror a substantial anchor, but it does not establish continuous hardness. In particular, the reduction has a separate group type for each 3DM triple, so its type support need not be small relative to its population. The continuous problem is aimed at a different, plausible regime with repeated profiles. My weakest point is the scenario: standardized benefit categories and repeated household approval profiles may fit a large program, but many fair-division instances concern one-off heterogeneous goods. If the authors or a referee reject repeated categories as a faithful regime for their allocation question, the mirror loses force. The mirror does preserve the groups of three, binary utilities, indivisible bundles, proportional benchmark, and one-good allowance; its case rests on whether the repeated-profile setting is convincing.
The best objection is that Theorem 4.4’s hardness may be a poor reason to expect a substantial continuous-computational contribution. Its reduction encodes a 3-Dimensional Matching instance in the compatibility between particular groups’ approval profiles and the goods they need. In a population mirror, identical households can be split among different bundles. That removes the one-to-one choices carrying the reduction’s obstruction.
The proposed model makes this convexification explicit: it assigns mass of each type to bundles that already satisfy PROP1, then checks aggregate supply. With three binary-valued members, those bundles are characterized by a small number of approval-count thresholds. A configuration LP with a dynamic-programming pricing oracle looks quite plausible. That could yield a valid Class A result, but it may be a routine consequence of anonymity and bounded group size rather than a revealing new complexity boundary. The paper’s NP-completeness theorem itself gives no reason to expect the continuous version to be hard.
There is also a fidelity question in the concrete formulation. The paper allocates distinct indivisible goods; the mirror replaces them with replicable categories and caps each household at one copy of a category. That cap is absent from the paper. Removing it would make bundles multisets and require a fresh pricing analysis; retaining it needs a setting where duplicate category copies are genuinely unavailable to one household. Neither issue rules out a mirror, but both make the proposed one less immediate than its description suggests.
The hardest objection to sustain is that no convincing high-multiplicity scenario exists. Repeated three-person approval profiles over a small catalogue are possible, and standardized benefits allocated to many households are plausible. The family, inheritance, and partnership examples in the paper are mostly small and heterogeneous, but that does not settle whether the same allocation problem has a sensible large-population regime.
So I cannot honestly make the universal negative case airtight. The strongest case against is that this anchor may produce a fairly direct fractional feasibility problem whose main obstruction disappears under type symmetry. That weakens the case for prioritizing this paper, but it does not defeat the repaired mirror: the repeated-household question is well-posed, and an efficient algorithm for it could still be worth studying.
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.