Answer: Finding the required feasible rational selection is \(\mathrm{NP}\)-hard for every fixed \(\epsilon\in(0,1)\), already with uniform dyadic masses and symmetric positive payments.
Theorem 1 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateFor any $\epsilon > 0$, it is NP-hard to find a solution $S$ to optimization problem \eqref{eq.opt_e} (and thus \eqref{eq.opt}) such that $ \frac{f(S)}{f(\opt)} \ge \frac{1}{|V|^{1-\epsilon}}$.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite type set \(T\), rational type masses \(\mu_t>0\) summing to \(1\), symmetric peer eligibility, rational expected payments \(\pi_{tu}\) for eligible pairs, and a rational per-capita budget \(B\), choose rational selected masses \(x_t\in[0,\mu_t]\). Every type with \(x_t>0\) must have an eligible peer type \(u\) with \(x_u>0\); a type may peer with itself when positive mass represents distinct agents of that type. The cost is \(C(x)=\sum_{t\in T}x_t\max_{u\text{ eligible for }t,\;x_u>0}\pi_{tu}\). Maximize \(F(x)=\sum_{t\in T}x_t\) subject to \(C(x)\le B\). What are the exact and approximation complexities of this problem in \(|T|\) and the input bit length?
A society is given by its support: a nonempty list \(T\) of \(\tau=|T|\) types with positive binary-rational masses \(\mu_t\), summing to \(1\). Here \(\tau\) is the support size, not the number of possible types; \(L\) is the total input bit length. There is no separate candidate parameter \(m\).
Input also specifies a symmetric eligibility relation \(R\subseteq T\times T\), with every type having an eligible peer, strictly positive rational directed payments \(\pi_{tu}\) for \((t,u)\in R\), and a positive rational per-capita budget \(B\). Payments need not be symmetric and have no fixed instance-independent upper bound.
Choose rational masses \(0\le x_t\le\mu_t\). Writing \(A(x)=\{t:x_t>0\}\), require that every \(t\in A(x)\) has some \(u\in A(x)\) with \((t,u)\in R\). A diagonal eligibility entry permits distinct agents of the same type to serve as peers; no minimum positive mass or peer capacity is imposed.
Define \(C(x)=\sum_{t\in A(x)}x_t\max_{u\in A(x):(t,u)\in R}\pi_{tu}\) and \(F(x)=\sum_{t\in T}x_t\); the zero vector has cost zero. Feasibility requires \(C(x)\le B\). Let \(\mathrm{OPT}\) be the supremum of \(F(x)\) over feasible rational selections.
For each fixed \(\epsilon\in(0,1)\), is finding a feasible rational selection with \(F(x)\ge\tau^{-(1-\epsilon)}\mathrm{OPT}\) solvable in time polynomial in \(\tau\) and \(L\), or is it NP-hard?
For finite societies of \(n\) agents, obtaining value at least \(n^{-(1-\epsilon)}\) times optimum is NP-hard for every fixed \(\epsilon\in(0,1)\), already for cardinality utility and symmetric positive payments. [Source](https://machineteaching.mpi-sws.org/files/papers/radanovic18information_long.pdf)
No result settling this precise continuous approximation question was located in the literature search.
For every fixed \(\epsilon\in(0,1)\), finding the required feasible rational selection is \(\mathrm{NP}\)-hard, already with uniform dyadic masses, complete eligibility including diagonal entries, and symmetric positive payments.
The proof gives a polynomial-time conversion from any feasible continuous selection to a clique. Thus arbitrarily small positive masses do not invalidate the reduction.
For a finite simple graph \(G\), let \(\omega(G)\) denote its maximum clique size.
Zuckerman’s Theorem 1.1 states that, for every fixed \(\delta\in(0,1)\), finding a clique of size at least \(\omega(G)/n^{1-\delta}\) in an \(n\)-vertex graph is \(\mathrm{NP}\)-hard. We will apply this with \(\delta=\epsilon/2\). [Source: *Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number*.](https://theoryofcomputing.org/articles/v003a006/v003a006.pdf)
Let \(G=(V,E)\) be a simple graph with \(n\ge2\) vertices. Let \(N\) be the smallest power of two satisfying \(N\ge n\). Add isolated vertices to obtain a graph \(G'=(V',E')\) with \(N\) vertices. Then
\[ \text{ } \]
\(n\le N<2n,\qquad \omega(G')=\omega(G).\)
The clique numbers agree because every clique containing an added isolated vertex has size one, while \(G\) has a singleton clique.
Construct the society as follows:
\(\displaystyle \pi_{tu}= \begin{cases} 1,&t=u\text{ or }\{t,u\}\in E',\\ H,&t\ne u\text{ and }\{t,u\}\notin E'. \end{cases} \)
All masses are positive dyadic rationals and sum to one. All payments are positive integers. Every type has an eligible peer, and diagonal eligibility makes singleton supports permissible under the task’s convention.
The explicit encoding has length \(O(N^2\log N)\), hence polynomial in the source graph’s size.
Lemma. From any feasible rational selection \(x\) in the constructed society, one can compute a clique \(Q\) in \(G'\) satisfying
\(\displaystyle |Q|\ge N F(x).\)
Proof. Write \(S=A(x)\). If \(S\) is empty, take \(Q=\varnothing\).
Otherwise, partition \(S\) into
\(\displaystyle D=\{t\in S:\exists u\in S\setminus\{t\},\ \{t,u\}\notin E'\}, \qquad U=S\setminus D. \)
Every vertex in \(U\) is adjacent in \(G'\) to every other vertex of \(S\). Consequently, \(U\) is a clique. Moreover, for every \(d\in D\), the set \(U\cup\{d\}\) is a clique.
The maximum selected-peer payment is exactly \(H\) for every vertex in \(D\), and exactly one for every vertex in \(U\). Therefore,
\(\displaystyle C(x)=\sum_{t\in U}x_t+H\sum_{t\in D}x_t\le1, \)
which implies
\(\displaystyle \sum_{t\in D}x_t\le\frac1H.\)
We now consider both cases.
If \(D=\varnothing\), take \(Q=S=U\). Since each mass is at most \(1/N\),
\(\displaystyle N F(x)=N\sum_{t\in U}x_t\le |U|=|Q|.\)
If \(D\ne\varnothing\), choose any \(d\in D\) and take \(Q=U\cup\{d\}\). This is a clique, and
\(\displaystyle N F(x) =N\sum_{t\in U}x_t+N\sum_{t\in D}x_t \le |U|+\frac NH =|U|+\frac1N \le |U|+1 =|Q|. \)
This proves the lemma. Computing the support, its partition, and the clique requires only exact comparisons of the output rationals with zero and inspection of vertex pairs, so it is polynomial-time. \(\square\)
In particular, the proof applies regardless of how small the positive selected masses are.
The lemma implies that every feasible selection satisfies
\(\displaystyle F(x)\le\frac{\omega(G')}{N}.\)
Conversely, let \(K\) be a maximum clique of \(G'\), and select full mass \(1/N\) from each type in \(K\), with zero mass elsewhere. All selected-peer payments are one, so
\(\displaystyle C(x)=F(x)=\frac{|K|}{N}\le1. \)
This is a feasible rational selection. Hence
\(\displaystyle \mathrm{OPT}=\frac{\omega(G')}{N}=\frac{\omega(G)}{N}.\)
Thus the supremum is attained on these instances.
Fix \(\epsilon\in(0,1)\). Suppose a polynomial-time algorithm always outputs a feasible rational selection satisfying the requested guarantee. On the constructed instance, its output would satisfy
\(\displaystyle F(x)\ge N^{-(1-\epsilon)}\mathrm{OPT} =\frac{\omega(G)}{N^{2-\epsilon}}. \)
Apply the lemma to obtain a clique \(Q\) in \(G'\). Then
\(\displaystyle |Q|\ge N F(x)\ge\frac{\omega(G)}{N^{1-\epsilon}}. \)
This clique converts to a clique of the same size in \(G\): if it contains an added isolated vertex, it must be a singleton, which can be replaced by any original vertex. Otherwise it already lies in \(G\).
For all \(n\ge2^{2/\epsilon}\),
\(\displaystyle N^{1-\epsilon} \le 2^{1-\epsilon}n^{1-\epsilon} \le 2n^{1-\epsilon} \le n^{1-\epsilon/2}. \)
Therefore the resulting clique in \(G\) has size at least
\(\displaystyle \frac{\omega(G)}{n^{1-\epsilon/2}}.\)
For the finitely many smaller sizes, maximum clique can be solved by exhaustive enumeration. Because \(\epsilon\) is fixed, this contributes only a constant bound to the running time. The complete procedure would consequently be a polynomial-time approximation algorithm contradicting the cited hardness theorem with \(\delta=\epsilon/2\), unless \(\mathrm{P}=\mathrm{NP}\).
This establishes the requested \(\mathrm{NP}\)-hardness.
⟨structured verdict parsed — rendered above⟩
The prover resolves the assigned continuous approximation question. The reduction and clique extraction are correct, the cited hardness theorem applies, and no mathematical gaps were found.
[Zuckerman’s Theorem 1.1](https://theoryofcomputing.org/articles/v003a006/v003a006.pdf) establishes that, for every fixed positive exponent parameter, approximating maximum clique within the corresponding factor \(n^{1-\delta}\) is NP-hard. The prover correctly states its solution-output consequence: producing a clique of size at least \(\omega(G)/n^{1-\delta}\) is NP-hard.
The application uses \(\delta=\epsilon/2\). Since the task fixes \(\epsilon\in(0,1)\), this is a fixed parameter in the required range. The source establishes deterministic NP-hardness; no additional randomized-complexity assumption is needed.
Every restriction in the task is satisfied:
The encoding-length bound \(O(N^2\log N)\) is valid: there are quadratically many payment entries, each requiring \(O(\log N)\) bits, and the remaining data fit within that bound. Since \(N<2n\), construction time and output length are polynomial in the source graph’s explicit encoding length.
The lemma is valid for every feasible rational selection, including selections with arbitrarily small positive coordinates.
For empty support, \(F(x)=0\), so the empty clique satisfies the claimed inequality.
For nonempty support \(S\), the definitions of \(D\) and \(U\) give the asserted adjacency properties. A vertex in \(U\) has no distinct nonneighbor in \(S\). Thus \(U\) is a clique, and \(U\cup\{d\}\) is a clique for each \(d\in D\).
The payment maxima are also exact:
Consequently,
\(C(x)=\sum_{t\in U}x_t+H\sum_{t\in D}x_t\).
Nonnegativity and feasibility imply
\(\sum_{t\in D}x_t\le 1/H\).
Both extraction cases check out:
\(NF(x)\le |U|+N/H=|U|+1/N\le |U|+1=|Q|\).
There is no unjustified rounding or lower bound on positive selected mass.
Support detection and pairwise adjacency inspection take polynomial time in the graph size and the encoded selection length. In the reduction’s application, a polynomial-time selection algorithm necessarily produces an output of polynomial length, so extraction remains polynomial-time.
The lemma gives \(NF(x)\le |Q|\le\omega(G')\) for every feasible rational selection. Therefore it bounds the supremum as well:
\(\mathrm{OPT}\le\omega(G')/N\).
The reverse bound is correctly established by selecting full mass from a maximum clique. Every relevant payment is one, so its cost and value both equal \(|K|/N\le1\). This selection is rational and satisfies the peer requirement, including when the maximum clique is a singleton.
Thus
\(\mathrm{OPT}=\omega(G')/N=\omega(G)/N\),
and the supremum is attained on the constructed instances.
The promised continuous guarantee gives
\(F(x)\ge\omega(G)/N^{2-\epsilon}\).
Applying the lemma therefore yields
\(|Q|\ge\omega(G)/N^{1-\epsilon}\).
The conversion back to \(G\) is valid. A clique containing an added isolated vertex must be a singleton and can be replaced by any original singleton. Otherwise it already lies in \(G\). The approximation guarantee ensures positive output value, so the extracted clique in this application is nonempty.
For \(n\ge2^{2/\epsilon}\), every inequality in the displayed factor comparison is correct. In particular,
\(2\le n^{\epsilon/2}\) gives
\(2n^{1-\epsilon}\le n^{1-\epsilon/2}\).
The resulting clique therefore meets the cited hardness threshold with \(\delta=\epsilon/2\).
Handling smaller graphs by exhaustive enumeration preserves polynomial running time because their size is bounded by a constant depending only on the fixed \(\epsilon\). This also handles the excluded singleton source graph.
The proof establishes the requested NP-hardness through a polynomial-time approximation reduction. It directly addresses the continuous support model and accounts for arbitrarily small positive masses. No repair or additional clarification is needed.
⟨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.