| paper | d4-conf-aaai-2026-4554 |
| 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: \(\mathrm{NP}\)-complete for \(\tau=2\), even when \(\mu_1=\mu_2=1/2\), every \(q_g=1/2\), and \(s_{tg}\in\{0,1\}\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 3
statement extracted from the paper’s text layer
Given two agent types with rational masses μ_t, integral bundles of indivisible good types, rational per-capita supplies q_g, and additive valuations and social impacts, does there exist a distribution of each type’s mass over bundles that uses every supply, maximizes total social impact, and is EF1 between every pair of bundles receiving positive mass?
Use types t ∈ {1,2}, masses μ_t summing to 1, and variables x_{t,B} for the fraction of the population of type t receiving integral bundle B. Require ∑_B x_{t,B} = μ_t and ∑_{t,B:g∈B} x_{t,B} = q_g; maximize ∑_{t,B} x_{t,B}s_t(B). For every B,D with x_{t,B}>0 and x_{u,D}>0, require v_t(B) ≥ v_t(D) or some g ∈ D satisfies v_t(B) ≥ v_t(D\{g}).
The mirror covers the EF1 case of Theorem 3 for socially unaware agents. It leaves the other fairness criteria and the paper’s results on social awareness, restricted valuations, and other agent counts unaddressed.
My strongest mirror is a two-type, high-multiplicity version of the paper’s EF1 result. Imagine a large network of clinics distributing standardized equipment: clinics share one of two complete profiles, each specifying how much they value each item and the social impact they produce with it. The type masses are population fractions, and item supplies scale with the population. That is a plausible regime with many clinics and very few distinct profiles.
Call the problem Two-Type Continuous SIM-EF1. An instance has a finite set \(G\) of indivisible good types; two agent types \(T=\{1,2\}\) with rational masses \(\mu_t>0\), \(\mu_1+\mu_2=1\); additive nonnegative rational valuations \(v_t(g)\) and social impacts \(s_t(g)\); and a rational per-capita supply \(q_g\in[0,1]\) for each good type. Each individual receives a subset \(B\subseteq G\), so every person’s bundle remains integral. A type is complete: all agents in it have the same valuation and social-impact functions. Repeated copies can be represented as separate good types if a person may receive more than one.
Represent an allocation by \(x_{t,B}\), the fraction of the whole population of type \(t\) receiving bundle \(B\). Feasibility requires
\[
\sum_{B\subseteq G}x_{t,B}=\mu_t
\quad\text{and}\quad
\sum_{t\in T}\sum_{B\ni g}x_{t,B}=q_g
\]
for every type \(t\) and good \(g\). Require EF1 between every pair of positive-mass cohorts: whenever \(x_{t,B}>0\) and \(x_{u,D}>0\), either \(v_t(B)\ge v_t(D)\), or some \(g\in D\) satisfies \(v_t(B)\ge v_t(D\setminus\{g\})\). Finally, require the allocation to attain the maximum total social impact possible for the given masses and supplies. The decision question is whether such an \(x\) exists; a solution is the finite table of cohort masses and bundles. All inputs and solution masses are rational, so the question has a finite encoding.
The anchor is Theorem 3, proved in this paper. Its full statement is that for every \(\mathcal F\in\{\text{tEF1},\text{EF1},\text{sEF1},\text{wEF1},\text{swEF1},\text{EFL}\}\), deciding whether a SIM and \(\mathcal F\)-fair allocation exists is NP-complete, even when social-impact functions are binary and there are only two agents. I rely specifically on its EF1 case. The paper proves the result by reducing from Partition; the cited hardness of Partition is weak, and the reduction uses nonbinary valuations. The theorem therefore anchors a sharp question about what happens when two distinct agents become two large cohorts with the same two profiles.
The authors could recognize this as their problem because the mirror keeps their core ingredients: additive private valuations, additive social impact, exact social-impact maximization, integral bundles, and EF1 comparisons between actual recipients. Only the scale changes: population and supplies are expressed as masses. For instance, \(x_{t,B}\) may describe a fraction of clinics receiving a particular whole bundle; it does not give any clinic a fractional item or fractional valuation.
For the two-type version, I lean toward Class A: the extra freedom to split each type’s population across bundles may smooth the Partition choice and permit a flow or configuration-based algorithm. That is a conjecture, not a consequence of Theorem 3. EF1 must hold across every pair of bundles that receives positive mass, and those bundles are still integral; those support-compatibility conditions could retain difficult combinatorics. The main next questions are whether the two-type problem is polynomial in \(m\) and the input bit length \(L\), whether configurations can be priced efficiently, and how the answer changes as the number of types \(\tau\) becomes part of the input. If hardness survives even for two types, it would be a continuum-specific obstruction; the finite two-agent reduction alone does not establish hardness transfer.
The scope here is deliberately narrow: it mirrors Theorem 3’s EF1 case in the socially unaware model. The weakest point is the supply scaling. The paper allocates a finite set of named goods, while the mirror gives each good type a population-scaled supply. Theorem 3 also studies exactly two agents, so it is an anchor for the question, not evidence that its reduction works in a high-multiplicity regime. I think the mirror remains worth asking because it preserves the paper’s allocation and fairness concepts at the individual level while making the population genuinely continuous.
The strongest case against the proposed mirror is a scaling mismatch in Theorem 3’s anchor. Its Partition reduction uses a fixed collection of one-off goods and forces each of two particular agents to receive a large item. If the population grows while that stock stays fixed, each good reaches a zero fraction of society; the mass model loses the forced allocation that makes the construction work. Scaling the stock with the population avoids that degeneration, but turns each one-off item into many copies. The anchor’s allocation gadget is then a different repeated-market problem, not a direct continuization of the reduction.
That objection does not rule out the stronger mirror the proponent gives. With repeated standardized goods, two complete agent profiles, and EF1 comparisons between every pair of bundles receiving positive mass, the question is coherent. Clinics or similar institutions could plausibly form large cohorts with those profiles. The paper’s fairness comparisons use valuations and bundles, not personal identity, so grouping identical agents does not discard information the model needs. The paper also has clear computational results to mirror; this is not a case where only axioms or distortion bounds are available.
The one-off-versus-replicated-goods distinction is a real reason to doubt that Theorem 3’s hardness result carries over unchanged. It is not a reason to dismiss the continuous question: per-capita supplies are an allowed co-modification, and whether mass splitting across integral bundles changes the problem is precisely something the mirror could establish. I can make a case against a *direct lift* of the reduction, but I cannot honestly make the universal case that no worthwhile mirror exists. The two-type repeated-goods version survives.
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.