| paper | d4-conf-atal-2014-0290 |
| 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}\text{-complete}\) · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 5
statement extracted from the paper’s text layer
Given a graph \(H=(T,F)\), positive rational masses \(\mu_t\) with \(\sum_{t\in T}\mu_t=1\), and affinities \(w_{ts}=-1\) for \(\{t,s\}\in F\) and \(0\) otherwise, does there exist a stable allocation among exactly three nonempty coalitions? An allocation is \(x_{ti}\geq 0\), with \(\sum_{i=1}^{3}x_{ti}=\mu_t\) and positive total mass in each coalition; type-\(t\) utility in coalition \(i\) is \(u_t(i)=\sum_{s\in T}w_{ts}x_{si}\). Require individual rationality \(u_t(i)\geq 0\) for each occupied type-coalition pair, and no blocking deviation of the paper's exact-\(k\) form interpreted over mass, in which every participating mass strictly benefits while exactly three coalitions remain.
A finite set of role types \(T\) carries rational population masses \(\mu_t\) and a symmetric type-level interaction graph. The decision variables \(x_{ti}\) split each type's mass among three coalitions; utilities are the interaction-weighted masses in each coalition, and the question is whether a \(k\)-coalitions-core allocation exists.
The hardness is support-level: the magnitudes of \(\mu_t\) do not affect existence, and stability reduces to individual rationality. The proponent notes that hardness survives mass splitting but does not show a proportion-sensitive phenomenon.
fatal: False
Covers the \(k=3\) hardness argument for K-C-EXIST in Theorem 5; it does not cover the organizer result, K-C-FIND, or K-C-MEMBERSHIP.
The strongest lead is Theorem 5, proved in the paper. It states: for a social network with positive and negative weights, K-C-EXIST—whether the \(k\)-coalitions-core is nonempty—is NP-hard for every fixed \(k>2\). The paper proves this by reducing from graph coloring, explicitly giving the \(k=3\) construction: each graph vertex becomes an agent, and each graph edge becomes a relationship of weight \(-1\). I would mirror the \(k=3\) case, where the reduction is clearest.
Call the continuous problem Three-Cohort-Core-Existence. Its input is a graph \(H=(T,F)\), with one role type \(t\) per vertex, positive rational masses \(\mu_t\) summing to \(1\), and affinities \(w_{ts}=-1\) when \(\{t,s\}\in F\), \(0\) otherwise, and \(w_{tt}=0\). A coalition structure is a matrix \(x_{ti}\geq0\), for \(i\in\{1,2,3\}\), with \(\sum_i x_{ti}=\mu_t\) and positive mass in each coalition. Thus types may split across coalitions. A type-\(t\) member in coalition \(i\) has utility \(v_t(i)=\sum_s w_{ts}x_{si}\), with the singleton outside option \(0\).
Use the paper’s \(k\)-coalitions-core conditions in their mass form: every occupied type-coalition pair must be individually rational, \(v_t(i)\geq0\); a block may include all the mass of exactly one existing coalition and portions of others, and must make every participating portion strictly better off while leaving exactly three coalitions. The problem asks whether such a core partition exists, and, on yes instances, to return one.
This remains NP-hard even though mass is divisible. With only negative affinities, individual rationality forces every coalition’s support to be an independent set: if adjacent types both have positive mass in a coalition, each has negative utility. Choose any occupied coalition for each type; adjacent types cannot choose the same one, giving a proper three-coloring. Conversely, a proper coloring gives a core partition with utility \(0\) for everyone, and no block can improve anyone’s utility above \(0\). So this is a direct reduction from three-coloring, not an appeal to an analogy. It also survives cohort replication: each role can represent \(q\) identical agents, making the population \(q\tau\) while preserving the coloring obstruction. The expected classification is hardness transfers. The hardness is driven by the conflict pattern across types, so allowing fractional mass does not dissolve it.
A second, distinct mirror is Theorem 3, also proved in the paper. It states that for \(0<\alpha<2\), the organizer’s problem of choosing added edges and a \(k\)-coalition partition to maximize \(SW(P,E_{\mathrm{new}})-\alpha|E^+|\) is solvable in polynomial time when \(k\) is fixed and the graph family is nearly positive. The proof gives Algorithm 1 and reduces to the paper’s earlier minimum-\(k\)-cut result, using cited cut algorithms.
Call the continuous version Cohort-Organizer-SW. Its input is rational masses \(\mu_t\) over \(\tau\) role types, a symmetric type-level relationship pattern and weights, fixed \(k\), and rational \(0<\alpha<2\). All members of a type have the same relationship profile to every type; relationship status and weight are uniform between each pair of types. Choose mass allocations \(x_{ti}\geq0\) summing to \(\mu_t\), with exactly \(k\) nonempty coalitions, and relationship-mass additions \(y_{tsi}\). For \(t\ne s\), \(y_{tsi}\leq x_{ti}x_{si}\); for same-type pairs, \(y_{tti}\leq x_{ti}^2/2\). Each unit of added relationship mass contributes \(2\) to social welfare and costs \(\alpha\). Existing relationships contribute twice their weight per unit of within-coalition pair mass. The task is to return allocations and additions maximizing social welfare minus facilitation cost.
The intended tractable regime has fixed \(k\), no negative within-type affinities, and a negative-edge vertex cover of size \(O(\log\tau)\) in the type interaction graph. For \(0<\alpha<2\), all feasible missing relationship mass within a coalition is beneficial. After taking that mass to its upper bound, the objective is convex in each type’s allocation row, so there is an optimum that assigns each type wholly to one coalition. The remaining optimization is a signed minimum-\(k\)-cut problem on the \(\tau\)-node type graph, with rational edge weights scaled by the masses. I expect tractability in \(\operatorname{poly}(\tau,L)\) for fixed \(k\) in this regime. Further questions include what happens when the negative-edge cover is unrestricted, or when within-type affinities can be negative and fractional splitting may then matter.
These mirrors cover the paper’s core-existence result and its organizer social-welfare optimization; they do not claim to continuize every stability result in Section 4. The core-existence mirror is my lead because its hardness survives the move to mass and has a short equivalence argument. The organizer mirror is an additional, plausible optimization question: the pairwise interaction and link-building decisions become quantities of mass, and the type-level cut structure provides a route to an algorithm.
The weakest point is the cohort assumption. The paper allows individualized social networks, while these mirrors require agents in a type to share their relationship profile across types. A large workforce in role cohorts, with collaboration compatibility set by role pairs, is a plausible instance regime, but it is a real restriction on the network model. The core mirror also needs a precise atomless blocking convention. I have used the direct mass analogue of the paper’s “one coalition contained in a blocking coalition” rule; the hardness equivalence itself rests on individual rationality, so it is insensitive to many finer choices about blocking.
The organizer mirror does not work as stated. In an atomless population, “exactly \(k\) nonempty coalitions” does not impose a positive minimum size on any coalition, so the maximum may not exist. Take one type of mass \(1\), \(k=2\), no existing relationships, and \(0<\alpha<2\). With the proposed pair-mass model, the net value is proportional to
\[
\frac{2-\alpha}{2}(x_1^2+x_2^2),
\qquad x_1+x_2=1,\quad x_1,x_2>0.
\]
Its supremum occurs as one coalition’s mass approaches zero, but it is never attained. The discrete theorem always has an optimum because each coalition contains at least one agent. A continuous version needs an added minimum workforce per task, or a different task-count convention. Either could be sensible, but it changes the problem; the claimed reduction to a minimum-\(k\)-cut does not establish the result for that repaired model.
The core-existence mirror is much harder to dismiss. Its reduction is sound under the stated cohort interpretation. Give each graph vertex positive mass and make adjacent types negatively related. Individual rationality then forces the types sharing any coalition to form an independent set. Choosing a coalition for each type yields a proper three-coloring. Conversely, a proper coloring gives three coalitions in which everyone has utility \(0\), and no blocking coalition can make anyone strictly better off. Replicating each type into a large cohort preserves this construction. The paper’s network is about individual relationships, but role cohorts with uniform compatibility between roles are a plausible block-structured social network. That is a restrictive regime; I cannot honestly say the authors would reject it as their problem.
The strongest objection to that surviving mirror is about what the continuous model adds. In this reduction, the yes/no answer depends only on which types have positive mass: changing their proportions does not matter. Core stability also contributes no further test once individual rationality gives everyone utility \(0\). The mirrored question is therefore a support-level coloring problem, rather than a question whose computational content depends on population proportions. That leaves little specifically continuous behavior to study here. But this is a weakness in the mirror’s value, not a decisive reason to rule it out: the programme explicitly treats transferred hardness as a legitimate outcome.
So the negative case is weak at its lead. The organizer anchor needs repair before it is a well-posed optimization mirror; Theorem 5 still supplies a defensible continuous-population question in a narrow but plausible cohort regime. I cannot support the universal claim that no worthwhile mirror exists.
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.