Answer: \(\text{polynomial-time solvable}\)
Theorem 1 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateThe problem of determining an optimal solu- tion for any G ∈G(6) is NP-hard. Notice that, since the optimum is also stable, this also implies the hardness of finding the best stable solution in bounded degree graphs.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite connected undirected role graph \(H=(T,F)\) of maximum degree six, positive rational masses \(\mu_t\) summing to one, and rational \(\varepsilon>0\), consider an atomless population with mass \(\mu_t\) of each role \(t\). Agents are adjacent exactly when their roles are adjacent in \(H\). For a measurable coalition \(j\), let \(x_{t,j}\) be its mass of role \(t\) and \(S_j=\{t:x_{t,j}>0\}\). Distinct roles in \(S_j\) have their shortest-path distances in \(H[S_j]\); distinct agents of the same role have distance two if that role has a neighbor in \(S_j\), and infinite distance otherwise. Their utility is the average inverse distance to coalition members, and total welfare is the integral of utility over the population. Find a finite rational mass table defining a partition with welfare within \(\varepsilon\) of the supremum over measurable partitions.
Let \(H=(T,F)\) be a finite connected simple unweighted undirected role graph of maximum degree six, with \(m=|T|\ge 2\). A society is given by its support: the list of the \(\tau\) types with positive mass, each mass a binary rational; \(\tau\) denotes support size, not the number of possible types. Here every role has positive mass, so \(\tau=m\), and \(\sum_{t\in T}\mu_t=1\).
The population is the disjoint union of atomless intervals of lengths \(\mu_t\), one per role. Agents are adjacent exactly when their distinct roles are adjacent in \(H\).
For a measurable coalition \(C_j\), write \(x_{t,j}\) for its role masses, \(M_j=\sum_t x_{t,j}\), and \(S_j=\{t:x_{t,j}>0\}\). For distinct supported roles, \(d_j(t,s)\) is their shortest-path distance in \(H[S_j]\), with disconnected distance \(\infty\); set \(d_j(t,t)=2\) if \(t\) has a neighbor in \(S_j\), and \(\infty\) otherwise.
For \(M_j>0\), role-\(t\) utility is \(u_{t,j}=M_j^{-1}\sum_{s\in S_j}x_{s,j}/d_j(t,s)\), with \(1/\infty=0\). Zero-mass coalitions give utility zero; zero-mass role occurrences do not supply paths. Welfare is the population integral of utility, equivalently \(W=\sum_{j:M_j>0}\sum_{t\in S_j}x_{t,j}u_{t,j}\).
Let \(\mathrm{OPT}\) be the supremum of welfare over measurable partitions with measurable utility. Given binary-rational \(\varepsilon>0\), the computational problem is to return a finite nonnegative rational table \((x_{t,j})\) with \(\sum_jx_{t,j}=\mu_t\), positive column sums, and \(W\ge\mathrm{OPT}-\varepsilon\).
Is this computational problem solvable in polynomial time in \(m,\tau,L\), where \(L\) is the total binary input length including \(\varepsilon\), or is it NP-hard?
Discrete social-distance welfare maximization, with utility normalized by coalition size, is NP-hard on connected unweighted undirected graphs of maximum degree six. [Source](https://ojs.aaai.org/index.php/AAAI/article/download/10607/10466)
No result settling this exact atomless mass-table problem was located in the literature search.
The computational problem is solvable in polynomial time. The proof uses role splitting to reduce the welfare supremum to a convex program indexed by the cliques of \(H\). Maximum degree six makes this program polynomial-sized.
Throughout, singleton cliques are included. Their contribution in the convex program is an auxiliary upper bound, which will be realized approximately by adding positive masses of neighboring roles.
Let \(A\) be the adjacency matrix of \(H\), let \(J\) be the all-ones matrix, and define
\[ B=\frac12(J+A),\qquad q(p)=p^{\mathsf T}Bp. \]
Thus \(B_{tt}=1/2\), an adjacent pair has coefficient \(1\), and a distinct nonadjacent pair has coefficient \(1/2\).
For any positive-mass coalition with mass vector \(x\), total mass \(M\), and normalized composition \(p=x/M\), its welfare contribution is at most \(Mq(p)\). Indeed:
Consequently, every coefficient in the coalition’s welfare quadratic form is bounded above by the corresponding coefficient of \(B\).
Lemma. Every probability vector \(p\) admits a finite decomposition
\[ p=\sum_{\ell}\lambda_\ell p^\ell,\qquad q(p)=\sum_{\ell}\lambda_\ell q(p^\ell), \]
where the weights are nonnegative and sum to one, and every \(p^\ell\) is supported on a clique of \(H\).
Proof. Suppose the support of \(p\) contains nonadjacent vertices \(u,v\). Define
\[ p^u=p+p_v(e_u-e_v),\qquad p^v=p-p_u(e_u-e_v),\qquad \lambda=\frac{p_u}{p_u+p_v}. \]
Both new vectors are probability vectors. Their supports are strictly smaller, and
\[ p=\lambda p^u+(1-\lambda)p^v. \]
Along the line joining them, \(q\) is affine: its quadratic coefficient in direction \(e_u-e_v\) is
\[ (e_u-e_v)^{\mathsf T}B(e_u-e_v) =B_{uu}+B_{vv}-2B_{uv} =\frac12+\frac12-1=0. \]
Therefore,
\[ q(p)=\lambda q(p^u)+(1-\lambda)q(p^v). \]
Repeat this operation whenever a support contains a nonadjacent pair. Each branch strictly decreases support size, so the process terminates after finitely many steps. Every terminal support is a clique, giving the claimed decomposition. \(\square\)
For a clique-supported probability vector, all distinct supported roles are adjacent. Hence
\[ q(p)=1-\frac12\|p\|_2^2. \]
For a nonnegative clique-supported mass vector \(x\), define
\[ M(x)=\sum_t x_t,\qquad h(x)=\frac{\|x\|_2^2}{M(x)},\qquad g(x)=M(x)-\frac12h(x) \]
when \(M(x)>0\), and define \(h(0)=g(0)=0\).
Thus \(g(x)=M(x)q(x/M(x))\). For a singleton-supported vector, \(g(x)=M(x)/2\); this is an auxiliary value, not its actual isolated-coalition welfare.
We will also need convexity of \(h\). For nonzero nonnegative vectors \(a,b\), a direct calculation gives
\[ h(a)+h(b)-h(a+b) = \frac{M(a)M(b)}{M(a)+M(b)} \left\|\frac{a}{M(a)}-\frac{b}{M(b)}\right\|_2^2 \ge 0. \]
The same inequality holds if one vector is zero. Since \(h\) is positively homogeneous, this proves its convexity. Therefore \(g\) is concave and positively homogeneous, and consequently
\[ g(a+b)\ge g(a)+g(b). \]
Both functions are continuous at zero because \(0\le h(x)\le M(x)\).
Let \(\mathcal K\) be the family of all nonempty cliques of \(H\). Introduce one column \(x^K\) for each \(K\in\mathcal K\), with entries outside \(K\) fixed to zero. Consider the program
\[ f_*= \min \left\{ \sum_{K\in\mathcal K}h(x^K): x^K\ge 0,\quad \sum_{K\ni t}x_t^K=\mu_t\ \text{for every }t \right\}. \]
Its feasible set is nonempty: assign each role entirely to its singleton column. It is compact, and the objective is continuous and convex. Thus its minimum exists.
Because all feasible tables have total mass one, the corresponding maximum auxiliary welfare is
\[ V=1-\frac12f_* =\max\sum_{K\in\mathcal K}g(x^K). \]
We claim that \(\mathrm{OPT}\le V\), including for partitions with infinitely many coalitions.
A finite-measure population has at most countably many disjoint positive-mass coalitions. Write their vectors as \(x^j\), their masses as \(M_j\), and their actual welfare contributions as \(w_j\). Section 1 gives
\[ w_j\le M_jq(x^j/M_j). \]
Apply the decomposition lemma to \(x^j/M_j\), and scale each resulting component by \(M_j\) times its decomposition weight. This produces clique-supported vectors \(z^{j,\ell}\) satisfying
\[ \sum_\ell z^{j,\ell}=x^j,\qquad \sum_\ell g(z^{j,\ell}) =M_jq(x^j/M_j)\ge w_j. \]
Aggregate all vectors with the same clique support. Superadditivity of \(g\) shows that aggregation cannot decrease their total auxiliary welfare. This remains valid for countably many vectors: apply the inequality to finite partial sums and pass to the limit using continuity. All masses and contributions are nonnegative and summable.
The remaining agents belong to zero-mass coalitions and have utility zero by the stipulated convention. Assign their remaining role masses to singleton columns. This gives a feasible table for the convex program whose auxiliary welfare is at least the original partition’s welfare.
Thus every admissible partition has welfare at most \(V\), proving
\[ \mathrm{OPT}\le V. \]
We now show that \(V\) is the exact welfare supremum.
Take any feasible clique table \(X=(x^K)\), and delete its zero columns. Write
\[ M_K=\sum_t x_t^K. \]
For any \(0<\delta<1\), define a new table by
\[ y_t^K=(1-\delta)x_t^K+\delta M_K\mu_t. \]
Its column sums remain \(M_K\). Its row sums are exactly correct, because
\[ \sum_K y_t^K =(1-\delta)\mu_t+\delta\mu_t\sum_KM_K =\mu_t. \]
Moreover, every retained column contains positive mass of every role.
Let \(R\) be the full-graph reciprocal-distance matrix:
\[ R_{ts}=\frac1{d_H(t,s)}\quad(t\ne s),\qquad R_{tt}=\frac12. \]
The diagonal convention is valid because connectedness and \(m\ge 2\) give every role a neighbor. Since every column of \(Y\) supports all roles, its actual welfare uses precisely this matrix.
All entries of \(R\) are nonnegative. On any clique, its restriction agrees with \(B\). Therefore,
\[ \frac{(y^K)^{\mathsf T}Ry^K}{M_K} \ge (1-\delta)^2 \frac{(x^K)^{\mathsf T}Rx^K}{M_K} =(1-\delta)^2g(x^K). \]
Summing over columns gives
\[ W(Y)\ge(1-\delta)^2\sum_Kg(x^K). \]
Every such finite table is realized by a measurable partition: cut each role interval into pieces of the prescribed lengths and combine pieces with the same column index. Utility is constant on each role piece and hence measurable.
Apply this construction to a maximizing table \(X\), and let \(\delta\) tend to zero. It follows that \(\mathrm{OPT}\ge V\). Together with Section 3,
\[ \boxed{\mathrm{OPT}=1-\frac12f_*}. \]
It remains to justify polynomial time in the binary input model, including logarithmic dependence on the required accuracy.
Every clique containing a fixed vertex \(t\) is determined by a subset of its neighbors. Since \(t\) has at most six neighbors, it belongs to at most \(2^6=64\) cliques.
Consequently, if
\[ N=\sum_{K\in\mathcal K}|K| \]
is the number of mass variables, then \(N\le64m\). The cliques can be enumerated by inspecting all neighbor subsets and removing duplicates.
Eliminate each singleton variable using its row equation:
\[ x_t^{\{t\}} =\mu_t-\sum_{\substack{K\ni t\\K\ne\{t\}}}x_t^K. \]
Let \(z\) denote the remaining variables. Their feasible set \(P\) is explicitly given by nonnegativity and the row inequalities that make the eliminated singleton variables nonnegative.
Write \(f(z)=\sum_Kh(x^K(z))\). Consider the bounded epigraph
\[ E=\{(z,s):z\in P,\ f(z)\le s\le2\}. \]
This is a closed convex set. On \(P\),
\[ 0\le f(z)\le\sum_KM_K=1. \]
It has a polynomial-time exact rational separation oracle:
For a positive-mass block, the supporting coefficients are explicitly
\[ \frac{\partial h(x)}{\partial x_t} =\frac{2x_t}{M(x)} -\frac{\|x\|_2^2}{M(x)^2}. \]
At a zero block, the zero vector is a valid supporting coefficient vector on the nonnegative orthant because \(h(x)\ge0\). Substitution of the eliminated variables therefore supplies rational supporting coefficients for \(f\) on \(P\).
All evaluations and separation coefficients have encoding length polynomial in the query length and input length.
Let \(d_t\) be the number of cliques containing \(t\), and choose the feasible table
\[ x_t^{K,0}=\frac{\mu_t}{d_t}\qquad(t\in K). \]
Let \(z^0\) be its free coordinates and \(\mu_{\min}=\min_t\mu_t\). Every table entry at this point is at least \(\mu_{\min}/N\).
Set
\[ r=\frac{\mu_{\min}}{2N^2}. \]
A Euclidean perturbation of \(z^0\) of norm at most \(r\) changes each free coordinate by at most \(r\), and each eliminated singleton coordinate by at most \(Nr\). Thus all coordinates remain nonnegative.
The ball of radius \(r\) around \((z^0,3/2)\) is consequently contained in \(E\): its \(z\)-coordinates remain feasible, and its last coordinate remains between \(1\) and \(2\), while \(f(z)\le1\).
Also, \(E\) lies in a ball around the origin of radius \(N+2\). Since the masses are positive binary rationals,
\[ \log(1/r)=O(L+\log N). \]
We use the standard rational ellipsoid optimization theorem: a bounded convex body with a polynomial-time rational strong separation oracle and known inner and outer radii admits additive approximation of a rational linear objective in time polynomial in the dimension, the input and oracle encoding parameters, the logarithms of those radii, and \(\log(1/\eta)\). See Grötschel, Lovász, and Schrijver, [*Geometric Algorithms and Combinatorial Optimization*, Chapters 3–4](https://link.springer.com/book/10.1007/978-3-642-78240-4).
Here the objective is simply to minimize \(s\) over \(E\). Its optimum is \(f_*\). All the theorem’s hypotheses have been verified above.
For completeness, near-optimal feasibility has adequate interior volume even if the optimum lies on the boundary. Let \(a_*=(z_*,f_*)\) be an optimal point and \(b=(z^0,3/2)\). Convexity shows that mixing \(a_*\) with the radius-\(r\) ball around \(b\), with weight \(\lambda=\eta/4\), gives a ball of radius \(\lambda r\) contained in \(E\). For \(0<\eta\le1\), its last coordinates are at most
\[ f_*+\lambda(3/2-f_*)+\lambda r \le f_*+2\lambda =f_*+\eta/2. \]
Thus the required near-optimal region contains a ball whose logarithmic inverse radius is polynomially bounded. The ellipsoid method can return an exactly feasible rational point with \(f(z)\le f_*+\eta\), rather than requiring an exact optimizer.
It follows that such a rational table is computable in polynomial time, with polynomial output encoding length.
Let
\[ e=\min\{\varepsilon,1\}. \]
Compute a feasible rational clique table \(X\) satisfying
\[ f(X)\le f_*+e. \]
Its auxiliary welfare \(F(X)=1-\tfrac12f(X)\) satisfies
\[ F(X)\ge\mathrm{OPT}-\frac e2. \]
Delete zero columns and apply the construction from Section 4 with
\[ \delta=\frac e4. \]
The resulting table \(Y\) is rational, has exact row sums \(\mu_t\), and has positive column sums. Since \(F(X)\le1\),
\[ W(Y)\ge(1-\delta)^2F(X) \ge F(X)-2\delta \ge\mathrm{OPT}-e \ge\mathrm{OPT}-\varepsilon. \]
There are at most \(64m\) output columns, and the dense output table has polynomial size. Every step runs in polynomial time in \(m,\tau,L\), with \(\tau=m\).
The discrete hardness premise does not transfer to this model: the proof relies on splitting role masses, and on the same-role reciprocal-distance contribution of \(1/2\) once a neighbor is present.
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The argument establishes polynomial-time solvability of the specified atomless mass-table problem. I found no mathematical errors or gaps requiring repair. The singleton convention, arbitrary measurable partitions, exact row sums, and binary dependence on the accuracy parameter are all handled.
For a positive-mass coalition, its welfare is a quadratic expression in the role masses divided by its total mass. Every coefficient is bounded by the corresponding entry of \(B\): adjacent distinct roles contribute at most \(1\), nonadjacent distinct roles at most \(1/2\), and equal roles either \(1/2\) or zero.
Because the masses are nonnegative, coefficientwise domination implies the claimed welfare bound \(Mq(p)\). This remains valid for disconnected induced supports and isolated supported roles.
The operation is applied only to supported nonadjacent vertices, so \(p_u,p_v>0\). Consequently, its denominator is positive and its mixing weight belongs to \((0,1)\).
Both endpoint vectors are nonnegative probability vectors. Each removes one supported vertex without introducing a new supported vertex. The stated barycentric identity is correct.
The critical calculation also checks out: \(B_{uu}+B_{vv}-2B_{uv}=0\) for a nonadjacent pair. Thus the quadratic has no quadratic term along this direction and preserves its value under the stated mixture.
Every branch strictly decreases support size. Therefore the branching construction terminates in finitely many clique-supported vectors, preserving both the probability vector and the average quadratic value. No polynomial bound on this decomposition is needed: it is used to establish the upper bound, not as an algorithmic step.
On a clique-supported probability vector, the stated formula \(q(p)=1-\frac12\|p\|_2^2\) follows from the diagonal coefficients \(1/2\) and the off-diagonal coefficients \(1\).
The identity for \(h(a)+h(b)-h(a+b)\) has the correct coefficient and sign. Together with positive homogeneity, it establishes convexity on the nonnegative orthant. Accordingly, \(g\) is concave, positively homogeneous, and superadditive.
The definitions at zero are consistent. The bound \(0\le h(x)\le M(x)\) proves continuity there; continuity away from zero follows from the positive denominator.
Crucially, the prover explicitly treats singleton values as auxiliary values. It never incorrectly identifies an isolated singleton coalition’s actual welfare with its auxiliary value.
In a finite-measure population, the family of disjoint positive-mass coalitions is at most countable. Their union is measurable, so its complement has well-defined remaining role masses.
Applying the decomposition coalition by coalition preserves their role masses and dominates their actual welfare. Aggregation by clique support is legitimate. For countably many components, finite partial sums converge, continuity permits passage to the limit, and superadditivity preserves the inequality.
The relevant sums converge: each auxiliary contribution is nonnegative and bounded by its component mass, and total population mass is one.
Agents in zero-mass coalitions have utility zero by the task’s explicit convention. Assigning the remaining role masses to singleton columns therefore produces a feasible auxiliary table without reducing the upper bound. This establishes \(\mathrm{OPT}\le V\), including for partitions with uncountably many zero-mass coalitions.
The perturbation preserves each retained column mass and every prescribed row sum. Every resulting entry is positive because \(\delta>0\), \(M_K>0\), and every \(\mu_t>0\).
Hence every output column supports the entire graph. Connectedness and \(m\ge2\) ensure every role has a neighbor, justifying the diagonal entries \(R_{tt}=1/2\).
The restriction of \(R\) to any clique agrees with \(B\), including singleton cliques. Nonnegativity of \(R\) justifies discarding the additional terms in the perturbed quadratic, giving the stated factor \((1-\delta)^2\).
The finite-table realization by interval pieces is measurable and has measurable utility. Applying the perturbation to an existing auxiliary maximizer and taking \(\delta\) to zero therefore proves \(\mathrm{OPT}\ge V\).
The conclusion concerns a supremum; it does not assume that an actual partition attains that supremum.
A clique containing a fixed vertex is determined by a subset of its at most six neighbors. Thus \(d_t\le64\), and summing vertex–clique incidences gives \(N\le64m\).
Enumerating neighbor subsets, checking the clique condition, and removing duplicates takes polynomial time. The number of columns is also at most \(N\). Eliminating singleton variables preserves feasibility exactly.
The bounded epigraph is closed and convex. On the feasible set, \(f\le1\), because each block satisfies \(h(x)\le M(x)\).
Violated linear constraints give exact separating hyperplanes. At feasible free coordinates, the objective can be evaluated exactly using rational arithmetic.
The displayed derivative for a positive-mass block is correct. At a zero block, the zero vector supplies a valid supporting inequality on the nonnegative orthant. This restricted-domain support is sufficient because every feasible block lies in that orthant. Substitution of the eliminated singleton variables preserves the supporting inequalities.
The resulting epigraph hyperplane strictly separates a query with \(s<f(z)\). Rational evaluation and coefficient construction have polynomial bit complexity in the input and query lengths.
The proposed interior table satisfies every row equation. Since \(d_t\le N\), its entries are at least \(\mu_{\min}/N\).
The perturbation bounds for free and eliminated coordinates are valid. With the stated radius, all masses remain nonnegative. The radius is smaller than \(1/2\), so the last coordinate of the proposed epigraph ball remains between \(1\) and \(2\); the bound \(f\le1\) then proves containment.
The outer radius is valid, and positivity of the binary-rational masses gives the claimed polynomial bound on the logarithmic inverse inner radius.
The cited ellipsoid principle applies to the stated rational separation model and geometric bounds. The distinction between approximate feasibility and exact feasibility matters here; the prover addresses it with an explicit ball inside the near-optimal feasible region. Its radius and objective bound are correct, supporting an exactly feasible rational output with additive objective error. The underlying ellipsoid optimization and bit-complexity results are documented in the authors’ [primary paper, Section 2 and Theorem 3.1](https://ir.cwi.nl/pub/10046/10046D.pdf).
Thus the optimization claim has logarithmic dependence on the required accuracy, rather than polynomial dependence on its reciprocal.
With \(e=\min\{\varepsilon,1\}\), the optimization error reduces auxiliary welfare by at most \(e/2\).
The choice \(\delta=e/4\) satisfies \(0<\delta<1\). Since \(0\le F(X)\le1\), the perturbation loses at most \(2\delta=e/2\). The total loss is therefore at most \(e\le\varepsilon\).
Removing zero columns leaves positive column sums. The perturbation preserves exact row sums and rationality. Its arithmetic preserves polynomial encoding length, and the number of output columns is polynomial.
Actionable feedback: No mathematical repair is needed. A theorem number for the particular ellipsoid formulation would make the reference easier to locate, but the stated theorem and the supplied geometric checks adequately justify its application.
⟨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.