| paper | d4-conf-atal-2011-0264 |
| 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}\)-hard · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 2
Given a finite type set \(T\), rational masses \(\mu_t\geq 0\) summing to \(1\), and rational symmetric values \(a_{ts}=a_{st}\), represent the population by measurable type sets \(I_t\subseteq[0,1]\) with measure \(\mu_t\). For a measurable coalition \(C\), a member of type \(t\) receives \(u_t(C)=\sum_{s\in T}a_{ts}\lambda(C\cap I_s)\). Decide whether there is a measurable partition of \([0,1]\), up to measure zero, into positive-measure coalitions such that no positive-measure measurable group \(D\) has all its members weakly prefer \(D\) to their current coalition and a positive measure of its members strictly prefer it.
A finite-support, atomless hedonic society: each type is a complete valuation vector, carries rational mass \(\mu_t\), and values a coalition by the mass of each type it contains. The decision problem is strict-core existence for measurable partitions, with symmetry \(a_{ts}=a_{st}\); complexity is measured in \(|T|\) and the input bit length.
A measurable partition may involve arbitrarily many coalition compositions, and the case gives no finite representation theorem or bound on the compositions needed to decide existence.
fatal: False
The mirror covers Theorem 2's core and strict-core existence results, with emphasis on strict core. It leaves Theorem 1's contractual individual stability algorithm and Theorem 3's contractual strict-core verification result alone; Theorem 4 has a separate Pareto mirror.
I would anchor the case in Theorem 2, proved in this paper by reduction from ExactCoverBy3Sets; the NP-completeness fact for that source problem is cited from [15]. The theorem says that deciding whether an additively separable hedonic game has a core-stable partition is NP-hard in the strong sense, and so is deciding whether it has a strict-core-stable partition. Both claims hold even when preferences are symmetric. The reduction uses instances in which each element occurs in at most three sets. My lead mirror is the strict-core half of that result.
A natural regime is a large online community or professional association whose members form working groups. Members may value a group additively, with their value for a colleague determined by that colleague’s behavioral or professional type. A type is the member’s complete vector of values for all types. It is plausible to have thousands or millions of members but only tens or hundreds of such vectors. That is a scenario for this instance regime, not a claim about hedonic games generally.
Here is a continuous version that keeps the paper’s coalition question. The input is a finite type set \(T\), rational masses \(\mu_t\geq 0\) with \(\sum_{t\in T}\mu_t=1\), and rational values \(a_{ts}\). For the symmetric variant, require \(a_{ts}=a_{st}\). Represent the society by a unit interval partitioned into type sets of measures \(\mu_t\). If \(B\) is a coalition, a member of type \(t\) in \(B\) gets
\[
u_t(B)=\sum_{s\in T}a_{ts}\,\lvert B\cap T_s\rvert.
\]
A feasible partition is a measurable partition into positive-mass coalitions, covering the population up to measure zero. Continuous Strict-Core Existence asks whether there is such a partition with no positive-mass coalition whose members all weakly prefer it to their current coalitions and for which a positive mass of members strictly prefers it. This translates the paper’s strict-core blocking condition to divisible population mass; a solution is a stable partition of the population, or a proof that none exists.
I would not claim that Theorem 2’s hardness transfers. Its reduction builds element and set roles whose incidence pattern carries the exact-cover choice. In the continuous model, mass of a type can split among coalitions, so those choices may fractionalize. My tentative expectation is that this problem could be hard for continuum-specific reasons when the number of types varies: coalition compositions still range over a rich space, and ruling out all weakly blocking coalitions is a global condition. But the paper’s reduction does not establish that. A tractability result, perhaps using continuous optimization for a bounded number of types or a pricing oracle over coalition compositions, would be an equally valuable answer.
A second, distinct mirror comes from Theorem 4, also proved here. It says that verifying whether the partition consisting of the grand coalition is Pareto optimal is coNP-complete. The proof follows the reduction in Theorem 3 from Partition: the grand coalition is Pareto improvable exactly when the weights can be split into two equal-sum subsets. Continuous Grand-Coalition Pareto Test takes the same type-level population and asks whether every member can be made weakly better off by repartitioning the population, with a positive mass strictly better off. A solution is either a witnessing partition or a proof that none exists.
For this mirror, I expect the discrete hardness to dissolve, at least for the reduction in the paper. With divisible type mass, the weight cohorts can split to make the required total \(W/2\), even when no subset of the original indivisible weights sums to \(W/2\). That makes a tractable continuous formulation a credible target, though the general test still has to find a whole partition into coalitions with mutually compatible utility gains. A useful next question is whether that test has a polynomial-time algorithm, or whether its complexity is governed by the number of types and the pricing problem for admissible coalition compositions.
These mirrors cover Theorems 2 and 4, not the paper’s full set of results. They continuize the population while keeping additive member utility, coalition formation, and stability or Pareto efficiency as the computational questions. Fractional utility from a type’s mass in a coalition is part of that population model. The main weakness is the gap between the paper’s named-player reductions and a genuinely few-type population: the reductions encode detailed incidence or weight information that may require many types. That weakens any hardness-transfer claim, but leaves concrete, author-recognizable continuous questions whose answers could show precisely which parts of the discrete complexity survive.
The strongest negative case is that the two proposed mirrors have not yet become finite algorithmic problems with a controlled representation of their answers. In Theorem 2, the Exact Cover reduction gives each element six gadget players and each set its own player. Their complete utility vectors encode the incidence pattern, so the number of distinct types can grow with the instance. That is a poor fit for a high-multiplicity regime. In a continuous population, members with the same vector can also split across coalitions, so the reduction’s element-by-element choices do not carry over. This weakens the link to the theorem’s hardness result, though the loss of hardness itself is not an objection under the programme’s standard.
The proposed Continuous Strict-Core Existence question is still recognizable: a positive-mass group blocks when its members weakly gain and a positive mass strictly gains. The unresolved modeling burden is what an algorithm is meant to return or reason over. A measurable partition may contain arbitrarily many coalition compositions, while the input lists only finitely many rational type masses and values. Before treating this as a standard complexity question, one would want a representation theorem—for example, a bound on the number of coalition compositions needed to witness existence or nonexistence. Without one, the question is mathematically definable, but its intended algorithmic form is underspecified.
Theorem 4 has the same gap, and its reduction gives a particularly clear warning about the mirror’s relationship to the paper. The players \(z_i\) carry the separate weights \(a_i\); divisible type mass can be split to achieve a target total even when no subset of those original weights does. That removes the reduction’s indivisibility mechanism. Again, this cannot count against asking what happens in the continuous model. A broader test—whether any partition of a finite-type population Pareto-improves on the grand coalition—is coherent and could matter for large groups with repeated valuation profiles. It also requires accounting for potentially unboundedly many coalition compositions, so the paper does not supply a ready-made computational formulation for it.
Theorem 1’s polynomial-time result is a weaker fallback. Contractual individual stability concerns one person moving; in an atomless society, that person has zero mass, so the move changes no coalition’s aggregate composition and the consent conditions lose their original role. Making the mover a positive-mass group would define a different stability notion.
These points support treating the proposed mirrors as new model-building work rather than direct continuizations of the paper’s results. They do not support the universal claim that no worthwhile mirror exists. Large communities with repeated, complete valuation profiles are plausible populations, and strict-core existence and grand-coalition Pareto efficiency remain meaningful questions for them. The negative case is weak at its central claim: it raises a real finite-representation and scope problem, but the two anchors survive as credible research questions once that problem is addressed.
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.