| paper | d4-journals-mss-2015-0062 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→NP-hard discrete result → its continuous mirror
Answer: Existence is \(\mathrm{NP}\)-complete, even for \(\tau=1\). Explicit stable partitions can require \(2^{\Omega(L)}\) output length even for \(\tau=1\) and \(k=3\). Construction is possible in \(2^{\operatorname{poly}(\tau,k,L)}+O(\ell_{\mathrm{out}})\) time, or with polynomial preprocessing using an \(\mathrm{NP}\) oracle followed by \(O(\ell_{\mathrm{out}})\) expansion. Deterministic construction polynomial in input plus output length exists if and only if \(\mathrm{P}=\mathrm{NP}\). · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 3
statement extracted from the paper’s text layer
Given rational type masses \(\mu_t\) and an explicitly represented rational piecewise-linear common score \(U(q)\) on feasible nonzero coalition-mass vectors \(0 \le q \le \mu\), decide whether there is a finite list of nonzero rational vectors \(q^1,\ldots,q^r\) with \(\sum_j q^j=\mu\) that is core stable, and output one if it exists. Core stability means there is no nonzero \(b \le \mu\) and decomposition \(b=\sum_j b^j\), with \(0 \le b^j \le q^j\), such that every group supplying positive mass strictly prefers the blocking coalition: \(b^j \ne 0 \Rightarrow U(b)>U(q^j)\).
An atomless workforce has finitely many role types with rational population shares \(\mu_t\). A coalition is represented by its type-mass vector \(q\), and all workers share a rational piecewise-linear ranking score \(U(q)\). The task is to find a finite partition of the population into coalition-mass vectors that admits no strictly preferred positive-mass blocking coalition.
Theorem 3's finite guarantee does not ensure existence in the mass model, and the piecewise-linear score supplies an input representation not specified by the theorem.
fatal: False
The mirror covers the core-stability component of Theorem 3; it leaves the joint individual-stability guarantee, subset-neutral Nash-stability results, and representation results aside.
The best anchor is Theorem 3, proved in the paper. It says that every hedonic game satisfying the common-ranking property has a partition that is core stable, individually stable, and contractually individually stable. It also gives an algorithm: repeatedly choose a highest-ranked coalition among the remaining players, break ties by choosing the largest coalition, and remove it. The paper proves that this procedure returns a partition with those properties. It does not give a polynomial-time bound or a complexity classification, so this is an algorithmic existence anchor, not a tractability theorem.
A plausible high-multiplicity setting is a large workforce divided among a fixed, relatively small number \(\tau\) of role or skill types. For each type \(t\), let \(\mu_t\) be its share of the population, with \(\sum_t\mu_t=1\). A coalition is described by its type-mass vector \(q\), where \(q_t\) is the share of the whole population of type \(t\) in that coalition. Suppose workers share a common ranking over coalition compositions, represented by a score \(U(q)\): higher scores mean more preferred coalitions. This fits, for example, a setting where workers value team composition through a shared measure of team performance. Types can be split across teams, so coalition masses need not be integral.
Here is the continuous problem I would hand to a prover: Common-Ranking Stable Mass Partition. The input is rational type masses \(\mu\), a rational piecewise-linear common score \(U\) on feasible nonzero coalition-mass vectors \(0\le q\le\mu\), and a common utility \(u_0\) for being alone. Decide whether there is a finite list of nonzero rational vectors \(q^1,\ldots,q^r\) with \(\sum_j q^j=\mu\) that describes a stable partition, and output one if it exists. Any such list can be realized by measurable groups in an atomless population.
Core stability means there are no nonzero vectors \(b^1,\ldots,b^r\), with \(b^j\le q^j\), such that \(b=\sum_j b^j\) and every source group supplying deviators strictly prefers the new coalition: \(b^j\ne0\) implies \(U(b)>U(q^j)\). Individual stability means no infinitesimal agent can improve by moving to another existing group or becoming a singleton; destination members accept because the move changes no group’s mass. Thus all occupied groups must have equal \(U\)-value, at least \(u_0\). Together, these conditions make the question concrete: can the population be partitioned into mass vectors that attain the highest feasible positive coalition score, while meeting the singleton condition?
I would provisionally expect a Class A result for fixed \(\tau\) and this piecewise-linear input: one can optimize over the finitely described regions of \(U\), then study whether the maximizing mass vectors can be assembled into a partition of \(\mu\). The decomposition step is the uncertain part; its complexity as \(\tau\) varies is a natural follow-up. Other questions include when the paper’s peeling algorithm extends to mass vectors, whether countably many groups are ever needed, and how the result relates to finite high-multiplicity instances.
This mirrors Theorem 3’s common-ranking stability result, not the paper’s full study of hedonic games, its subset-neutral Nash-stability result, or its representation results. My weakest point is individual stability: a single agent has zero mass here, so moving does not change a coalition’s composition. The paper’s largest-coalition tie-break matters because a finite entrant changes group sizes; it does not transfer directly. The mass-level core question is the firmer part of the mirror, and the joint core-and-individual-stability problem should be presented with that limitation explicit.
The strongest case against starts with Theorem 3’s limited computational content. It gives a peeling procedure, but no running-time bound or compact input model: preferences are rankings over coalitions, and choosing the highest-ranked coalition may require examining exponentially many subsets. So the paper does not give a complexity result whose continuous counterpart is waiting to be charted. To get one, the proponent must add a succinct model such as a piecewise-linear score \(U(q)\) over type-mass vectors. That is a plausible research question, but its input and computational structure come from the new model, not from a complexity question posed by the theorem.
There is also a real gap in the proposed *joint* core-and-individual-stability mirror. In an atomless population, one agent can move without changing either coalition’s mass. Individual stability therefore reduces to a condition on the scores of occupied groups: they must all have the same \(U\)-value, and that value must be at least the singleton value. Combined with core stability, this requires a partition into groups whose mass vectors all attain the highest feasible score. The paper’s finite algorithm instead relies on removing a highest-ranked coalition and breaking ties by choosing the largest one; an infinitesimal entrant does not change a destination group, so that part of the theorem has changed substantially. The proposed mirror should not present the finite joint-stability guarantee as carrying over.
That still does not defeat the stronger version of the anchor. Workers can plausibly fall into a small number of role types, and a shared ranking over team compositions is a coherent high-multiplicity model. Core blocking by positive masses remains meaningful even when individual moves have zero mass. One could ask whether a stable mass partition exists and how to compute one, allowing the answer to differ from the finite theorem. This question is not already answered merely because the paper supplies a finite algorithm, and its having a potentially simple or negative answer would not make it unworthy.
So the negative case is weak where it needs to be strongest. It can show that the proponent has not established a Class A result, and that the joint core-and-individual mirror needs reformulation. It cannot honestly show that no worthwhile continuous mirror exists: a core-stability problem for role-composition masses survives the best objections. The firmest conclusion is that this paper offers a less direct anchor than a named complexity theorem, not that the anchor fails.
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.