| paper | d4-conf-aaai-2026-2709 |
| 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→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\text{-hard}\) · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Proposition 1
statement extracted from the paper’s text layer
Given a finite type set \(T\), positive rational type masses \(\mu_t\) summing to \(1\), and rational type-pair interaction masses \(q_{tu}\), choose fractions \(p_t\in[0,1]\) of each type for Team 1, with \(0<\sum_t\mu_t p_t<1\), to maximize \(K(p)=\sum_{t<u}q_{tu}\bigl(p_t(1-p_u)+(1-p_t)p_u\bigr)+\sum_t q_{tt}p_t(1-p_t)\). What is the complexity of computing a maximizing split, which gives an EF+SO two-team allocation?
A finite-type continuum of people: type \(t\) has mass \(\mu_t\), and a fraction \(p_t\) is assigned to Team 1. Rational type-pair interaction masses \(q_{tu}\) define the cut objective \(K(p)\); each person receives one team, and the two teams have equal cut value.
The mirror applies to type-block interaction networks: aggregate \(q_{tu}\) values do not retain individual adjacency information for arbitrary graphs.
fatal: False
Covers Proposition 1’s \(n=2\) EF+SO hardness result; it does not mirror the EF+TS algorithmic clause or the paper’s other results.
My strongest case is Lead mirror: Two-Team Continuous Cut-SO, anchored on Proposition 1. I read the paper’s team-formation interpretation literally: vertices represent people, and the two recipient bundles are teams. Consider a large cohort of people with a small number \(\tau\) of recurring roles. A type \(t\) has population mass \(\mu_t>0\), with \(\sum_t\mu_t=1\). People of the same type have the same role and the same interaction profile with every other type. Let \(q_{tu}\) be the rational interaction mass between types \(t\) and \(u\). This describes a type-block mean-field network: in a finite cohort, each person is assigned wholly to one team, while the fraction of each type assigned to each team can be any real number.
Write \(p_t\in[0,1]\) for the fraction of type \(t\) assigned to Team 1; Team 2 receives the rest. The cut value is
\[ K(p)=\sum_{t<u}q_{tu}\bigl(p_t(1-p_u)+(1-p_t)p_u\bigr) +\sum_t q_{tt}p_t(1-p_t), \]
where \(q_{tt}\) records within-type interaction mass. The instance consists of the type masses and rational interaction masses; a solution is a maximizing vector \(p\), implementable by assigning a subset of each type’s population to Team 1. Both teams have cut value \(K(p)\), since a cut and its complement have the same value. Thus every feasible partition is EF, and maximizing social welfare is exactly maximizing \(K(p)\). Require both teams to have positive mass, as the paper excludes empty bundles.
Proposition 1 says that for \(n=2\), an EF+SO allocation always exists, but computing one is NP-hard; it also says an EF+TS allocation always exists and can be computed in polynomial time. The proposition is proved in this paper: its hardness proof reduces to MAX-CUT, whose NP-hardness is cited from Garey et al. (1974). I anchor on the EF+SO hardness clause; the EF+TS clause is part of the proposition’s result, but I am not claiming a mirror for it here.
Why the hardness transfers: take any graph \(H\) on \(\tau\) vertices, use its vertices as types, set \(q_{tu}=1\) for each edge and \(0\) otherwise, and set \(q_{tt}=0\). Then \(K\) is affine in each coordinate \(p_t\) when the others are fixed, so a maximum exists at a corner \(p\in\{0,1\}^{\tau}\). At those corners, \(K(p)\) is exactly the number of edges cut in \(H\). The continuous optimum therefore equals MAX-CUT’s optimum. This is Class B: hardness transfers; the combinatorics remain in the type-interaction support \(\tau\), even when the population is arbitrarily large relative to \(\tau\).
The regime is plausible in the paper’s stated team-formation setting: for example, a large hiring cohort divided between two teams, with many people in each of a few skill or interaction roles. The number of people can greatly exceed the number of types, and type-level fractions represent how much of each role goes to each team. The continuous question preserves the paper’s cut objective, two-team fairness, and social-optimality criterion. Only the aggregate description changes, in the way a population limit requires; each person still receives an integral assignment.
The weakest point is that the paper’s formal input is an arbitrary finite simple graph, while this mirror represents interactions by type-pair densities. If individual adjacency is essential to the authors’ question, capturing it in types could force \(\tau\) to grow with the population and remove the high-multiplicity advantage. I think the mirror remains recognizable because the paper explicitly motivates cut valuations through team formation, and the aggregate model still asks for a maximum cut under its EF+SO formulation. This case covers Proposition 1’s \(n=2\) EF+SO hardness result only. Natural follow-up questions are whether within-type interactions \(q_{tt}>0\) create useful fractional optima, and which structural restrictions on the type-interaction graph make the continuous optimization tractable.
Proposition 1 is a genuine computational anchor: computing an EF+SO allocation for two agents is NP-hard, by reduction from MAX-CUT, and the proposition also gives a polynomial-time algorithm for EF+TS. The paper therefore does not fail for lack of a named computational result.
The strongest objection is that the proposed \(q_{tu},p_t\) model does not follow from an arbitrary graph in the paper. In a general graph, the fractions of each type assigned to a team and the total number of edges between types do not determine the cut: which particular vertices are assigned matters. Preserving the exact graph may require making types fine enough to distinguish adjacency patterns, potentially leaving no compression. Using only aggregate interaction masses instead imposes a mixing or mean-field assumption. There is also a scope concern: the paper’s formal agents are the two recipients, who have identical valuations; the proposed continuum is on the vertex side, where people are treated as items.
That objection does not defeat the stronger version of the mirror. In a team-formation regime with a fixed set of role types and a graph built from repeated, type-level interaction patterns, the population can be a weighted blow-up of a finite graph. Then type fractions determine the cut exactly, and each person still goes to one team. The paper itself motivates its model with team formation, so this seems a plausible scenario the authors could recognize. The fact that the continuous optimum can encode MAX-CUT is no reason to dismiss the question under the programme’s criteria.
So the negative case is weak. It identifies a modeling boundary: an aggregate type graph needs a justified interaction structure, and the mirror treats the people being assigned as the continuous population. But the paper’s application gives a credible high-multiplicity regime on that side of the allocation. I cannot honestly claim that no worthwhile continuous mirror 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.