Answer: \(\mathrm{NP}\text{-hard}\)
Theorem 1 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateComputing a maximum utilitarian partition is NP-hard in the strong sense even with symmetric and strict preferences. Computing a maximum elitist partition is much easier. For any player i, let F(i) = {j | vi(j) > 0} be the set of players which i strictly likes and f(i) = P j∈F (i) vi(j). Both F(i) and f(i) can be computed in linear time.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite type set \(T\), rational masses \(\mu_t>0\) summing to \(1\), a symmetric rational valuation matrix \(V\) with nonzero entries, and rational \(\varepsilon>0\), find a finite list of rational coalition compositions \(q^k\ge 0\), with \(\sum_k q^k\le\mu\), whose welfare \(\sum_k (q^k)^{\mathsf T}Vq^k\) is within additive \(\varepsilon\) of the maximum over all measurable partitions of the atomless population. Determine the computational complexity in \(|T|\), input bit length, and \(\varepsilon\).
A society is given by its support: a nonempty list \(T\) of \(\tau\) types with positive binary-rational masses \(\mu_t\), summing to \(1\); \(\tau\) counts supported types, not possible types. Here \(m=\tau\); there is no separate ground-set parameter.
The population is the Lebesgue unit interval, divided into measurable type sets of masses \(\mu_t\). Input also includes a symmetric matrix \(V\in\mathbb{Q}^{\tau\times\tau}\) with every entry nonzero, of either sign, and binary-rational \(\varepsilon>0\). Let \(L\) be the total input bit length, including \(\varepsilon\).
A coalition is a measurable set with composition \(q_t\) equal to its type-\(t\) mass. A type-\(t\) member has utility \(\sum_s V_{ts}q_s\), so coalition welfare is \(q^{\mathsf T}Vq\); diagonal entries value distinct members of the same type, and excluding oneself changes no mass.
Partitions cover the population by disjoint measurable coalitions, with no restriction on coalition sizes or number. Their welfare is the sum over their at most countably many positive-mass coalitions; zero-mass coalitions contribute zero. Define \(\mathrm{OPT}\) as the supremum of this welfare.
The computational problem is to find a finite list \(q^1,\ldots,q^K\in\mathbb{Q}_{\ge0}^{\tau}\) with \(\sum_k q^k\le\mu\) coordinatewise and \(\sum_k(q^k)^{\mathsf T}Vq^k\ge\mathrm{OPT}-\varepsilon\). Residual mass is partitioned into singletons.
Is this additive-\(\varepsilon\) search problem solvable in polynomial time in \(m,\tau,L\), or is it NP-hard when \(\varepsilon\) is part of the binary input?
For finite agents, maximizing utilitarian welfare in additively separable hedonic games is strongly NP-hard even with symmetric, nonzero pairwise valuations. [Source](https://arxiv.org/pdf/1005.4540v3)
No result settling exactly the continuous problem defined above was located in the literature search.
The additive-\(\varepsilon\) search problem is \(\mathrm{NP}\text{-hard}\). This holds even when every diagonal entry equals \(1\), all valuations are nonzero integers, all supported types have equal dyadic masses, and \(1/\varepsilon\) is polynomially bounded in \(\tau\).
The crucial fact is that positive diagonal entries allow fractional compositions to be rounded to partitions that keep every type together.
Lemma. Suppose \(V\) is symmetric and \(V_{tt}\ge 0\) for every type \(t\). From any finite feasible list \(q^1,\ldots,q^K\), one can construct a partition keeping each type entirely within one coalition, with welfare at least
\(\sum_{k=1}^K(q^k)^{\mathsf T}Vq^k\).
For rational input, this construction takes polynomial time in the combined input and list encoding lengths.
Proof. Let \(r_t=\mu_t-\sum_kq_t^k\). Append one composition \(r_te_t\) for each type \(t\), where \(e_t\) is its coordinate vector. These added compositions contribute
\(\sum_tV_{tt}r_t^2\ge 0\).
Thus we now have finitely many coalition labels, with every type’s mass fully allocated.
Fix a type \(t\), keeping the allocations of all other types fixed. Write its current allocations as \(x_1,\ldots,x_J\), with \(\sum_jx_j=\mu_t\). Set
\(d=V_{tt}\) and \(b_j=\sum_{s\ne t}V_{ts}q_s^j\).
By symmetry, total welfare has the form
\(F=C+d\sum_{j=1}^Jx_j^2+2\sum_{j=1}^Jb_jx_j,\)
where \(C\) does not depend on this type’s allocation.
If all of type \(t\) is placed at label \(j\), the resulting welfare is
\(F_j=C+d\mu_t^2+2\mu_tb_j\).
Taking the weighted average with weights \(x_j/\mu_t\) gives
\(\displaystyle \sum_{j=1}^J\frac{x_j}{\mu_t}F_j =C+d\mu_t^2+2\sum_{j=1}^Jb_jx_j \ge F.\)
The inequality follows from \(d\ge 0\) and
\(\sum_jx_j^2\le(\sum_jx_j)^2=\mu_t^2\).
Consequently, at least one label receives all of type \(t\) without decreasing welfare.
Perform this operation once for each type. Previously processed types remain unsplit. At the end, discard empty labels; the remaining labels define a partition of the types. Grouping the corresponding measurable type sets realizes this partition.
For rational data, all comparisons are exact rational comparisons. Throughout the procedure, each coordinate is either an original allocation, a residual allocation, zero, or its full type mass. There are \(K+\tau\) labels and \(\tau\) steps, so the arithmetic and encoding lengths are polynomially bounded. This proves the lemma.
Consequence for arbitrary measurable partitions. Under the lemma’s hypotheses, let \(M_*\) denote the maximum welfare among partitions keeping every type together. There are finitely many partitions of the supported types, so this maximum exists.
For any measurable population partition, enumerate its positive-mass coalitions as \(q^1,q^2,\ldots\). With \(s_k=\sum_tq_t^k\) and \(D=\max_{t,s}|V_{ts}|\),
\(\displaystyle \sum_k\left|(q^k)^{\mathsf T}Vq^k\right| \le D\sum_ks_k^2 \le D\left(\sum_ks_k\right)^2 \le D.\)
Thus its welfare series converges absolutely. The lemma applied to every finite prefix gives
\(\displaystyle \sum_{k=1}^J(q^k)^{\mathsf T}Vq^k\le M_*.\)
Taking the limit proves that every measurable partition has welfare at most \(M_*\). Conversely, a maximizing partition of the types is a permissible population partition. Therefore
\(\mathrm{OPT}=M_*.\)
This also handles residual mass lying in arbitrarily many zero-mass coalitions.
We use the known \(\mathrm{NP}\)-completeness of deciding whether an unweighted simple graph has a cut of at least a specified size. See [Garey, Johnson, and Stockmeyer, *Some simplified NP-complete graph problems*](https://www.sciencedirect.com/science/article/pii/0304397576900591).
Let \(G=(U,E)\) be such a graph, with \(n=|U|\ge 1\). Define
\(H=\binom n2,\qquad M=H+1,\qquad A=nM+1,\qquad B=nA+1.\)
Choose \(N\) to be the least power of two satisfying \(N\ge n+2\). Create:
Every type has mass \(1/N\). Thus \(m=\tau=N\), all masses are positive dyadic rationals, and their sum is \(1\).
Define the symmetric valuation matrix by the following rules:
All entries are nonzero.
For a partition \(\mathcal P\) of the types, define its integer score
\(\displaystyle S(\mathcal P)=\sum_{C\in\mathcal P}\sum_{t,s\in C}V_{ts}.\)
Because every type has mass \(1/N\), the corresponding population welfare is \(S(\mathcal P)/N^2\). Let \(S_*\) be the maximum integer score. The rounding lemma gives
\(\mathrm{OPT}=S_*/N^2.\)
We next determine the structure of every maximizing type partition.
If a dummy shares a coalition with \(r\ge 1\) other types, separating it into its own coalition removes \(r\) unordered interactions, each of valuation \(-1\). Its diagonal contribution is unchanged, so its separation increases \(S\) by \(2r>0\).
Hence every dummy is alone in a maximizing partition.
Suppose both anchors belong to one coalition. After the preceding observation, its other members are some set \(R\) of vertex types. Separating \(b\) into its own coalition changes the score by
\(2(B-A|R|)\ge 2(B-An)=2>0.\)
Therefore the anchors belong to different coalitions in every maximizing partition.
Suppose a nonempty coalition \(R\) contains only vertex types. Merge it with the coalition containing \(a\). If that anchor coalition contains \(r\le n\) vertex types, the sum of the newly introduced unordered valuations is at least
\(A|R|-M|R|r\ge |R|(A-Mn)=|R|>0.\)
Here every valuation between two distinct vertex types is at least \(-M\). The merger therefore strictly increases the score.
It follows that every maximizing partition consists of two anchor coalitions containing all vertex types, together with isolated dummy types.
An assignment to the two anchors defines a cut of \(G\). Let \(c\) be the number of graph edges crossing this cut, and let \(u_0\) be the number of nonedges whose endpoints lie on the same side. The score is
\(S=N+2\bigl(nA-M(|E|-c)-u_0\bigr).\)
Indeed, the diagonals contribute \(N\), each vertex contributes one anchor interaction of value \(A\), each uncut edge contributes \(-M\), and each uncut nonedge contributes \(-1\).
Consider two assignments with cut sizes \(c_1>c_2\). Their score difference satisfies
\(S_1-S_2 =2\bigl(M(c_1-c_2)-(u_{0,1}-u_{0,2})\bigr) \ge 2(M-H)=2>0,\)
because \(0\le u_{0,i}\le H\).
Thus every assignment with a larger graph cut has a strictly larger score. In particular, every maximizing type partition yields a maximum cut of \(G\).
Set
\(\varepsilon=\frac{1}{2N^2}.\)
Suppose an algorithm returns any valid finite rational list for this constructed instance. Its welfare \(W\) satisfies
\(W\ge\mathrm{OPT}-\varepsilon =\frac{S_*}{N^2}-\frac{1}{2N^2}.\)
Apply the rounding lemma to the returned list. This produces a type partition \(\widehat{\mathcal P}\) whose welfare is at least \(W\). Consequently,
\(S(\widehat{\mathcal P})\ge S_*-\frac12.\)
Both scores are integers, and \(S_*\) is the maximum. Therefore
\(S(\widehat{\mathcal P})=S_*.\)
The rounded partition is exactly optimal. By the structural analysis above, reading which vertices accompany \(a\) and \(b\) gives a maximum cut. Comparing its size with the original decision threshold solves the maximum-cut decision problem.
The construction satisfies \(N<2(n+2)\). The valuation magnitudes are polynomially bounded:
\(M=O(n^2),\qquad A=O(n^3),\qquad B=O(n^4).\)
Each valuation therefore uses \(O(\log n)\) bits. If \(N=2^r\), then the masses are \(2^{-r}\) and \(\varepsilon=2^{-(2r+1)}\), also requiring only \(O(\log n)\) bits each. Hence the entire constructed instance has polynomial encoding length.
A polynomial-time search algorithm would have polynomial output length, so the exact rounding procedure would also run in polynomial time. It would then solve the \(\mathrm{NP}\)-complete maximum-cut decision problem in polynomial time.
This proves the requested \(\mathrm{NP}\)-hardness. In particular, the search problem is not polynomial-time solvable unless \(\mathrm P=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The proof resolves the assigned problem. The rounding lemma, structural reduction, and precision argument are correct. I found no major or minor mathematical issues.
\(F=C+d\sum_jx_j^2+2\sum_jb_jx_j\).
Each supported mass satisfies \(\mu_t>0\), so the averaging weights \(x_j/\mu_t\) are defined, nonnegative, and sum to one. The weighted average of the \(F_j\) is computed correctly. The inequality follows from \(d\ge 0\) and \(\sum_jx_j^2\le\mu_t^2\). Hence some full allocation of type \(t\) does not decrease welfare.
\(\sum_k|(q^k)^{\mathsf T}Vq^k|\le D\sum_ks_k^2\le D\)
establishes absolute convergence. Every finite prefix is feasible for the rounding lemma, so its welfare is at most \(M_*\). Passing to the limit is valid. Conversely, a maximizing type partition is admissible. Thus the proof establishes \(\mathrm{OPT}=M_*\), including the unrestricted partition setting in the task.
Choosing \(N\) as stated produces exactly \(N\) supported types with positive dyadic masses summing to one. The valuation rules cover all matrix entries, are symmetric, and produce nonzero integers. Every diagonal equals \(1\), satisfying the rounding lemma’s hypotheses.
The arguments are used in the proper order: dummy isolation precedes the anchor and vertex arguments, and anchor separation precedes the merger argument. Consequently, every maximizing partition has precisely the asserted structure.
\(S=N+2(nA-M(|E|-c)-u_0)\)
correctly accounts for diagonals and both orientations of each unordered interaction. Since \(0\le u_0\le H\), increasing the cut size by at least one increases the score by at least \(2(M-H)=2\). Thus every score-maximizing partition yields a maximum cut. Possible tie-breaking between assignments with equal cut size causes no problem.
No additional clarification or repair is needed. The proof establishes NP-hardness of the specified continuous search problem, including the restricted family claimed by the prover.
⟨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.