| paper | d4-journals-ai-2013-0052 |
| 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{-hard}\) · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given a finite type set \(T\), rational masses \(\mu_t>0\) summing to \(1\), a symmetric rational valuation matrix \(V\) with nonzero entries, and rational \(\varepsilon>0\), find a finite list of rational coalition compositions \(q^k\ge 0\), with \(\sum_k q^k\le\mu\), whose welfare \(\sum_k (q^k)^{\mathsf T}Vq^k\) is within additive \(\varepsilon\) of the maximum over all measurable partitions of the atomless population. Determine the computational complexity in \(|T|\), input bit length, and \(\varepsilon\).
An atomless unit-mass society has finitely many complete preference types \(t\in T\), masses \(\mu_t\), and symmetric valuations \(v_{tt'}\). A coalition is represented by its type-mass vector \(q^k\); its contribution to normalized utilitarian welfare is \((q^k)^{\mathsf T}Vq^k\), and the objective is to maximize the sum over a feasible partition of the mass.
The mirror covers Theorem 1’s maximum utilitarian welfare problem. It leaves the egalitarian, Pareto, envy-freeness, and stability results unaddressed.
The strongest mirror I see is the paper’s utilitarian partition problem. Its lead anchor is Theorem 1, proved in this paper using the known NP-hardness of Max Agreements in correlation clustering: *computing a maximum-utilitarian-welfare partition is NP-hard in the strong sense, even when preferences are symmetric and strict.* This is the cleanest fit because utilitarian welfare sums individual utilities, so its population version has a direct mass-based definition.
Call the mirror Continuous Max-Utilitarian ASHG. An instance has a finite set \(T\) of types, rational positive masses \(\mu_t\) with \(\sum_{t\in T}\mu_t=1\), and a rational symmetric matrix \(v_{tt'}=v_{t't}\). An agent of type \(t\) values each member of type \(t'\) at \(v_{tt'}\); take every entry to be nonzero, matching the paper’s notion of strict preferences. Thus a type is a complete description of the agent’s preferences for this problem.
Represent the society by an atomless unit-mass population with type masses \(\mu\). A feasible coalition structure is a measurable partition of that population. For coalition \(k\), let \(q^k_t\) be its mass of type \(t\). An agent of type \(t\) in that coalition receives utility \(\sum_{t'}v_{tt'}q^k_{t'}\). The population’s normalized utilitarian welfare is
\[ W=\sum_k\sum_{t,t'}v_{tt'}q^k_tq^k_{t'}. \]
The decision variable is the partition, or equivalently its feasible coalition-composition vectors, with \(\sum_k q^k_t\leq \mu_t\). Any leftover mass can be assigned to singleton coalitions, giving zero utility. The underlying question is to maximize \(W\). For a finite, checkable output, give a rational \(\varepsilon>0\) and ask for a finite list of rational composition vectors whose welfare is within \(\varepsilon\) of the optimum. Atomlessness lets each such list be realized by splitting type mass among the specified coalitions. The normalization corresponds to dividing a discrete game’s total welfare by \(n^2\): as repeated types grow, the omitted self-interactions vanish.
A plausible regime is a large platform or organization forming affinity-based teams: many thousands of people, but a much smaller catalog of role and preference profiles. Members with the same profile have the same values for every other profile, and the symmetric matrix represents shared compatibility. Here the many agents share complete problem-relevant types, while mass—not one-person increments—is the natural scale for team composition. The coalitions and additive utility remain those of the paper; it is the population that becomes continuous. I think the authors would recognize this as their utilitarian partition problem in a high-multiplicity regime.
My expectation for this mirror is continuum-specific hardness (Class C), though that is a research hypothesis rather than a result of Theorem 1. Optimizing over coalition compositions appears to leave a nonconvex quadratic problem over a continuous domain. A central question is whether that structure admits efficient optimization or pricing, or instead makes the continuous problem hard in its own right. Further questions include whether an optimal partition can be represented by finitely many coalition compositions, the approximation complexity in \(\tau=|T|\), input bit length and \(\varepsilon\), and the integrality gap between the continuous optimum and discrete populations with repeated types.
The soft spot is substantial: Theorem 1’s hardness does not establish hardness for this mirror. Its correlation-clustering combinatorics may rely on distinctions among individual players, while the mirror groups agents with identical valuations and permits their mass to split. The theorem therefore supplies the problem and a meaningful hardness benchmark, not a transferred reduction. That limitation is also exactly why the mirror is worth asking: does divisibility make utilitarian coalition formation tractable in a genuinely high-multiplicity society?
The strongest case against the proponent’s anchor is that Theorem 1’s proof is an individual-player result: its reduction uses a graph of pairwise agreements, and grouping players by identical valuation profiles may leave as many types as players. It therefore does not establish hardness in a regime with many agents per type, or show that such a regime is central to the paper’s applications.
That gap does not defeat the better mirror. A large organization could form teams from many employees in a small set of role or preference types, with compatibility depending on the pair of types. For rational masses \(\mu_t\) and a symmetric valuation matrix \(V\), a coalition with type-mass vector \(q^k\) contributes \(q^{k\mathsf T}Vq^k\) to normalized utilitarian welfare. This retains the paper’s objective while making the population continuous. In a finite society with many copies of each type, the corresponding normalized welfare approaches this expression; the omitted self-interactions vanish as the population grows.
The resulting optimization over coalition compositions may be difficult, and its answer may differ from the discrete problem’s. Neither possibility counts against asking the question: tractability, hardness, and the effect of divisibility are precisely what the mirror could establish. The continuous model also has no obvious degeneracy for utilitarian welfare: positive-mass coalitions can contribute nonzero welfare, while singletons retain the paper’s zero-utility baseline.
So the negative case is weak. Theorem 1’s reduction does not transfer automatically, and the role-based scenario is a modeling choice rather than evidence that the authors’ usual applications have high multiplicity. But a plausible repeated-type regime exists, and I cannot show that its continuous optimization question is unrecognizable or unworthy of study. On the stated standard, Theorem 1 survives as a worthwhile mirror.
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.