| paper | d4-conf-aldt-2017-0021 |
| 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: Both core-existence and strict-core-existence are \(\Sigma_2^p\)-hard, hence \(\mathrm{NP}\)-hard. · discrete side: hardness · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 6.1
Given a finite type set \(T\), rational masses \(\mu_t\geq 0\) summing to \(1\), and a symmetric rational valuation matrix \(W=(w_{ts})\), decide whether the atomless population admits a measurable partition into coalitions with no positive-mass core block (or strict-core block). A type-\(t\) agent in a coalition with type-mass vector \(q\) has utility \(u_t(q)=\sum_{s\in T}w_{ts}q_s\); a core block makes its members strictly better off, while a strict-core block makes them weakly better off and has positive mass of strict improvers.
An atomless population of mass \(1\) has finitely many complete additive preference types with rational masses \(\mu_t\). Symmetric type valuations \(w_{ts}\) give utility \(\sum_s w_{ts}q_s\) for coalition composition \(q\). Outcomes are measurable partitions, equivalently countable lists of positive-mass coalition vectors with remaining mass assigned to null coalitions; deviations may use any available type masses.
The mirror covers Theorem 6.1's additive core and strict-core existence questions. It does not cover the Boolean hedonic result or the paper's questions about bounded-size blocking coalitions and other parameters.
The strongest positive case is Theorem 6.1, proved in this paper. It states that deciding whether an additive hedonic game has a strict-core-stable partition is \(\Sigma_2^p\)-complete; deciding whether it has a core-stable partition is also \(\Sigma_2^p\)-complete; and both problems remain hard when valuations are symmetric and each agent assigns nonzero values to at most 10 others. The paper proves the strict-core result and the symmetric, sparse strengthening; the core hardness had previously been established by Woeginger. The theorem and its proof are in the [arXiv version](https://arxiv.org/html/1509.02333).
My lead mirror is Continuous Type-Additive (Strict-)Core Existence. Consider a large cooperative project network in which many people form teams, and each person’s view of a team depends on the roles of its members. A type records a person’s complete role and preference profile. For example, everyone in a type might have the same skill profile and the same additive valuation of every other role. A plausible regime has \(N\) people and \(\tau\) such types, with many people per type and \(\tau\ll N\). People form coalitions because of the value they get from their teammates; no named individual-to-individual relationship is needed.
Precisely, an instance gives a finite type set \(T\), rational masses \(\mu_t\geq 0\) summing to \(1\), and a symmetric rational valuation matrix \(w_{ts}=w_{st}\). For the type-sparse version, each type has at most 10 nonzero entries in its row. The population is an atomless measured set \(\Omega=[0,1]\), with a measurable type assignment whose type-\(t\) agents have mass \(\mu_t\). If a coalition \(C\) has type-mass vector \(q(C)\), where \(q_s(C)\) is the mass of type \(s\) in \(C\), a type-\(t\) member’s normalized additive utility is
\[
u_t(C)=\sum_{s\in T}w_{ts}q_s(C).
\]
An outcome is a measurable partition of the population into coalitions; type mass may be split across teams. Equivalently, its positive-mass coalitions can be specified by a countable list of coalition-mass vectors, with any remaining agents in singleton coalitions.
The decision question takes a mode, core or strict core, and asks whether such a partition exists with no positive-mass blocking coalition. A core block is a positive-mass coalition whose members all strictly prefer its composition to their current coalitions. For the mass-based strict-core version, a block gives its members weakly higher utility and a positive mass of them strictly higher utility. A solution is a stable partition. This is an existence question, as in the theorem, rather than a welfare-maximization problem.
This is a high-multiplicity relaxation of type-uniform finite games: if a finite society has \(N\) members and \(N_t\) of type \(t\), its masses are \(\mu_t=N_t/N\); finite coalition profiles lie on the \(1/N\) grid, while the continuous problem allows fractional masses. Dividing finite additive utilities by \(N\) preserves their comparisons. It also exposes the important limit question: fractional splitting can change whether stable partitions exist, so the discrete theorem does not by itself prove hardness of this mirror. The paper’s reference to work on agent types in coalition formation supports the type-based regime; it is background, not a collision with this continuous computational question.
I would expect hardness to transfer (Class B) when \(\tau\) grows: the theorem’s quantified-formula structure can plausibly live in the number of types and their interaction pattern, even when each type has many members. That is a prediction, not a consequence of Theorem 6.1. The paper’s reduction uses named agents and specific incidences, so a proof would need to show those constraints survive fractional splitting. A natural follow-up is whether the problem is \(\Sigma_2^p\)-hard in \(\tau\) and the input bit length, including under type-level symmetry and sparsity; another is whether fixed or moderate \(\tau\) admits an efficient algorithm and a finite witness description.
The weakest point is the coarsening of the interaction structure. The theorem’s sparse instances give each person at most 10 named neighbors; this mirror gives each person nonzero value for at most 10 *types*, potentially containing a large fraction of the population. Thus it preserves additive hedonic preferences and the core question, but not the theorem’s individual-level sparse graph. Fractional participation may also break the reduction’s gadgets. The case survives as a plausible continuous version of the authors’ underlying stable-partition problem, but the named hardness result is motivation for the mirror, not evidence that its answer is already known.
The strongest objection to the proposed mirror is that it changes the interaction structure doing the work in Theorem 6.1. In the paper’s symmetric, sparse games, an agent values at most 10 *named individuals*. Under the programme’s definition, two agents are the same type only if their complete descriptions agree, including whom they value. If two agents have identical nonzero valuation rows, symmetry makes every valued neighbor adjacent to both; a group of \(r\) such agents therefore gives that neighbor at least \(r\) nonzero links. With degree bounded by 10, nontrivial identical types cannot have large multiplicity. Large classes of isolated agents are possible, but they contribute no interactions to the reduction.
The proposed matrix \(w_{ts}\) avoids that problem by making each type value the *mass* of another type. In a finite population, this means each person interacts with a growing number of people as the population grows, with per-pair values scaled to keep total utility finite. That is a coherent role-based model, but it replaces the paper’s sparse, identity-specific links with dense cohort interactions. Its blocking coalitions and partitions need not preserve the QBF gadgets or the paper’s sparse-game question. Calling it a mirror therefore requires more than showing that its finite versions are additive hedonic games: the authors must recognize this new, anonymous interaction model as their problem.
The sparse-preserving alternative has a different cost. One can take a continuum of copies of a finite interaction network, keeping each person linked only to named roles within their own copy. But then cross-copy coalition membership has no effect on anyone’s utility: core and strict-core stability reduce to stability within each copy. The continuum supplies repetitions, not aggregate interactions. A more general measured-network model could retain local links, but it must encode their correlations, which type masses alone cannot describe.
This is a real case against *Theorem 6.1’s sparse result* as a continuous mirror. It is not a decisive case against every worthwhile mirror. In particular, the role-based model is plausible for repeated teams with interchangeable skill profiles, and the paper itself points to the number of agent types as an open direction. That is evidence the authors might recognize the resulting question as theirs. So the universal negative claim remains weak: the strongest objection is a mismatch between the paper’s sparse identity-based interactions and the proposed mass-based ones, not a demonstration that no worthwhile continuous version 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.