Answer: \(\mathrm{NP}\text{-complete}\)
Theorem 7 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateThe decision variant of SW-MAXIMIZING- CONCESSIONS (does there exist a feasible solution with social welfare ≥K?) is NP-complete, even when there are only negative externalities, all utility functions decompose (and all the components uk i are step functions), and each agent controls only one variable. Hardness with only two agents So far, we have not assumed any bound on the number of agents. A natural question to ask is whether such a bound makes the problem easier to solve.
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\) summing to one, finite rational step-function own-utility curves \(g_t\), externality curves \(h_{r,s}\), and a rational threshold \(K\), decide whether there are action distributions \(\nu_t\) over the finitely many action regions such that \(U_t(a;\nu)=g_t(a)+\sum_{s\in T}\mu_s\int h_{t,s}(z)\,d\nu_s(z)\ge 0\) for \(\nu_t\)-almost every assigned action \(a\), and average welfare \(W(\nu)=\sum_{t\in T}\mu_t\int U_t(a;\nu)\,d\nu_t(a)\ge K\).
A society is given by its support: a nonempty list \(T\) of \(\tau\) types with positive binary rational masses \(\mu_t\), where \(\sum_{t\in T}\mu_t=1\). Here \(\tau=|T|\) is the support size, not the number of possible types.
Each individual controls one action \(a\in\mathbb R_{\ge0}\). Input curves \(g_t\) and \(h_{r,s}\) are explicitly represented finite, right-continuous piecewise constant functions with rational breakpoints and values. Require \(g_t(0)=h_{r,s}(0)=0\), each \(g_t\) nonincreasing, and every \(h_{r,s}\) nondecreasing; hence \(g_t\le0\) and \(h_{r,s}\ge0\).
For each source type \(s\), partition \(\mathbb R_{\ge0}\) at all breakpoints of \(g_s\) and \(h_{r,s}\), including the final unbounded interval, and let \(A_s\) contain one representative per region. Set \(m=\max_s|A_s|\); let \(L\) be the total binary input length, including a threshold \(K\in\mathbb Q\).
An assignment \(\nu_t\) is a probability distribution with arbitrary real probabilities on \(A_t\), specifying the fractions of type \(t\) assigned each action. Define \(U_t(a;\nu)=g_t(a)+\sum_{s\in T}\mu_s\sum_{z\in A_s}h_{t,s}(z)\nu_s(z)\). The term \(h_{t,t}\) describes externalities from other individuals of the same type.
An assignment is feasible when \(U_t(a;\nu)\ge0\) whenever \(\nu_t(a)>0\). Its average welfare is \(W(\nu)=\sum_{t\in T}\mu_t\sum_{a\in A_t}\nu_t(a)U_t(a;\nu)\). The all-zero action assignment is allowed.
Is deciding whether a feasible assignment with \(W(\nu)\ge K\) exists solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?
For finitely many individual agents, welfare-threshold feasibility is NP-complete even with one action variable per agent, nonincreasing own utility, nondecreasing externality components, and single-step components; piecewise linear concave components instead admit polynomial-time welfare maximization ([Conitzer–Sandholm](https://www.cs.cmu.edu/~conitzer/externalitiesJCSS10.pdf)).
No result settling this exact mass-distribution problem was identified in the literature search.
The decision problem is \(\mathrm{NP}\)-complete. Hardness holds even when all masses are equal dyadic rationals, every nonconstant curve has its only breakpoint at \(\,1\,\), and \(\,m=2\,\).
The reduction below handles arbitrary real assignment probabilities directly.
Write \(\,p_{s,a}=\nu_s(a)\,\). Since \(\,\sum_{a\in A_t}p_{t,a}=1\,\), expanding the welfare gives
\[ W(p)=\sum_{s\in T}\sum_{a\in A_s} \mu_s\left(g_s(a)+\sum_{t\in T}\mu_t h_{t,s}(a)\right)p_{s,a}. \]
Thus welfare is linear. Feasibility, however, requires an action’s utility to be nonnegative whenever its probability is positive. This conditional requirement will enforce integral choices in the reduction.
We reduce from Set Cover, whose \(\mathrm{NP}\)-completeness is classical. See [Karp’s original paper](https://www2.seas.gwu.edu/~simhaweb/champalg/tsp/papers/KarpOriginal.pdf).
An instance consists of a universe \(\,E=\{1,\ldots,q\}\,\), sets \(\,S_1,\ldots,S_n\subseteq E\,\), and an integer \(\,k\,\). The question is whether at most \(\,k\,\) sets cover \(\,E\,\). We restrict to \(\,n,q\ge1\,\) and \(\,0\le k\le n\,\); excluded cases are directly decidable, so these restrictions retain hardness.
Let \(\,N\,\) be the smallest power of two satisfying \(\,N\ge n+q+1\,\). Introduce:
Every type has mass \(\,\mu_t=1/N\,\). Define
\[ \delta_j=|S_j|,\qquad D_j=N+\delta_j,\qquad P=n+1, \qquad C=\frac{1}{N}\sum_{j=1}^n D_j. \]
Let \(\,\sigma(a)=0\,\) for \(\,0\le a<1\,\), and \(\,\sigma(a)=1\,\) for \(\,a\ge1\,\).
The own-utility curves are
\[ g_{d_j}(a)=-(1+D_j)\sigma(a),\qquad g_{e_i}(a)=-\sigma(a). \]
The hub and dummy types have identically zero own-utility curves.
The nonzero externality curves are precisely:
All other externality curves are zero. Here the first index is the receiver and the second is the source.
Set the welfare threshold to
\[ K=C+Pq-k. \]
Every curve is finite, explicitly represented, right-continuous, and piecewise constant. All curves vanish at zero. Own-utility curves are nonincreasing, and externality curves are nondecreasing.
Every nondummy source has exactly two regions, represented by \(\,0\,\) and \(\,1\,\). Dummy sources have one region, represented by zero. Therefore \(\,m=2\,\).
Moreover, \(\,N<2(n+q+1)\,\), and all curve values and the threshold have polynomial binary encoding length. The entire explicit construction, including zero curves, has polynomial size. All masses are positive dyadic rationals summing to one.
For an arbitrary assignment, write
\[ y=\nu_b(1),\qquad x_j=\nu_{d_j}(1),\qquad z_i=\nu_{e_i}(1). \]
These numbers lie in \(\,[0,1]\,\).
For set type \(\,d_j\,\), the utility of action one is
\[ U_{d_j}(1;\nu)=-(1+D_j)+x_j+D_jy =-(1-x_j)-D_j(1-y). \]
Both terms on the right are nonpositive. If \(\,x_j>0\,\), feasibility requires this utility to be nonnegative. Consequently both terms must vanish:
\[ x_j>0\quad\Longrightarrow\quad x_j=1\ \text{and}\ y=1. \]
Thus every feasible assignment has \(\,x_j\in\{0,1\}\,\). Fractional set choices are impossible.
For element type \(\,e_i\,\),
\[ U_{e_i}(1;\nu)=-1+\sum_{j:\,i\in S_j}x_j. \]
Hence \(\,z_i>0\,\) is possible only if at least one selected set contains \(\,i\,\). Conversely, when this condition holds, assigning action one to the entire element type is feasible.
Action zero always has nonnegative utility, because its own utility is zero and all externalities are nonnegative. Both hub actions and all dummy actions likewise have nonnegative utility. These observations check every feasibility constraint.
Using the linear welfare formula from Section 1, the coefficient of the hub probability \(\,y\,\) is
\[ \frac{1}{N}\sum_{j=1}^n D_j=C. \]
For set type \(\,d_j\,\), its action-one coefficient is
\[ \frac{1}{N}\left(-(1+D_j)+1+\delta_j\right) =\frac{-D_j+\delta_j}{N}=-1. \]
The positive terms here are its self-externality and its externalities to the elements of \(\,S_j\,\).
For element type \(\,e_i\,\), its action-one coefficient is
\[ \frac{1}{N}\left(-1+(1+NP)\right)=P. \]
All action-zero coefficients and all dummy coefficients vanish. Therefore, for every assignment,
\[ W(\nu)=Cy-\sum_{j=1}^n x_j+P\sum_{i=1}^q z_i. \]
Suppose \(\,J\subseteq\{1,\ldots,n\}\,\) covers \(\,E\,\) and \(\,|J|\le k\,\).
Choose \(\,y=1\,\), choose \(\,x_j=1\,\) exactly for \(\,j\in J\,\), and choose \(\,z_i=1\,\) for every element.
Every selected set type has action-one utility zero. Every element type has action-one utility at least zero because it is covered. All other assigned actions are feasible by Section 3. The welfare is
\[ W=C-|J|+Pq\ge C-k+Pq=K. \]
Conversely, suppose a feasible assignment satisfies \(\,W\ge K\,\). Define
\[ J=\{j:x_j>0\}. \]
Section 3 proves that \(\,x_j=1\,\) for every \(\,j\in J\,\), so \(\,\sum_jx_j=|J|\,\). Since \(\,C>0\,\), \(\,y\le1\,\), and \(\,z_i\le1\,\),
\[ W\le C-|J|+Pq. \]
Comparing this bound with \(\,W\ge C+Pq-k\,\) yields \(\,|J|\le k\,\).
If some element were uncovered by \(\,J\,\), its feasibility constraint would force \(\,z_i=0\,\). Then
\[ W\le C-|J|+P(q-1)\le C+P(q-1). \]
But \(\,P=n+1>k\,\), so
\[ C+P(q-1)<C+Pq-k=K, \]
a contradiction. Thus \(\,J\,\) covers every element and contains at most \(\,k\,\) sets.
This proves \(\mathrm{NP}\)-hardness.
For the general problem, nondeterministically choose a nonempty subset \(\,B_t\subseteq A_t\,\) for each type. Consider the following rational linear feasibility system:
\[ g_t(a)+\sum_{s\in T}\mu_s\sum_{z\in A_s}h_{t,s}(z)p_{s,z}\ge0; \]
If the original instance has a feasible assignment, choosing its actual positive-probability supports makes this system feasible.
Conversely, any solution of this system is feasible for the original problem: every action with positive probability belongs to \(\,B_t\,\) and therefore has nonnegative utility. Allowing some actions in \(\,B_t\,\) to receive zero probability causes no difficulty.
There are at most \(\,\tau m\,\) variables and polynomially many constraints. Their rational coefficients can be computed with polynomial bit length from the explicitly represented input. Rational linear-programming feasibility is decidable in time polynomial in this encoding length. Thus a polynomial-length support guess followed by a polynomial-time feasibility check establishes membership in \(\mathrm{NP}\).
Arbitrary real probabilities do not enlarge the class of yes-instances beyond rational witnesses: each feasible system above is a bounded rational polytope, and a nonempty such polytope has a rational vertex of polynomial encoding length, by the determinant bounds for its defining tight constraints.
Consequently, the problem is \(\mathrm{NP}\)-complete, and a polynomial-time algorithm in \(\,m,\tau,L\,\) would imply \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The prover’s claim is correct. The argument establishes \(\mathrm{NP}\)-completeness for the exact mass-distribution problem, including assignments with arbitrary real probabilities. I found no major or minor mathematical issues requiring repair.
The externality term received by type \(t\) is independent of that type’s assigned action. Consequently, summing it against \(p_{t,a}\) multiplies it by \(\sum_a p_{t,a}=1\). Interchanging the finite sums therefore gives exactly the formula in Section 1.
All factors \(\mu_s\) and \(\mu_t\) are correctly placed. The calculation includes externalities within the same type, as required by USER_TASK. No independence assumption or restriction to rational probabilities is used.
The source problem is the standard decision version of Set Cover: whether an explicitly given family contains at most \(k\) sets whose union is the universe. Its cited \(\mathrm{NP}\)-completeness is applicable. [Karp’s original paper](https://www2.seas.gwu.edu/~simhaweb/champalg/tsp/papers/KarpOriginal.pdf).
The restrictions \(n,q\ge1\) and \(0\le k\le n\) exclude only polynomially decidable cases and retain hardness.
The power-of-two padding satisfies \(n+q+1\le N<2(n+q+1)\). Thus the number of types, including dummy types, is polynomial in the explicitly represented source instance. Giving every type mass \(1/N\) produces positive dyadic rational masses summing to one.
The quantities \(D_j\), \(P\), the curve values, and \(K\) have polynomial binary encoding length. Explicitly listing all receiver-source curves, including zero curves, requires only polynomially many entries.
Every nonconstant curve is a rational multiple of the right-continuous step function \(\sigma\), with its sole breakpoint at \(1\). All own-utility coefficients are nonpositive, and all externality coefficients are nonnegative. Hence every curve has the required monotonicity and vanishes at zero.
Every nondummy source has a breakpoint at \(1\):
Therefore their regions are exactly \([0,1)\) and \([1,\infty)\), represented validly by \(0\) and \(1\). Dummy sources have one region. The claim \(m=2\) is correct, including the final unbounded regions.
For a set type, the only nonzero incoming externalities are its self-externality and the hub contribution. Their mass factors give exactly
\(U_{d_j}(1;\nu)=-(1-x_j)-D_j(1-y)\).
Since \(x_j,y\in[0,1]\) and \(D_j>0\), both summands are nonpositive. If \(x_j>0\), feasibility requires their sum to be nonnegative, so both vanish. Thus \(x_j=1\) and \(y=1\).
This proves integrality of every set choice for all real-valued assignments. It does not incorrectly impose feasibility on an unused action.
For an element type, the expression
\(U_{e_i}(1;\nu)=-1+\sum_{j:i\in S_j}x_j\)
is also correct. Given the established integrality, positive \(z_i\) requires coverage. Coverage conversely permits \(z_i=1\).
All action-zero utilities are nonnegative. Hub utilities are nonnegative at both actions, and dummy utilities are zero. Thus the remaining feasibility constraints are accounted for.
Rechecking the linear coefficients gives:
The set coefficient correctly includes the self-externality and all \(\delta_j\) outgoing element externalities. The element coefficient correctly includes its outgoing externality to the hub.
Consequently, \(W(\nu)=Cy-\sum_jx_j+P\sum_i z_i\) holds for every assignment, not merely feasible or integral ones.
A cover of size at most \(k\) yields the stated feasible assignment: selected set types have utility zero, and every active element type has nonnegative utility. Its welfare meets \(K\).
Conversely, for a feasible assignment meeting \(K\), integrality gives \(\sum_jx_j=|J|\). Using \(y,z_i\le1\) yields \(W\le C-|J|+Pq\), hence \(|J|\le k\).
If any element is uncovered, its probability \(z_i\) must be zero. The resulting bound \(W\le C+P(q-1)\) is strictly below \(K\), because \(P=n+1>k\). Fractional probabilities on covered elements cannot invalidate this bound.
Empty sets, uncovered universe elements, \(k=0\), and \(k=n\) introduce no exceptions. The all-zero assignment is feasible but cannot meet the constructed positive threshold.
The guessed supports have polynomial encoding length. The proposed system contains only rational linear constraints and polynomially many variables and constraints.
Both implications are correct: an original feasible assignment satisfies the system for its actual positive supports; any system solution satisfies every utility constraint associated with a positive probability. Permitting additional zero-probability actions in the guessed supports causes no false acceptance.
The stated polynomial-time theorem for rational linear-programming feasibility applies: the constraints are non-strict, explicitly represented, and have polynomial coefficient bit length. Thus guessing supports and deterministically checking the resulting system establishes membership in \(\mathrm{NP}\).
The supplementary rational-witness assertion is also valid. Normalization and nonnegativity make each system bounded; a nonempty bounded rational polyhedron has a vertex whose rational coordinates have polynomial encoding length by the stated determinant bounds. Lower-dimensional systems do not invalidate this assertion.
Repair feedback: None is needed. The proof resolves the assigned question and supports the stronger claim of \(\mathrm{NP}\)-completeness under the stated restrictions.
⟨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.