| paper | d4-journals-mss-2024-0023 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: $\mathsf{NP}$-complete for every fixed $q\ge3$, even when all masses and supplies are dyadic rationals with precision bounded solely in terms of $q$. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 2
statement extracted from the paper’s text layer
For fixed \(q\ge3\), given \(q\) strict rankings over goods \(J\), positive rational type masses \(\mu_t\) summing to \(1\), and rational per-capita supplies \(\rho_j\), does there exist a bundle \(B_t\subseteq J\) for each type such that \(\sum_{t:j\in B_t}\mu_t=\rho_j\) for each good \(j\), and for every ordered pair \(t,u\) there is an injection \(f:B_u\to B_t\) whose matched goods are weakly preferred by type \(t\), with equality allowed only for copies of the same good?
A population of mass \(1\) has \(q\) preference types with masses \(\mu_t\); each unit of type \(t\) receives the same integral bundle \(B_t\). Goods have interchangeable copies and rational per-capita supplies \(\rho_j\). The decision variables are the type bundles, subject to exact supply use and pairwise necessary envy-freeness with indifference between copies of the same good.
The mirror makes copies of a catalogue good interchangeable, weakening the paper’s strict comparison between individually named items; author recognition therefore depends on accepting the scaled-supply cohort interpretation.
fatal: False
The mirror covers ExistsNEF for fixed \(q\ge3\), including the three-agent case; it leaves aside the two-agent polynomial-time result and the paper’s structural lemmas.
I’d make a conditional case around a high-multiplicity version of the paper’s existence problem. Consider a nonatomic population of mass \(1\), with a fixed set \(T\) of \(q\) preference types over a catalogue \(J\) of \(m\) goods. Type \(t\) has rational mass \(\mu_t>0\), and each catalogue good \(j\) has rational per-capita supply \(\rho_j\in[0,1]\). Copies of a catalogue good are interchangeable. The regime is a large distribution programme with many households but only a few stable preference archetypes; both inventory and cohort sizes scale with the population.
Call the problem Mass-ExistsWNEF. A solution chooses an integral bundle \(B_t\subseteq J\) for each type; every unit of mass of type \(t\) receives one copy of each good in \(B_t\). It must satisfy
\[
\sum_{t:\,j\in B_t}\mu_t=\rho_j
\quad\text{for every }j\in J.
\]
For every ordered pair \(t,u\), require an injection \(f:B_u\to B_t\) such that \(f(j)\) is at least as preferred by type \(t\) as \(j\). The comparison is weak only for interchangeable copies of the same catalogue good; rankings over distinct goods remain strict. Thus every individual receives an integral bundle, while the mass consumed by a good is fractional. The question is whether such type bundles exist.
My anchor is Theorem 2: for every fixed integer \(q\ge3\), ExistsNEF—deciding whether a complete necessarily envy-free allocation exists—is NP-complete on instances with \(q\) agents. The paper proves this result, extending its three-agent reduction with dummy agents. The mirror covers this existence result, not the paper’s broader fair-division setting.
The discrete problem embeds in the \(q\)-type mirror. Give each type mass \(1/q\), and set every good’s per-capita supply to \(1/q\). The supply equations then require each good to go to exactly one type, so the bundles partition the catalogue just as an allocation partitions the items among \(q\) agents. On the reduction instances, the agents have distinct preference lists and the bundles are disjoint; the weak comparison between copies therefore reduces to the paper’s strict comparison between items. This gives NP-hardness even at those fixed masses and supplies. With \(q\) fixed, a certificate consists of \(q\) bundles; supply and envy checks are polynomial, so this mirror is NP-complete. I would expect hardness to transfer (Class B): the reduction’s combinatorics live in the item catalogue, not in a large population.
The paper also cites high-multiplicity fair-allocation work, which supports treating large cohorts of identical agents as a sensible regime. That work is supporting context, not a collision with this necessary-envy-freeness question. Further questions include whether the two-type version has a polynomial algorithm, and what happens if a type’s mass may be split among different bundles while fairness is still imposed at the individual level.
The weak point is substantial. The paper defines strict preferences over individual items. If a positive-mass cohort repeats one complete strict ranking, exact individual-level NEF is generally incompatible with giving its members different disjoint bundles: each would have to strictly prefer its own bundle to the other’s. My mirror handles that by treating copies as tied within a catalogue category and giving equal bundles to equal types. A referee may regard those choices as a sensible high-multiplicity co-modification; they may instead judge that they change the fairness problem too much. Under the paper’s exact strict model, the theorem’s three-agent hardness alone does not establish a credible large-population regime.
The strongest negative point is that necessary envy-freeness resists aggregation by preference type. If two agents have the same strict ranking, NEF requires each agent’s bundle to be strictly preferable to the other’s. Applying the condition in both directions forces them to receive the same bundle. So, under the paper’s exact model, a large cohort of identical agents cannot divide a finite catalogue of indivisible items among its members and remain NEF. A literal population limit either degenerates or requires changing the goods model.
The best mirror handles that by scaling the supply of each catalogue good with the population and treating copies as interchangeable. That is plausible, but it also changes the setting: preferences are strict between catalogue goods and tied between their copies, and every member of a type receives the same bundle. The resulting problem has little room for splitting a type across allocations. This makes it a narrow mirror, and a critic could question whether it captures the paper’s strict, item-level model closely enough.
That concern does not defeat the anchor under the programme’s stated rules. With three types of mass \(1/3\), and per-capita supply \(1/3\) for every catalogue good, each good must go to exactly one type. The type bundles then partition the catalogue, and the NEF comparisons between types reproduce those between the paper’s three agents. Theorem 2 therefore supplies a well-posed continuous-population question, with the co-modification motivated by scaling supply. The paper’s cited high-multiplicity work supports the regime; it is not a collision.
I cannot honestly defeat this anchor. The objection is that the mirror may have limited continuous structure and depends on an extension to interchangeable copies. But the brief explicitly allows population-driven co-modifications, and hardness transfer is an intended result of the programme. The case against “no worthwhile continuous mirror in any scenario” is therefore weak.
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.