| paper | Stable Outcomes in Modified Fractional Hedonic Games |
| authors | G. Monaco, Luca Moscardelli, Yllka Velaj |
| venue | ATAL 2018 |
| filed under | coalition · hedonic |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: \(\mathrm P\) · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 5
statement extracted from the paper’s text layer
Given a finite type set \(T\), rational masses \(\mu\in\mathbb{Q}_{\ge 0}^{T}\) summing to \(1\), and a symmetric \(0\)-\(1\) affinity matrix \(w\), choose a finite-support family of nonnegative masses \(\lambda_q\) for coalition templates \(q\in\mathbb{N}^{T}\setminus\{0\}\) satisfying \(\sum_q\lambda_q q_t=\mu_t\) for every \(t\), where \(u_t(q)=0\) if \(\lVert q\rVert_1=1\) and \(u_t(q)=(\sum_s q_s w_{ts}-w_{tt})/(\lVert q\rVert_1-1)\) otherwise; maximize \(\sum_q\lambda_q\sum_t q_tu_t(q)\).
A high-multiplicity finite-coalition-copy model: types are complete affinity profiles, \(\mu_t\) is the mass of type \(t\), and \(\lambda_q\) is divisible mass of copies of an integral coalition template \(q\). The objective is total modified-fractional welfare; for \(0\)-\(1\) \(w\), Theorem 3 reduces templates to \(K_1\), \(K_2\), and \(K_3\), yielding a polynomial-size LP.
The mirror covers Theorem 5's unweighted welfare optimization and Theorem 18's weighted \(1/2\)-approximate core-stable construction; it leaves the strong-Nash existence and price results, Nash dynamics and price bounds, strict-core impossibility, and the remaining core price bounds untouched.
The strongest positive case is a mirror of Theorem 5, with Theorem 18 as a second, independent anchor. The paper contains no numbered NP-hardness theorem of its own, so I would not manufacture a hardness anchor from the cited related work.
The natural high-multiplicity regime is a large population divided into a small number \(\tau\) of affinity types. A type records the complete interaction vector \(w_{t,\cdot}\), including its interaction with other members of the same type. Thus agents of one type are interchangeable in every respect used by the game. The population is \(\mu\in\mathbb{Q}^{\tau}\), where \(\mu_t\) is the fraction of agents of type \(t\), and \(\tau\ll N\). This is plausible for large communities, parties, workplaces, or social groups with finitely many compatibility categories. It is not a claim that every arbitrary graph is high-multiplicity; it is a claim about the block-structured instance regime.
The exact population-to-finite dictionary is straightforward. If \(\mu_t=n_t/N\), then the finite game has \(n_t\) interchangeable agents of type \(t\). Conversely, a finite type-homogeneous game normalized by \(N\) gives \(\mu\). A type is therefore not merely a preference label: it includes the whole affinity profile, as required by the programme’s definition of high multiplicity.
My lead anchor is Theorem 5, proved in this paper. It states: given an unweighted graph \(G\), there is a polynomial-time algorithm computing a coalition structure \(\mathcal C^*\) maximizing social welfare. The proof uses Theorem 3, also proved here, which says that every coalition structure can be replaced by one containing only \(K_1\), \(K_2\), and \(K_3\) coalitions without decreasing welfare, and Theorem 4, cited from Hell (1984), which gives a polynomial-time algorithm for the corresponding \(K_1/K_2/K_3\) partition problem.
I would mirror it with the following problem, Continuous Maximum-Welfare MFHG. An instance consists of a finite type set \(T\), rational masses \(\mu_t\), and a symmetric \(0\)-\(1\) compatibility matrix \(w\). A coalition template is a nonzero vector \(q\in\mathbb N^\tau\); \(q_t\) is the number of type-\(t\) agents in that coalition. Let \(\lVert q\rVert_1\) be its size, and define the utility of a type-\(t\) member by
\[ u_t(q)= \begin{cases} 0,&\lVert q\rVert_1=1,\\[2mm] \dfrac{\sum_s q_s w_{ts}-w_{tt}}{\lVert q\rVert_1-1},&\lVert q\rVert_1\ge2. \end{cases} \]
A continuous outcome is a finite-support collection of nonnegative masses \(\lambda_q\), where \(\lambda_q\) is the normalized amount of population assigned to coalition copies of template \(q\), satisfying
\[ \sum_q \lambda_q q_t=\mu_t \]
for every type \(t\). Its welfare is
\[ \operatorname{SW}(\lambda)= \sum_q \lambda_q\sum_t q_tu_t(q). \]
The problem is to output a feasible \(\lambda\) maximizing \(\operatorname{SW}(\lambda)\).
This is genuinely a population mirror: \(\mu\) is the continuous object, while every individual mass unit still belongs to an ordinary finite coalition template. We are not making outcomes or preferences probabilistic. For rational \(\mu\), multiplying all \(\lambda_q\) by a common denominator gives an actual finite high-multiplicity game.
I expect this problem to be Class A. The continuous analogue of Theorem 3 should reduce every template to \(K_1\), \(K_2\), and \(K_3\) templates. The resulting problem is a finite LP with variables for compatible pairs, compatible triangles, and singletons:
\[ \max \sum_{q\in\mathcal B_2\cup\mathcal B_3}\lVert q\rVert_1 z_q \]
subject to
\[ \sum_{q\in\mathcal B_1\cup\mathcal B_2\cup\mathcal B_3}q_tz_q=\mu_t,\qquad z_q\ge0. \]
There are only polynomially many such type templates, \(O(\tau^3)\), so this is polynomial in \(\tau\) and the encoding length of \(\mu\). The paper’s structural insight is therefore not merely preserved; it becomes visibly a fractional packing formulation.
The second anchor is Theorem 18, proved in this paper. It states that for every weighted graph \(G=(N,E,w)\), there is a polynomial-time algorithm computing a core-stable coalition structure \(\mathcal C\), all of whose coalitions have cardinality at most \(2\), such that
\[ \operatorname{SW}(\mathcal C)\ge \frac12\operatorname{SW}(\mathcal C^*(\ga(G))). \]
This includes arbitrary edge weights, including negative ones.
Its continuous counterpart is Continuous Core Pairing. The instance is a type population \((T,\mu,w)\) as above. The output must be a coalition allocation \(\lambda\) supported only on singleton and pair templates. It must be core-stable against all finite coalition templates: there must not exist a template \(q\) such that, for every type \(t\) with \(q_t>0\), a positive mass of type-\(t\) agents currently receive utility strictly below \(u_t(q)\). Equivalently, writing
\[ L_t(v)=\sum_{r:u_t(r)<v}\lambda_r r_t, \]
the allocation is core-stable if no \(q\) satisfies \(L_t(u_t(q))>0\) for every type used by \(q\). The required welfare guarantee is
\[ \operatorname{SW}(\lambda)\ge \frac12\operatorname{OPT}(\mu,w), \]
where \(\operatorname{OPT}\) ranges over all feasible coalition-template allocations.
I also expect this to be Class A, though less confidently than the first problem. The proof strategy of Theorem 18 is already a greedy maximum-edge matching argument. In the high-multiplicity setting, one can consume divisible amounts of the currently heaviest compatible type pair, leave unmatched mass single, and obtain a pair-supported allocation. The core argument should lift because a positive-mass blocking template can be instantiated by sufficiently many identical finite coalitions. The approximation charging argument likewise has a natural mass version.
The authors should recognize both questions as their problems. They retain the same agents, symmetric affinity weights, modified fractional utility, coalition partitions, social welfare, and core notion. The only change is that many interchangeable agents are represented by their mass and that counts of identical coalition patterns become divisible. The mirror covers the welfare-optimization result of Theorem 5 and the stable approximation result of Theorem 18; it does not claim to cover every theorem in the paper.
The weakest point is coalition granularity. The paper’s original coalitions are finite, whereas an atomless population invites a different definition based on averaging over coalition mass. That alternative could change both utilities and stability, so I would not silently use it. The finite-template formulation above is deliberately conservative: it is the normalized limit of many replicated finite coalitions and preserves the paper’s exact utility formula. The remaining limitation is that arbitrary individual-specific graphs do not admit a useful small type space. That is a real boundary, but it is a boundary of the instance regime rather than a reason the mirror is conceptually invalid.
Natural follow-up questions include whether the continuous analogue of Theorem 6—optimal strong Nash stability—remains tractable, whether the weighted version of Continuous Maximum-Welfare MFHG is polynomial, and whether the continuous core price of anarchy has constants corresponding to Theorems 22 and 23.
The strongest negative argument is that the proposed continuum is not really an atomless MFHG. The paper’s utility is defined for a finite coalition, with denominator \(|C|-1\). In a genuinely atomless population, an individual has measure zero, so the natural utility becomes something like
\[
u_t(x)=\frac{\sum_s x_s w_{ts}}{\sum_s x_s},
\]
and the paper’s \(K_1/K_2/K_3\) structure no longer has an obvious meaning. The proponent’s finite-template model avoids this by retaining ordinary finite coalitions and making only their number divisible. Thus \(\lambda_q\) is arguably fractional bookkeeping over coalition copies, rather than a continuous society whose members form mass coalitions.
The core anchor has an additional difficulty. In the finite game, one coalition containing even a single agent can block. In an atomless population, that coalition has measure zero. The proposed condition \(L_t(u_t(q))>0\) therefore silently changes the core: it requires a positive mass of dissatisfied agents and discards finite blocking coalitions. One could instead define blocking by positive mass vectors, but that is a new stability concept, not an automatic continuation of the paper’s core. Different choices produce genuinely different questions.
These objections do weaken the exact formulations offered, but they do not defeat the best mirror. The programme explicitly permits integral bundles received by mass units, so a continuum of finite coalition copies is a legitimate high-multiplicity model. More importantly, Theorem 3 lifts exactly: a finite type-homogeneous blow-up has the same decomposition into \(K_1\), \(K_2\), and \(K_3\) templates, and rational template masses can be scaled to finite instances. Theorem 5 therefore yields a genuine continuous population-capacity problem, not merely outcome-space continuity. The fact that its LP has only \(O(\tau^3)\) variables is a tractability result, not a modelling defect.
Theorem 18 is harder to dismiss. The greedy maximum-edge argument has a natural divisible version: repeatedly consume the maximum-weight available mass of a compatible type pair. Agents in an earlier pair receive their maximum attainable utility relative to all remaining types, so no positive-mass blocking template can contain them; the paper’s charging argument also has a direct mass analogue. Type splitting across several partners is handled by tracking the dissatisfied mass \(L_t\). This is a sensible continuous core question even though its answer may be easy.
Consequently, I cannot honestly sustain the requested universal negative. The finite-template formulation should be presented carefully as a high-multiplicity continuum of finite coalitions, and its core notion should be justified explicitly. But Theorems 5 and 18 both have credible population mirrors, with plausible type-homogeneous scenarios and named computational content. The negative case exposes modelling choices; it does not show that no worthwhile continuous mirror 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.