| paper | Simple Causes of Complexity in Hedonic Games |
| authors | Dominik Peters, Edith Elkind |
| venue | IJCAI 2015 |
| filed under | coalition · hedonic |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 3
statement extracted from the paper’s text layer
Given a finite type set \(\Theta\), rational masses \(\mu\in\mathbb{Q}_{\ge 0}^{\tau}\) summing to \(1\), and complete median-game profiles \(v_{\theta}(\eta)\), does there exist a finite-support measurable partition into coalition mass vectors \(z^1,\ldots,z^R\) and singleton mass \(s\), with \(\sum_r z^r+s=\mu\), such that no positive-mass coalition \(b\) strictly improves every participant (CR), or weakly improves all participants and strictly improves a positive mass (SCR)?
A finite type space with complete median-game profiles, rational population masses \(\mu\), divisible cohort mass, coalition vectors \(z^r\), weighted-median utilities, and positive-mass blocking coalitions; the computational objective is feasibility of a CR- or SCR-stable partition.
The formulation gives no support bound or finite encoding for measurable partitions, and cohort splitting may eliminate the parity mechanism used in Theorem 3.
fatal: False
The mirror covers the median-game instantiation of Theorem 3 for CR- and SCR-EXISTENCE, including nonnegative utilities; it leaves the paper's other representations and stability concepts untreated.
The strongest mirror is a continuous version of the paper’s median-game core-existence problem.
The lead anchor is Theorem 3. Proved in this paper (with the full proof deferred to its extended version), it states:
For every polynomially representable class \(C\), CR-EXISTENCE and SCR-EXISTENCE for \(C\) are NP-hard if, for every finite agent set \(N\) and every strict, mutual collection of preference orderings in which each agent has at most four friends, \(C\) contains a game that is consistent on pairs, triangle-appreciating, monotone on triangles, \(\{0\!-\!1\}\)-toxic, weakly \(\{1\!-\!1,2\!-\!2,3\!-\!3\}\)-toxic, and intolerant in triangles.
Section 6 instantiates this theorem for median games with \(J0,5K\)-utilities, and notes that the hardness remains for social median games with non-negative utilities. I use that median-game consequence as the concrete anchor.
My proposed mirror is Continuous Median-Core Existence.
There is a unit-mass population divided among finitely many complete types \(\Theta=\{1,\ldots,\tau\}\). Type \(\theta\) has mass \(\mu_\theta\), where \(\mu\in\mathbb{Q}_{\ge 0}^{\tau}\) and \(\sum_\theta\mu_\theta=1\). A type includes the agent’s entire preference profile: its values \(v_\theta(\eta)\) for every possible member type \(\eta\), its tie-breaking convention, and its singleton value. Thus two agents of the same type are interchangeable in every respect used by the model.
For a coalition with type-mass vector \(z\neq 0\), type \(\theta\)'s utility is the weighted median of the values \(v_\theta(\eta)\), with weights \(z_\eta\). More precisely, if \(q_z\) is the normalized distribution \(z/\|z\|_1\), define
\[ u_\theta(z) = \frac{q^-_{\theta,z}+q^+_{\theta,z}}{2}, \]
where \(q^-_{\theta,z}\) and \(q^+_{\theta,z}\) are the lower and upper \(1/2\)-quantiles of \(v_\theta(\eta)\) under \(q_z\). This agrees with the ordinary median on odd-sized coalitions and averages the two middle values on even-sized coalitions. Singleton mass receives the type’s singleton value, normalized to \(0\) as in the paper’s median-game constructions.
An outcome is a finite collection of coalition mass vectors \(z^1,\ldots,z^r\), together with singleton mass \(s\), satisfying
\[ \sum_{r=1}^{R}z^r+s=\mu. \]
This is an actual measurable partition: each type cohort can be divided into the listed masses. The decision question is whether there is such an outcome with no blocking positive-mass coalition. A deviating coalition has mass vector \(b\), assembled from agents currently in the various coalitions and singleton mass. It core-blocks the outcome if every participating agent strictly prefers \(u_\theta(b)\) to her current utility. For the strict core variant, every participant must weakly prefer \(b\), with a positive mass of participants strictly preferring it.
This is not merely fractionalizing the outcome. Individuals still belong wholly to coalitions; only the population of indistinguishable agents is divisible. The continuous object is the society, while the underlying question remains exactly the paper’s question: does there exist a coalition structure immune to profitable group deviations?
A natural regime is a large organization, platform, or municipality forming voluntary teams or clubs. Millions of participants may fall into a relatively small number of recurring social or professional types. Members of a type have the same compatibility profile, and median utility captures settings in which an agent evaluates a group by the quality of its middle member: “at least half of my teammates must be acceptable.” Here the number of agents is enormous compared with \(\tau\), and \(\mu_\theta\) is the honest quantity. A type is not merely a preference label; it includes the complete median-game profile, so the construction respects the programme’s high-multiplicity requirement.
The original authors should recognize this as their problem. The paper’s median games already define preferences from individual member values and then evaluate coalitions by a median. Replacing a large cohort of identical agents by its mass and replacing an ordinary median by a weighted median is the direct high-multiplicity operation. The friend graph, mutuality, toxicity, triangle conditions, and core deviations all remain present at the type level. The paper itself is finite and never makes the population continuous, so this is not a novelty collision.
My provisional expectation is Class B: hardness should transfer. The combinatorics in Theorem 3 live primarily in the sparse interaction structure—mutual friend edges, triangles, and the clause-cycle gadgets—not in large numerical population counts. That suggests that a reduction could encode the gadget graph in the type space and amplify every type into a large cohort. The main technical task would be proving that fractional splitting of cohorts cannot repair an unsatisfiable gadget. If the odd-cycle and triangle conditions enforce that integrality, the paper’s NP-hardness becomes hardness of the continuous problem as well.
The further questions are substantial:
The weakest point is precisely the hardness-transfer claim. Theorem 3’s proof uses individual agents and odd finite gadgets. In the continuum, a cohort can split across several coalitions, and weighted medians may permit fractional arrangements that have no discrete counterpart. Thus I would not claim that Theorem 3 automatically proves continuous NP-hardness. What it does provide is a particularly faithful and nontrivial mirror whose central research question is whether the paper’s discrete obstruction survives high multiplicity. Even if the answer is unexpectedly tractable, that would be a meaningful continuization result rather than a change of subject.
The median-game anchor is the only one raised, and it is not honestly defeatable by saying that the paper lacks a computational result: Theorem 3 explicitly gives NP-hardness for core-existence, and Section 6 instantiates it for median games with nonnegative utilities.
The strongest negative case is that the proposed continuum destroys the mechanism that Theorem 3 actually exploits. Its reduction uses named vertices, sparse friend graphs, and odd nine-agent cycles. The obstruction is parity: a nine-cycle cannot be partitioned into stable pairs, so it must connect to a literal gadget. In a genuinely divisible population, a cohort can be split across arbitrarily many coalitions. The oddness disappears, as does the requirement that one particular named player be matched. For the weighted-median utility proposed by the other analyst,
\[ u_\theta(\lambda z)=u_\theta(z) \]
for every \(\lambda>0\). Thus any improving coalition can be shrunk to an arbitrarily small positive mass. The finite packing problem at the heart of the reduction has vanished.
The obvious repair is to clone every reduction vertex into a large cohort while retaining the whole compatibility matrix at type level. But then the reduction requires one distinct type for essentially every named vertex: identifying two vertices as one type would require them to have identical values toward every other vertex and identical adjacency relations. The type space therefore retains the entire arbitrary graph. Worse, a “friend” type now represents many friends, so the paper’s condition that each agent has at most four friends no longer has the same meaning. To recover the nine-cycle argument one must prohibit splitting cohorts or preserve individual atoms, which restores a finite hedonic game rather than a continuous population.
There is also a computational gap in the proposed formulation. An outcome is not naturally a finite list of coalition vectors. A measurable partition may induce an arbitrary distribution over coalition compositions, and the paper gives no bound on the number of coalition types needed in a stable outcome. Without such a bound or an explicit representation of the partition, “does a stable outcome exist?” is not yet a finite computational problem. Imposing bounded support, whole-type coalitions, or minimum coalition masses would make it computable, but each imposes new structure not present in the paper.
This is a serious objection to the stated mirror, but not a decisive universal objection. A large organization with recurring compatibility types is a plausible high-multiplicity setting, and asking whether fractional cloning restores core stability could itself be worthwhile. The honest negative conclusion is therefore weak: the paper’s particular hardness mechanism does not survive the natural atomless median limit, and the proposed mirror is under-specified computationally, but I cannot defend the stronger claim that no repaired continuous median-core problem would be worthwhile.
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.