Answer: \(\mathrm P\)
Theorem 5 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateGiven an unweighted graph $G$, there exists a polynomial time algorithm for computing a coalition structure $\outcome^*$ maximizing the social welfare.
statement extracted from the paper’s text layer; consult the paper for the exact wording
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 society is given by its support: a nonempty list \(T\) of \(\tau\) types with positive binary rational masses \(\mu_t\), summing to \(1\). Here \(\tau\) is the support size, not the number of possible types.
The input includes a symmetric matrix \(w\in\{0,1\}^{T\times T}\) and a binary rational threshold \(B\). The entry \(w_{tt}\) describes affinity between distinct members of type \(t\), not self-affinity.
A coalition template is any \(q\in\mathbb Z_{\geq0}^{T}\setminus\{0\}\), with no bound on its size \(k=\sum_tq_t\). For each represented type \(t\), define \(u_t(q)=0\) when \(k=1\), and \(u_t(q)=(\sum_s q_sw_{ts}-w_{tt})/(k-1)\) otherwise.
An allocation is a finitely supported family \(\lambda_q\in\mathbb R_{\geq0}\) satisfying \(\sum_q\lambda_qq_t=\mu_t\) for every \(t\). Its welfare is \(W(\lambda)=\sum_q\lambda_q\sum_{t:q_t>0}q_tu_t(q)\); no stability constraint is imposed.
Is deciding whether such an allocation satisfies \(W(\lambda)\geq B\) in \(\mathrm P\), with running time polynomial in \(\tau\) and the total input bit length \(L\), or is it \(\mathrm{NP}\)-hard?
For finite agents on unweighted undirected graphs, unconstrained welfare maximization in modified fractional hedonic games is polynomial-time solvable ([Monaco, Moscardelli and Velaj](https://www.isi.it/wp-content/uploads/2024/01/stable-outcomes-in-modified-fractional-hedonic-games_Velaj.pdf)).
No result settling this exact mass-template problem was identified in the literature search.
The decision problem is in \(\mathrm P\), with running time polynomial in \(\tau\) and the total input bit length \(L\). Every allocation can be replaced by one using only singleton and two-member templates, preserving both its type masses and its welfare exactly.
Enumerate the types as \(T=\{1,\ldots,\tau\}\), and write \(e_t\) for the unit vector of type \(t\). Let \(F(q)\) denote the welfare contributed by one unit of template \(q\).
A singleton satisfies \(F(e_t)=0\). For a template of size \(k=\sum_tq_t\geq2\), the given utility definition yields
\(\displaystyle F(q)=\frac{\sum_{t,s}q_tq_sw_{ts}-\sum_tq_tw_{tt}}{k-1}.\)
Using symmetry of \(w\), this becomes
\(\displaystyle F(q)=\frac{2\sum_{t<s}q_tq_sw_{ts}+\sum_tq_t(q_t-1)w_{tt}}{k-1}.\)
For \(t\leq s\), define the two-member template \(p^{ts}=e_t+e_s\). Thus \(p^{tt}=2e_t\). Both members of \(p^{ts}\) have utility \(w_{ts}\), including when they are distinct members of the same type. Consequently,
\(\displaystyle F(p^{ts})=2w_{ts}.\)
Lemma. For every template \(q\) of size at least two, there exist nonnegative rational coefficients \(a_{ts}(q)\) such that
\(\displaystyle q=\sum_{t\leq s}a_{ts}(q)p^{ts}\qquad\text{and}\qquad F(q)=\sum_{t\leq s}a_{ts}(q)F(p^{ts}).\)
Proof. Set
\(\displaystyle a_{ts}(q)=\frac{q_tq_s}{k-1}\quad(t<s),\qquad a_{tt}(q)=\frac{q_t(q_t-1)}{2(k-1)}.\)
These coefficients are nonnegative because each \(q_t\) is a nonnegative integer.
The mass of type \(t\) in the proposed replacement equals
\(\displaystyle 2a_{tt}(q)+\sum_{s<t}a_{st}(q)+\sum_{s>t}a_{ts}(q)=\frac{q_t(q_t-1)+q_t\sum_{s\ne t}q_s}{k-1}=q_t.\)
Here a same-type pair consumes two units of type \(t\), while every other incident pair consumes one. Thus all type masses are preserved.
Its welfare equals
\(\displaystyle \sum_{t\leq s}2w_{ts}a_{ts}(q)=\frac{2\sum_{t<s}q_tq_sw_{ts}+\sum_tq_t(q_t-1)w_{tt}}{k-1}=F(q).\)
This proves both identities. \(\square\)
Now take any allocation \(\lambda\) allowed by the question. Keep its singleton templates, and replace each larger template \(q\) by the mixture from the lemma, multiplied by \(\lambda_q\). The original support is finite, so all resulting sums are finite. The replacement uses only the \(\tau\) singleton templates and the \(\tau(\tau+1)/2\) two-member templates.
By the two identities in the lemma, the replacement satisfies every mass equality and has exactly the original welfare.
Introduce nonnegative variables \(z_t\) for singleton templates \(e_t\), and \(x_{ts}\) for two-member templates \(p^{ts}\), where \(t\leq s\).
The required decision is exactly feasibility of the following rational linear system:
\(\displaystyle z_t+2x_{tt}+\sum_{s<t}x_{st}+\sum_{s>t}x_{ts}=\mu_t\qquad(t\in T),\)
\(\displaystyle 2\sum_{t\leq s}w_{ts}x_{ts}\geq B,\)
\(\displaystyle z_t\geq0,\qquad x_{ts}\geq0.\)
For completeness, both directions of this equivalence hold:
In particular, the reduction preserves equality at the threshold; it does not merely preserve a supremum.
The system has \(\tau+\tau(\tau+1)/2\) variables, \(\tau\) mass equalities, and one welfare inequality, besides nonnegativity constraints. Every matrix coefficient belongs to \(\{0,1,2\}\). Its rational right-hand sides are precisely the input masses and threshold. The system therefore has encoding length polynomial in \(\tau\) and \(L\).
The standard polynomial-time theorem for rational linear-programming feasibility applies to this finite, explicitly encoded system. It decides feasibility exactly in time polynomial in its encoding length, establishing the claimed running time.
There is also an attained welfare maximum. Indeed, the mass equalities are feasible by choosing \(z_t=\mu_t\) and all pair variables zero. Summing those equalities gives
\(\displaystyle \sum_tz_t+2\sum_{t\leq s}x_{ts}=1.\)
Together with nonnegativity, this bounds every variable. The feasible set for welfare maximization is consequently nonempty, closed, and bounded, so its linear objective attains a maximum. Section 2 shows that this is also the maximum over all allowed allocations, despite their unbounded template sizes.
The decisive feature is the permission to split mass fractionally among templates. Overlapping pairs can thereby replace a larger coalition while preserving its average-affinity welfare. This argument directly settles the mass-template problem; it does not require transferring the cited [finite-agent theorem of Monaco, Moscardelli and Velaj](https://www.isi.it/wp-content/uploads/2024/01/stable-outcomes-in-modified-fractional-hedonic-games_Velaj.pdf).
⟨structured verdict parsed — rendered above⟩
The prover’s argument is correct and resolves the stated mass-template problem in \(\mathrm P\). The exact replacement lemma is valid, the resulting linear program is equivalent to the original decision problem, and its encoding has polynomial size. No major or minor issues were found.
For a singleton, the definition gives \(F(e_t)=0\).
For \(k\geq2\), summing the utilities with multiplicities gives
\[
F(q)=\frac{\sum_{t,s}q_tq_sw_{ts}-\sum_tq_tw_{tt}}{k-1}.
\]
Terms with \(q_t=0\) contribute zero, so including unrepresented types in these sums is legitimate. Symmetry combines the off-diagonal terms into
\[
2\sum_{t<s}q_tq_sw_{ts},
\]
and the diagonal contribution after subtraction is
\[
\sum_tq_t(q_t-1)w_{tt}.
\]
Both displayed welfare formulas are correct.
For \(p^{ts}=e_t+e_s\), each member has exactly one other member. Its utility is \(w_{ts}\), including when \(t=s\), because the task explicitly interprets \(w_{tt}\) as affinity between distinct members of that type. Thus \(F(p^{ts})=2w_{ts}\) is correct.
The coefficients are well-defined because \(k-1>0\). They are rational and nonnegative: in particular, \(q_t(q_t-1)\geq0\) for every nonnegative integer \(q_t\).
The type-\(t\) mass calculation is correct:
\[
2a_{tt}(q)+\sum_{s<t}a_{st}(q)+\sum_{s>t}a_{ts}(q)
=\frac{q_t(q_t-1)+q_t(k-q_t)}{k-1}
=q_t.
\]
The factor of two for a same-type pair is necessary and is included correctly.
Multiplying each coefficient by the corresponding pair welfare gives exactly the previously computed expression for \(F(q)\). Hence the lemma preserves both mass and welfare, with no inequality or limiting argument.
Applying the lemma to an allocation is legitimate even when its coefficients \(\lambda_q\) are arbitrary nonnegative real numbers. Multiplication by the rational replacement coefficients preserves nonnegativity. Because the original allocation has finite support and each replacement uses finitely many pairs, all sums remain finite. Repeated occurrences of a pair can be combined into one coefficient.
The mass constraints correctly count singleton mass, twice the coefficient of a same-type pair, and once the coefficient of each incident mixed-type pair. The threshold expression correctly assigns welfare \(2w_{ts}\) to each pair.
Both implications are established:
Thus feasibility is equivalent to the requested existential decision, including equality at the threshold. No assumption about rationality of the original allocation or attainment of a supremum is needed for this equivalence.
The variable count is \(O(\tau^2)\), and the number of constraints, including nonnegativity, is polynomial in \(\tau\). Even a dense encoding of the constraint matrix has polynomial size. All matrix coefficients are small integers, while the right-hand sides are the given binary rationals.
The invoked rational linear-programming theorem states that feasibility of a finite, explicitly encoded rational linear system is decidable in time polynomial in its binary encoding length. Its hypotheses are satisfied here. This theorem provides exact feasibility decisions, so the argument does not depend on numerical tolerance at \(B\).
Consequently, the claimed running time polynomial in \(\tau\) and \(L\) follows.
The attainment argument correctly concerns the mass-constrained feasible set before adding a welfare threshold. The singleton allocation proves this set nonempty. Summing the mass equalities gives
\[
\sum_tz_t+2\sum_{t\leq s}x_{ts}=1,
\]
which bounds every nonnegative variable. The set is closed and bounded in a finite-dimensional space, and the linear welfare objective is continuous, so its maximum is attained. Exact replacement transfers this maximum to the original allocation problem.
The formulas cover \(\tau=1\), zero diagonal affinities, singleton templates, and arbitrary rational thresholds. Templates of size zero are never introduced. The linked finite-agent result is expressly unnecessary and is not used as a premise.
No additional clarification or repair is required.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.