d4-conf-atal-2015-0397

The strongest hardness anchor is Theorem 16, proved in this paper. It says that, given an FEN-hedonic game, deciding whether there exists a coalition structure that is *possibly Nash stable* is NP-complete. “Possibly” means that there must be some partition of the agents and some profile of complete preference orders extending their generalized Bossong–Schweigert preferences for which the partition is Nash stable. The paper proves NP-hardness by reduction from X3C.

A plausible high-multiplicity setting is a large organization assigning employees to teams: many employees share one of a relatively small number of complete role-and-preference profiles. A type records an employee’s friend, neutral, and enemy classes among the other types, including the weak rankings within the friend and enemy classes. Its mass \(\mu_t\) is that profile’s share of the workforce. This is a meaningful regime when, say, tens of thousands of employees fall into dozens of preference types; it is not a claim that every small committee is a continuum population. The restriction that members of a type are indistinguishable is exactly the high-multiplicity assumption.

Here is the corresponding problem, Possible Nash Stability for Continuous FEN Populations. An instance is a finite supported type set \(T\), rational masses \(\mu_t\geq 0\) summing to one, and each type’s FEN rankings over types. A coalition is represented by a vector \(x\in[0,\mu]^\tau\), where \(x_t\) is the mass of type \(t\) in it. Extend the paper’s partial order to these vectors by divisible matching: for each friend-rank prefix, the preferred vector must contain at least as much mass in that prefix; for each enemy-rank suffix, it must contain no more mass in that suffix. Neutral mass is disregarded. A completion is a total preorder on coalition vectors extending this mass version of the GBS order.

The decision question is whether there is a measurable partition of the population and a complete preorder for each type such that almost every agent weakly prefers their current coalition to every other existing coalition joined by that agent, and to the empty-coalition option. A solution is the partition and the typewise completions; the objective is feasibility, as in Theorem 16. The number of types \(\tau\), the rational bit length \(L\), and the ranking input size are the natural complexity parameters. This is a literal continuous-population analogue of the paper’s possible-Nash-existence question, and I would expect its atomless version to be Class A, rather than a transfer of the theorem’s NP-hardness: a partition into singleton coalitions is stable. Each individual has zero mass, so moving to another singleton leaves the type-mass vector at zero, as does the empty option. The answer is always YES.

That collapse is also the mirror’s weakest point. In the finite game, joining another singleton adds an identifiable agent; in the atomless model, it adds zero mass. A referee might accept the question as the direct population limit of the paper’s problem but judge it too degenerate to carry a useful complexity study. The X3C reduction also creates many distinct preference roles, so it does not establish hardness in a regime with small support \(\tau\). I would not claim that Theorem 16’s hardness transfers.

A sturdier complementary anchor is Proposition 14, also proved here. It states that all the paper’s problems concerning perfection are in P; the entry I would mirror is deciding whether a perfect coalition structure exists. In the paper, perfection means every agent weakly prefers their assigned coalition to every possible coalition containing them. The associated mirror, Perfect Coalition Formation for Continuous FEN Populations, takes the same type-mass and ranking input and asks whether the population can be partitioned into coalition mass vectors so that almost every type-\(t\) agent’s coalition contains all the mass of each friend type and none of any enemy type. That is the type-mass form of the paper’s perfection characterization. It is a feasibility question with no numerical objective. A block’s types must be closed under friend relations and contain no enemy conflict; checking the friend-connected groups for internal enemy edges gives a polynomial-time decision procedure in \(\tau\) and \(L\). I expect Class A here as well. This is a more substantive mirror than possible Nash existence because perfection compares against all possible coalitions, not just the coalitions currently in the partition, so singleton cells do not automatically solve it.

Both questions preserve the paper’s coalition-formation object and its FEN preference structure while making the society itself a distribution over complete agent types. The fit is strongest where an organization really does have many interchangeable members of each role; it weakens when preferences depend on named colleagues. My case covers Theorem 16’s possible-Nash-stable existence question and Proposition 14’s perfect-structure existence question only. It does not claim a mirror for every stability concept in the paper. The central caveat is that atomless individual deviations erase exactly the one-person effects that make the lead hardness result interesting.