| paper | Welfare Maximization in Fractional Hedonic Games |
| authors | H. Aziz, Serge Gaspers, Joachim Gudmundsson, Julián Mestre, H. Täubig |
| venue | IJCAI 2015 |
| filed under | coalition · hedonic |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\text{-hard}\) · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 3
statement extracted from the paper’s text layer
Given a finite type set \(T\) with \(|T|=\tau\), a symmetric binary affinity matrix \(A\in\{0,1\}^{\tau\times\tau}\), and rational masses \(\mu\in\Delta_\tau\), choose coalition compositions \(p^j\in\Delta_\tau\) and masses \(s_j\ge0\) with \(\sum_j s_j=1\) and \(\sum_j s_jp^j=\mu\), maximizing \(\sum_j s_j(p^j)^\mathsf{T}Ap^j\).
A high-multiplicity block FHG has repeated affinity types \(t\in T\), population masses \(\mu_t\), and coalitions of mass \(s_j\) and composition \(p^j\); type \(t\) receives utility \((Ap^j)_t\), with utilitarian welfare \(\sum_j s_j(p^j)^\mathsf{T}Ap^j\).
The best surviving objection is that atomless splitting removes the integral triangle-partition witness, while egalitarian welfare requires an explicit essential-minimum convention and treatment of types with \(\mu_t>0\); no rounding or convergence theorem is supplied.
fatal: False
It covers the simple-symmetric hardness results in Theorems 3 and 4, including utilitarian, egalitarian, and normalized Nash variants; it leaves the matching-based approximation algorithms in Theorems 5–8 unaddressed.
The strongest positive case is a high-multiplicity version of the paper’s own simple symmetric FHG, with Theorem 3 as the lead anchor and Theorem 4 as a useful second anchor. The paper itself is not already continuous: its agents are individually named vertices of a finite graph, whereas the mirror replaces repeated vertices by masses of interchangeable types.
A type \(t\) is an affinity profile: every agent of type \(t\) has the same binary valuation for every type \(t'\), including the same valuation for other agents of type \(t\). Thus the type-level instance is a symmetric matrix \(A\in\{0,1\}^{\tau\times\tau}\), where \(A_{tt'}=1\) means that an agent of type \(t\) values an agent of type \(t'\). The society is a rational distribution \(\mu\in\mathbb{Q}^{\tau}_{\ge 0}\) with \(\sum_t\mu_t=1\). The intended regime is \(n\) very large and \(\tau\ll n\): for example, millions of participants in a recurring discussion, matching, or clustering system whose mutual compatibility is determined by a few dozen or hundred interest/role profiles.
A continuum coalition is a measurable set of agents. It is represented by its mass \(s_j\) and its type composition \(p^j\in\Delta_\tau\), with \(\sum_j s_j=1\) and \(\sum_j s_jp^j=\mu\). An individual of type \(t\) in coalition \(j\) receives utility \(u_t^j=(Ap^j)_t\). This is not fractional membership: each infinitesimal agent belongs to one coalition; only a mass of interchangeable agents can be divided among coalitions. The diagonal entry \(A_{tt}\) records compatibility with other agents of the same type, while the agent’s own self-interaction has measure zero.
My lead problem is Continuous Simple-Symmetric FHG Welfare. Its input is \((A,\mu,W)\), where \(W\) is either utilitarian or egalitarian welfare. Its output is a finite coalition decomposition \(\{(s_j,p^j)\}\) maximizing the selected objective. For utilitarian welfare the value is \(\sum_j s_j\sum_t p_t^j(Ap^j)_t\). For egalitarian welfare it is \(\min_{j,t:p_t^j>0}(Ap^j)_t\). This is a direct population continuization of the paper’s underlying partition problem: the denominator in the original average utility becomes coalition mass, while the decision remains a partition of the population.
The lead anchor is Theorem 3, proved in this paper. It states: “For simple symmetric FHGs, UTILITARIAN WELFARE and EGALITARIAN WELFARE are both NP-hard.” The proof reduces from PARTITIONINTOTRIANGLES, which remains NP-complete for 3-partite graphs with the three independent sets specified. A triangle partition gives every vertex utility \(2/3\), hence total utilitarian welfare \(2n/3\). The paper proves that no coalition can have average utility above \(2/3\), with equality only when its three parts are balanced and induce a complete tripartite graph; such a coalition can itself be divided into triangles. The same argument gives NP-hardness for egalitarian welfare.
The continuous question is genuinely interesting because that reduction’s decisive combinatorics is individual indivisibility. In the blow-up graph, each original vertex becomes a large population of identical agents. In the continuum, its mass may be split between coalitions. The integral triangle-partition question can therefore become a fractional exact-decomposition question. In the particular threshold construction from Theorem 3, balanced complete tripartite coalitions can be decomposed into infinitesimal triangle configurations, suggesting that the original NP-hardness may dissolve into a configuration LP.
For utilitarian welfare, the continuous problem can be written as an LP over distributions of coalition compositions: maximize \(\int_{\Delta_\tau}p^\mathsf{T}Ap\,d\lambda(p)\), subject to \(\int p\,d\lambda(p)=\mu\) and \(\lambda(\Delta_\tau)=1\). Its pricing problem is essentially \(\max_{p\in\Delta_\tau}\{p^\mathsf{T}Ap-\ell\cdot p\}\). Thus the mirror exposes precisely the programme’s intended question: does population continuization make the configuration LP tractable, or does the type-level graph still make pricing hard? My expectation is an A/C boundary rather than automatic hardness transfer: structured type-affinity graphs may admit polynomial algorithms, while unrestricted \(A\) is a plausible continuum-specific-hardness candidate. The discrete triangle reduction alone does not establish Class B.
The second anchor is Theorem 4, also proved here. It states: “For simple symmetric FHGs, NASH WELFARE is NP-hard.” The same triangle reduction is used. A triangle partition has Nash product \((2/3)^n\); the arithmetic–geometric mean inequality shows that no coalition can have geometric mean utility above \(2/3\), with equality again forcing the balanced complete-tripartite structure.
Its continuous counterpart is Continuous Nash FHG Welfare on the same input \((A,\mu)\). The natural high-multiplicity objective is the normalized Nash welfare, namely \(\exp\!\left(\sum_j s_j\sum_{t:p_t^j>0}p_t^j\log((Ap^j)_t)\right)\), with value \(0\) if a positive-mass set of agents receives zero utility. Taking the \(n\)-th root does not change the finite problem’s optimizer, and this normalized logarithmic form is exactly the limit of the discrete Nash product under population replication. Again, the theorem’s integral triangle argument need not survive: fractional masses may realize the same \(2/3\) threshold without an integral triangle partition. The general continuous Nash problem may still be difficult because its configuration objective is nonlinear, but the expected source of hardness is now the type-affinity geometry or pricing problem, not merely the number of agents.
The authors should recognize these as their problems. Their paper explicitly motivates FHGs by agents seeking to maximize average agreement with coalition members, and its simple symmetric restriction is already an unweighted undirected type-affinity model. A large population of people with repeated interest or institutional profiles is a credible high-multiplicity regime: \(n_t/n\) converges to \(\mu_t\), and the finite blow-up graph converges to the stated continuum problem. This is not outcome-space continuity or a probabilistic social-choice construction; the continuous object is the population itself.
The weakest point is the regime’s realism for arbitrary networks. A generic social network has idiosyncratic edges, so its number of genuine types may be close to \(n\), making the mirror unhelpful. The positive case therefore covers the repeated-profile/block-network regime, not every FHG instance. That concession does not destroy the mirror: the paper’s own application is average-agreement clustering, where repeated affinity profiles are natural, and the programme only requires one convincing instance regime. The resulting questions are whether the utilitarian and Nash configuration-pricing problems are tractable for natural type graphs, whether the triangle reduction becomes a fractional LP exactly, and what rounding theorem connects the continuous optimum back to large finite blow-ups.
The strongest negative case is that the proposed mirror quietly changes the paper’s object. In a symmetric FHG, a type must preserve an agent’s valuation of every other agent. Thus two agents of the same type are graph-theoretic twins: they have identical neighbourhoods, including the same relation to every other type. A generic social network has essentially no such multiplicities. The paper’s reductions deliberately use individually distinguished vertices.
This creates a dilemma. If \(\tau\ll n\), the instance is a highly structured blow-up of a small quotient graph, and the paper’s triangle-partition reduction no longer represents the same combinatorial phenomenon: the hard choices were among distinct vertices, not among many copies of a few profiles. If \(\tau\) grows with the reduction, then each original vertex becomes its own type. Replicating it many times gives a legitimate limit, but the “continuum” has added only divisible copies of an already explicit graph; it has not exposed a population-level structure in the paper’s network-clustering problem.
This weakens Theorem 3 as an anchor. Its triangle argument is about integral membership in triples. In the proposed continuum, a type’s mass can be divided among arbitrarily many coalitions, and the threshold \(2/3\) becomes a fractional decomposition condition. The resulting problem may be interesting, but it is no longer a continuous version of the theorem’s decisive question; it is a new fractional optimization problem on a quotient graph. The utilitarian formulation confirms this: \(\int p^{\mathsf T}Ap\,d\lambda(p)\) is an infinite linear program in the measure \(\lambda\), but its pricing problem is a quadratic optimization over the simplex, and its output is a distribution of coalition compositions rather than a network clustering with identifiable members.
The egalitarian anchor is even less stable as a limit. In the finite problem, every named vertex contributes to the minimum. In the atomless model, a vanishing exceptional population disappears from the objective, while a positive but arbitrarily small type remains fully relevant. Different sequences of finite blow-ups can therefore have the same limiting distribution but different worst-off-agent behaviour. One can repair this by fixing positive type masses and using an essential minimum, but that is a substantive modelling choice rather than something supplied by the paper.
Theorem 4 does not rescue the negative case. The raw Nash product collapses to zero over an infinite population, but the normalized geometric mean,
\[
\exp\!\left(\sum_j s_j\sum_t p_t^j\log((Ap^j)_t)\right),
\]
is a sensible high-multiplicity repair and does preserve the finite optimizer under replication. Likewise, a block-structured population with repeated compatibility profiles is not mathematically absurd. It could support a genuine continuum problem.
That concession is decisive against a universal negative verdict. The paper has named computational results, the proposed typed blow-up has a coherent finite-to-continuous bridge, and high-multiplicity FHGs are not already covered by the paper. The negative case can show that the proponent overstates how naturally the model represents ordinary social networks, and that Theorem 3’s particular hardness proof does not automatically survive. It cannot honestly show that no worthwhile mirror exists. Under the programme’s rules, these anchors should therefore be treated as surviving unless ChoCo excludes block-structured or repeated-profile network populations on application-specific grounds.
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.