Answer: NP-hard to obtain a \(1.092\)-approximation under the stated restrictions.
Theorem 8 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateIn fair coverage instances, it is NP-hard to approximate the maximum Nash social welfare within a factor of 1.092.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite support \(K\) of complete approval types with rational masses \(\mu_\theta\), where \(\sum_{\theta\in K}\mu_\theta=1\), and \(T\) rounds with explicit menus \(\mathcal C_r\subseteq 2^K\), choose \(S_r\in\mathcal C_r\) to maximize \(\exp\!\left(\sum_{\theta\in K}\mu_\theta\log(1+\sum_{r=1}^T \mathbf 1[\theta\in S_r])\right)\). Is it NP-hard to approximate this optimum within a factor of \(1.092\), even when \(\mu_\theta=1/|K|\) for every type and every allowed option covers mass \(1/T\)?
A society is given by its support: a nonempty list \(K\) of \(\tau=|K|\) distinct complete approval types, each with positive binary rational mass \(\mu_\theta\), with \(\sum_{\theta\in K}\mu_\theta=1\). Here \(\tau\) is the support size, not the number of possible types.
There are \(T\in\mathbb Z_{>0}\) rounds, each with an explicitly listed nonempty menu \(\mathcal C_r\subseteq 2^K\). A type's complete approval profile specifies its binary approval of every round-labelled option; option \(S\) is approved exactly by the types in \(S\).
Let \(m=\sum_{r=1}^T|\mathcal C_r|\), and let \(L\) be the total binary input length, including masses and option incidences. State running times in \(m,\tau,T,L\).
A feasible outcome selects one whole option \(S_r\in\mathcal C_r\) per round; the same subset may be selected in multiple rounds when available. Its welfare is \(W(S)=\exp\bigl(\sum_{\theta\in K}\mu_\theta\log(1+\sum_{r=1}^T\mathbf 1\{\theta\in S_r\})\bigr)\), with natural logarithms. Write \(\mathrm{OPT}=\max_S W(S)\).
Restrict to instances with \(\mu_\theta=1/\tau\) for every type and \(\sum_{\theta\in A}\mu_\theta=1/T\) for every allowed option \(A\).
Is obtaining a feasible outcome with \(W(S)\ge\mathrm{OPT}/1.092\) polynomial-time solvable, or is this approximation problem NP-hard under these restrictions?
Discrete fair coverage with valuations equal to one plus coverage count is NP-hard to approximate within \(1.092\), even with explicit identical menus whose options all have size \(n/T\); it also admits an \(18+o(1)\)-approximation when weight maximization admits an FPTAS. [Source](https://arxiv.org/pdf/2207.01970v1).
No separate result for the precise distributional formulation above was verified.
The approximation problem is NP-hard, even with identical explicit menus in every round. The requirement that support types have distinct complete approval profiles needs an additional construction; simply treating each agent in the cited reduction as a type does not establish it.
We use the following established gap from the proof of Theorem 8 in [Barman, Krishna, Narahari, and Sadhukhan](https://arxiv.org/pdf/2207.01970v1).
The source instances have an explicit universe \(U\) of \(n\) agents, an integer \(T\), and an explicit nonempty family \(\mathcal F\). Every member of \(\mathcal F\) has size \(n/T\), and every round has menu \(\mathcal F\). For an outcome \(F=(F_1,\ldots,F_T)\), define
\[
\]
\(G(F)=\left(\prod_{i\in U}\left(1+\sum_{r=1}^{T}\mathbf 1\{i\in F_r\}\right)\right)^{1/n}.\)
The cited proof establishes that distinguishing the following cases is NP-hard:
We may restrict to \(T\ge 2\): when \(T=1\), every allowed set is the entire universe, so every such instance is a YES instance. Also \(T\le n\), since \(n/T\) is a positive integer.
The remainder is a reduction from this gap that enforces distinct support types.
Set \(q=10000T\) and \(N=qn\). Introduce the labelled elements
\(V=U\times\{1,\ldots,q\}.\)
For \(A\in\mathcal F\), let its lift be
\(\widehat A=A\times\{1,\ldots,q\}.\)
Choose any \(A_0\in\mathcal F\), put \(B=\widehat A_0\), and fix \(x_0\in B\) and \(y_0\in V\setminus B\). These choices exist because \(T\ge2\) and \(|B|=N/T\).
In every round, use the same menu consisting of all lifted sets and the following additional sets:
\(D_x=(B\setminus\{x\})\cup\{y_0\}\quad\text{for every }x\in B,\)
\(E_y=(B\setminus\{x_0\})\cup\{y\}\quad\text{for every }y\in V\setminus B.\)
Remove duplicate options. Each element of \(V\) defines a complete approval profile by membership in these round-labelled options.
Every two elements have different profiles:
All these options remain available after duplicate removal. Thus the profiles form a support \(K\) of exactly \(\tau=N\) distinct types.
Assign every type mass \(\mu_\theta=1/N\), encoded as a binary rational.
Every lifted option has size \(q(n/T)=N/T\). Every additional option replaces one member of \(B\) with one nonmember, so also has size \(N/T\). Consequently, every allowed option \(S\) satisfies
\(\sum_{\theta\in S}\mu_\theta=|S|/N=1/T.\)
The construction therefore satisfies all the required restrictions.
With uniform masses, the constructed welfare is
\(W(S)=\left(\prod_{v\in V}(1+c_v(S))\right)^{1/N},\)
where \(c_v(S)\) is the number of selected options containing \(v\).
If an outcome uses only lifted options, all \(q\) copies of each original agent receive its original coverage count. Hence lifting preserves welfare exactly:
\(W(\widehat F_1,\ldots,\widehat F_T)=G(F).\)
Now consider an arbitrary constructed outcome \(S\). Replace each selected additional option by \(B\), leaving lifted selections unchanged. Call the resulting outcome \(S^0\). It projects to a feasible source outcome \(F\), and therefore \(W(S^0)=G(F)\).
We bound the change when transforming \(S^0\) back into \(S\), one round at a time. Each replacement changes \(B\) into \(B\setminus\{x\}\cup\{y\}\), with \(x\in B\) and \(y\notin B\). Immediately before this replacement, write \(v_x=1+c_x\) and \(v_y=1+c_y\). Since that round currently selects \(B\), we have \(v_x\ge2\), while \(v_y\ge1\).
The change in log welfare is exactly
\(\Delta\log W=\frac1N\left(\log(v_x-1)-\log v_x+\log(v_y+1)-\log v_y\right).\)
The first difference is negative, and \((v_y+1)/v_y\le2\). Thus
\(\Delta\log W\le\frac{\log2}{N}.\)
There are at most \(T\) replacements. It follows that
\(W(S)\le G(F)\exp\left(\frac{T\log2}{N}\right)\le G(F)e^{1/10000},\)
because \(N=10000Tn\) and \(\log2<1\).
In a source YES instance, lifting a source outcome of welfare at least \(2\) gives a constructed outcome of the same welfare. Thus the constructed optimum is at least \(2\).
In a source NO instance, the preceding bound applies to every constructed outcome, giving
\(W(S)\le1.83e^{1/10000}\le\frac{18300}{9999}.\)
For the last inequality, the exponential series gives \(e^z\le\sum_{j=0}^{\infty}z^j=1/(1-z)\) for \(0\le z<1\).
Choose the rational threshold \(h=1831/1000\). The relevant strict inequalities are
\(\frac{18300}{9999}<\frac{1831}{1000}<\frac{500}{273}=\frac{2}{1.092}.\)
They follow by cross multiplication:
\(18300000<18308169,\qquad 499863<500000.\)
Therefore, a hypothetical algorithm guaranteeing \(W(S)\ge\mathrm{OPT}/1.092\) would output:
It would distinguish the NP-hard source gap.
Let \(p=|\mathcal F|\). The constructed instance has
\(\tau=10000Tn,\qquad m\le T(p+\tau).\)
Because \(T\le n\), these quantities are polynomial in the explicit source input length. Dense option incidences and complete profiles can be constructed, with duplicates removed using a binary trie, in \(O(m\tau+\tau\log\tau)\) bit operations. The resulting input length \(L\) is polynomial in the source input length.
The separating threshold requires no numerical evaluation of logarithms. For a returned outcome, compute the integer
\(P=\prod_{\theta\in K}(1+c_\theta).\)
Then
\(W(S)>h\quad\Longleftrightarrow\quad1000^\tau P>1831^\tau.\)
The integers have \(O(\tau\log(T+1))\) bits. Reading the instance, computing counts, and performing this comparison with ordinary integer arithmetic takes
\(O\left(L+T\tau\log(T+1)+\tau^2\log^2(T+1)\right)\)
bit operations. Thus an approximation algorithm polynomial in \(m,\tau,T,L\), together with this reduction and comparison, would solve the source gap in polynomial time.
Consequently, obtaining the specified feasible approximation is NP-hard under all the stated restrictions, and is not polynomial-time solvable unless \(\mathrm P=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The reduction establishes the requested NP-hardness in substance. I found no mathematical error or blocking gap. One minor clarification is needed for the claimed construction time in bit operations.
The prover states the external result precisely enough to apply it: an explicit universe of \(n\) agents, identical explicit menus, options of size \(n/T\), and an NP-hard promise gap between optimum welfare at least \(2\) and every feasible outcome having welfare at most \(1.83\).
I checked the cited source. The construction in the proof of Theorem 8 has these menu and cardinality restrictions, and its concluding bounds are exactly the stated YES and NO welfare bounds. Repeated selections are permitted by its tuple formulation. Thus the citation supports the premise actually used here. [Source, Theorem 8 and its proof](https://arxiv.org/pdf/2207.01970v1).
The restrictions on \(T\) are valid:
Assessment: Correct; the cited result's hypotheses match the reduction.
The definitions \(q=10000T\), \(N=qn\), and \(V=U\times\{1,\ldots,q\}\) produce exactly \(N\) labelled elements.
The distinguished set \(B\) has size \(N/T\). Because \(T\ge2\), both \(B\) and its complement are nonempty, so the choices of \(x_0\) and \(y_0\) exist.
The profile-separation argument checks every possible pair:
Removing duplicate options retains a representative of each subset, so it preserves these membership distinctions. Since each menu is present in every round, the distinguishing subsets also give distinguishing round-labelled approval coordinates.
Consequently, the support contains exactly \(\tau=N\) distinct complete approval types. Their masses \(1/N\) are positive binary-encoded rationals and sum to one.
Assessment: Correct; the construction addresses the distinct-profile requirement rather than assuming it.
Every lift has size \(q(n/T)=N/T\). Each additional option removes one element of \(B\) and adds one element outside \(B\), so its size is also \(N/T\).
Uniform masses therefore give every option mass \((N/T)/N=1/T\). Duplicate removal does not change this property.
Assessment: Correct; all stated restrictions are satisfied.
With uniform masses, the geometric-mean expression for \(W\) follows exactly from the task's exponential definition.
For an outcome containing only lifted options, all copies of an original agent have the same coverage count. The resulting product repeats each original valuation \(q\) times, while the root changes from \(1/n\) to \(1/(qn)\). Thus the claimed exact welfare preservation is valid.
For an arbitrary constructed outcome, replacing additional options by \(B\) gives a feasible lifted outcome. Repetition of \(B\) is allowed, so the projection to a source outcome is valid.
During each reverse replacement:
The displayed log-welfare difference is therefore exact and well-defined. Its removal term is negative, while its addition term is at most \(\log 2\). These inequalities remain valid after earlier replacements, because the round currently being changed still selects \(B\).
There are at most \(T\) replacements. The resulting bound is correct, including the deliberately loose estimate \(T\log 2/N\le1/10000\).
Assessment: Correct; the bound applies to every feasible constructed outcome.
The YES lower bound follows from exact preservation under lifting. The NO upper bound follows from the preceding universal bound.
The exponential-series estimate is valid for \(0\le z<1\), and substituting \(z=1/10000\) gives the stated rational upper bound.
Both strict threshold comparisons are arithmetically correct:
Also, \(2/1.092=500/273\) exactly.
Hence a feasible outcome satisfying the requested approximation guarantee has welfare strictly above \(h\) in a YES instance. Every feasible outcome has welfare strictly below \(h\) in a NO instance. This establishes the claimed distinction without requiring the approximation algorithm to report its welfare numerically.
Assessment: Correct; neither rounding nor equality at the threshold causes a gap.
The bounds \(\tau=10000Tn\) and \(m\le T(p+\tau)\) are valid: there are \(p\) lifted options and at most \(\tau\) additional options per round.
Because \(T\le n\) and the source universe and family are explicit, the constructed incidence data, profiles, and rational masses have polynomial total length. Thus the reduction's polynomial-size claim is established.
Minor issue — precise bit-operation accounting. The sentence claiming construction and binary-trie deduplication in \(O(m\tau+\tau\log\tau)\) bit operations does not specify its computational model or account for multi-bit node addresses and indexing. A linear number of trie traversals is not, by itself, a justification of that exact bit-operation bound.
Minimum clarification: Specify the computational model and justify the stated bit cost, or qualify the bound with the applicable addressing costs. This affects the precise running-time statement, not the polynomial reduction or hardness conclusion.
The integer product \(P\) is positive, and \(W=P^{1/\tau}\). Raising the comparison to the positive integer power \(\tau\) and clearing the positive denominator gives exactly the stated integer comparison.
The product has \(O(\tau\log(T+1))\) bits. The threshold powers have \(O(\tau)\) bits, which fit within the same bound. The stated quadratic arithmetic allowance is sufficient for ordinary multiplication and comparison. Computing coverage counts also fits the stated bound.
Assessment: Correct; the final gap test uses exact arithmetic in polynomial time.
The prover therefore resolves the target, subject only to a minor clarification of its construction-time accounting. No additional mathematical lemma 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.