| paper | d4-conf-atal-2015-0289 |
| 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→P discrete result → its continuous mirror
Answer: The existence decision problem is in \(\mathrm{P}\). Every valid input admits a core-stable mass partition with at most \(\tau\) nonzero coalition vectors. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 5(i)
Given a finite type set \(T\), rational masses \(\mu_t\ge 0\) summing to \(1\), and a symmetric rational affinity matrix \(w_{ts}=w_{st}\), decide whether there is a countable family of nonzero coalition mass vectors \(x^j\in\mathbb{R}_{\ge 0}^{T}\) and isolated mass \(\sigma_t\ge 0\), with \(\sigma_t+\sum_j x_t^j=\mu_t\), such that no nonzero composition \(y\in\mathbb{R}_{\ge 0}^{T}\) can be formed from positive masses of every type \(t\) with \(y_t>0\) whose current utility is strictly below \(u_t(y)=\frac{\sum_s w_{ts}y_s}{\sum_s y_s}\). Is such a core-stable mass partition guaranteed to exist?
Types are complete affinity profiles; the input gives each type’s rational population share \(\mu_t\) and the symmetric rational values \(w_{ts}\). A partition assigns mass to coalition compositions \(x^j\), with isolated mass receiving utility \(0\); a blocking composition \(y\) requires positive underperforming mass of every type in its support and gives type \(t\) utility \(u_t(y)=\frac{\sum_s w_{ts}y_s}{\sum_s y_s}\). The question is whether a partition with no such blocker exists.
The mirror covers core existence for symmetric fractional hedonic games, anchored by Theorem 5(i). It leaves aside the paper’s Nash-stability, individual-stability, strict-preference, and other existence results.
The lead mirror I believe in is core existence for a continuum of symmetric fractional hedonic agents, in the paper’s own party-formation setting. A large electorate can have millions of people but relatively few complete affinity profiles: two agents have the same type only if they value every type of potential coalition partner identically. Let \(T\) be those types, let \(\mu_t\in\mathbb{Q}_{\ge 0}\) be each type’s population share, and let \(w_{ts}=w_{st}\) be the value a type-\(t\) agent assigns to another type-\(s\) agent. As in the paper, an agent’s value for themself is zero.
A continuous coalition partition is a countable family of population-mass vectors \(x^1,x^2,\ldots\in\mathbb{R}_{\ge0}^{T}\), together with isolated mass \(\sigma_t\ge0\), such that
\[
\sigma_t+\sum_j x_t^j=\mu_t \qquad(t\in T).
\]
Here \(x_t^j\) is the mass of type \(t\) in coalition \(j\), and each person belongs to one coalition or is alone. A type-\(t\) member of coalition \(x\) receives the limiting fractional-hedonic utility
\[
u_t(x)=\frac{\sum_{s\in T}w_{ts}x_s}{\sum_{s\in T}x_s};
\]
isolated agents receive utility \(0\). The question is whether such a partition exists with no blocking coalition. Precisely, a proposed composition \(y\) blocks if, for every \(t\) with \(y_t>0\), there is positive mass of type \(t\) currently receiving less than \(u_t(y)\). Because the population is atomless, the proposed coalition can take a sufficiently small amount of that mass in each type while preserving \(y\)’s proportions. A solution is a partition with no such \(y\). This is an existence question, with no separate objective.
The anchor is Theorem 5(i): \(\mathrm{SYMMFHG\text{-}CS}\) is NP-hard—given a symmetric fractional hedonic game, deciding whether it admits a core-stable partition is NP-hard. The paper proves this result here; its surrounding discussion says the core-stability construction adapts Sung and Dimitrov’s construction [20]. The mirror asks the corresponding existence question after replacing the finite electorate by type masses and coalition compositions by population masses.
The scenario is plausible because the paper itself motivates symmetric valuations by political parties whose members value one another according to ideological distance. In a population-scale party system, many people can share one complete affinity type, while each party contains substantial population mass. The mass vectors express how much of each type joins each party; party membership remains a partition of the population. My mirror covers this symmetric core-existence result only. It does not claim to cover the paper’s Nash-stability, individual-stability, or strict-preference results.
My first expectation is Class A, tractable, for this mass model: coalition utilities depend on normalized compositions in a finite-dimensional simplex, and population balance is expressed directly in type masses. That makes convex feasibility or column-generation methods a plausible route. The hard part would be turning the strict blocking tests and possibly countably many coalitions into a finite optimization problem; I am proposing a research question, not asserting that an LP already solves it. Useful next questions are whether stable mass partitions always exist for symmetric FHGs, whether a stable partition can always be represented with finite support, and whether the answer can be computed in time polynomial in \(|T|\) and the input bit length.
The weakest point is that the paper’s hardness construction is organized around individual vertices and an exact-cover gadget; the authors do not establish hardness when many vertices share a complete type. Also, this mirror concerns population-scale coalitions. If the relevant groups remain small as the population grows, their mass vanishes and this model may not capture their stability. Those limits mean the discrete hardness is an anchor for the question, not evidence that hardness transfers to this particular continuum.
The strongest case against this anchor is that the paper’s hardness result does not establish hardness in a high multiplicity regime. Theorem 5(i) is NP-hardness for finite symmetric games whose input is a graph of named agents. It does not show that the reduction still works when many agents share a complete affinity type, or when the input is just rational type masses and a symmetric type-affinity matrix. So the discrete theorem gives little reason to expect hardness for the continuous problem. The proponent’s proposed LP route is also only a conjecture: atomless blocking lets a coalition peel arbitrarily small positive mass from each underperforming type, and the paper gives no finite-support certificate or optimization formulation for that condition.
That is a real limitation on the anchor’s force, but it does not defeat the better mirror. Given rational \(\mu_t\) and symmetric \(w_{ts}\), deciding whether a population can be partitioned into coalition masses with no feasible positive-mass blocker is a well-defined computational question. The paper’s political-party example supplies a plausible setting: people with the same ideological position can share the same affinity profile, and a party can contain substantial mass of each type. The discrete reduction need not survive; finding out what happens under that structured type model is the point. The fact that finite-agent FHG research has also studied size- and gain-relaxed core notions shows that blocker semantics can vary, but that work does not make the population continuous or answer this question ([IJCAI 2021](https://www.ijcai.org/proceedings/2021/26)).
So my negative case is weak where it has to be strongest. It can say the NP-hardness theorem is not evidence that this mirror inherits hardness, and that the atomless core needs a precise representation before the proposed algorithmic direction is credible. It cannot honestly say the question is not worth asking: the population-scale type model is sensible, the paper contains a named computational result about core existence, and the paper’s own application fits the model. I cannot defeat this anchor across all plausible scenarios.
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.