Answer: Achieving any fixed approximation ratio \(\rho\in(50/51,1]\) is NP-hard, even with dyadic rational masses. The requested polynomial-time algorithm cannot exist unless \(\mathrm{P}=\mathrm{NP}\); ratios \(\rho>1\) are impossible.
Theorem 1 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateThe restriction of CPD to instances with k = 2, m = 2q, and agents with uniformly dichotomous utilities is NP-hard to approximate within a factor of 50/51 ⇡0.9804.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite item set \(X\) with \(|X|=2q\) and a rational distribution \(\mu\) over supported binary utility types \(t:X\to\{0,1\}\), compute a pair of disjoint \(q\)-item sets maximizing \(U_\mu(S)=\sum_t\mu_t\sum_{j=1}^{2}\max_{x\in S_j}u_t(x)\). In particular, is there a polynomial-time approximation with ratio strictly greater than \(50/51\)?
Given a positive integer \(q\) and an item set \(X\) with \(m=|X|=2q\), each utility type is an explicitly listed map \(u_t:X\to\{0,1\}\).
A society is given by its support: the list of the \(\tau\) distinct types with positive mass, each mass \(\mu_t\) a binary rational, with \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types; \(L\) is the total input bit length.
A feasible program is a pair \(S=(S_1,S_2)\) of disjoint subsets of \(X\), each of size \(q\), hence partitioning \(X\). Its utility is \(U_\mu(S)=\sum_t\mu_t\sum_{j=1}^{2}\max_{x\in S_j}u_t(x)\). Let \(\mathrm{OPT}_\mu=\max_S U_\mu(S)\).
Does there exist a fixed constant \(\rho>50/51\) and a deterministic algorithm, polynomial in \(m,\tau,L\) and \(q\), returning a feasible program with \(U_\mu(S)\ge\rho\,\mathrm{OPT}_\mu\), or is achieving such an approximation NP-hard?
For a finite list of equally weighted agents, binary utilities and two equal slots covering all items, approximation within \(50/51\) is NP-hard. [Caragiannis, Gourvès and Monnot](https://www.ijcai.org/Proceedings/16/Papers/028.pdf).
No separate result for exactly the rational-support formulation was identified in the literature search.
Achieving any fixed approximation ratio \(\rho\in(50/51,1]\) is NP-hard for the stated rational-support formulation. Consequently, the requested deterministic polynomial-time algorithm cannot exist unless \(\mathrm{P}=\mathrm{NP}\).
The reduction preserves every feasible program’s approximation ratio exactly. It even works when all masses must be dyadic rationals.
We use the following published result: for an explicitly listed population of equally weighted agents with binary utilities, maximizing total utility over two disjoint slots of size \(q\), with \(m=2q\), is NP-hard to approximate within \(50/51\). Thus achieving any fixed ratio strictly greater than \(50/51\) is NP-hard. These are precisely the restrictions in [Caragiannis, Gourvès and Monnot, Theorem 1](https://www.ijcai.org/Proceedings/16/Papers/028.pdf).
Here \(q\) varies with the input. For any fixed \(q\), enumerating all partitions gives an exact polynomial-time algorithm.
Consider an instance of that hard problem with \(n\geq 1\) explicitly listed agents, whose utility maps are \(u_1,\ldots,u_n:X\to\{0,1\}\). Write its objective as
\[ W(S)=\sum_{i=1}^{n}\sum_{j=1}^{2}\max_{x\in S_j}u_i(x), \]
and let \(W^\star=\max_S W(S)\).
Set
\[ N=2^{\lceil\log_2 n\rceil}. \]
Conceptually add \(N-n\) agents whose utility map is identically zero. This padding need not be explicitly generated.
Group the original agents by identical utility maps, and include the zero map if padding gives it positive multiplicity. For each resulting distinct map \(u_t\), let \(c_t\) be its multiplicity after padding, and assign mass
\[ \mu_t=\frac{c_t}{N}. \]
Omit every map with zero multiplicity. The resulting instance satisfies all required hypotheses:
For every feasible program \(S\), grouping identical maps and using the zero contribution of the padded agents gives
\[ \begin{aligned} U_\mu(S) &=\sum_t\frac{c_t}{N}\sum_{j=1}^{2}\max_{x\in S_j}u_t(x)\\ &=\frac{1}{N}\sum_{i=1}^{n}\sum_{j=1}^{2}\max_{x\in S_j}u_i(x)\\ &=\frac{W(S)}{N}. \end{aligned} \]
Taking maxima over the identical feasible sets therefore yields
\[ \mathrm{OPT}_\mu=\frac{W^\star}{N}. \]
These identities also hold when the optimum is zero; no division by the optimum is needed.
Grouping the explicitly listed binary vectors can be performed by sorting them, in polynomial time. The support size satisfies \(\tau\leq n+1\). Since \(N<2n\) for \(n>1\), each numerator and denominator has bit length \(O(\log(n+1))\). Including the explicit utility vectors, the constructed input has length
\[ L=O\bigl((n+1)(m+\log(n+1))+\log(q+1)\bigr). \]
Thus its size and construction time are polynomial in the original explicit input length.
Suppose a deterministic algorithm, polynomial in \(m,\tau,L,q\), always returned a feasible \(S\) satisfying
\[ U_\mu(S)\geq\rho\,\mathrm{OPT}_\mu \]
for some fixed \(\rho\in(50/51,1]\). Applying it to the constructed instance and multiplying the inequality by \(N>0\) would give
\[ W(S)=N U_\mu(S)\geq\rho N\mathrm{OPT}_\mu=\rho W^\star. \]
The composition would therefore be a polynomial-time \(\rho\)-approximation for the known hard problem, contradicting its hardness unless \(\mathrm{P}=\mathrm{NP}\).
Finally, \(\rho>1\) is impossible even without computational restrictions: an instance with one type assigning utility \(1\) to every item has utility and optimum both equal to \(2\).
Hence the rational-support formulation inherits the required hardness; no separate literature theorem for that representation is necessary.
⟨structured verdict parsed — rendered above⟩
The argument is correct and resolves the assigned question. The reduction transfers the cited hardness to the rational-support formulation, including the restriction to dyadic masses. No major or minor mathematical issues were found.
Theorem 1 of [Caragiannis, Gourvès and Monnot](https://www.ijcai.org/Proceedings/16/Papers/028.pdf) states hardness of approximation within \(50/51\) for conference program design with two slots, \(m=2q\), and binary utilities. The paper defines each slot as a disjoint set of exactly \(q\) items and defines social utility as the sum, over agents and slots, of the maximum item utility.
These definitions match the prover’s source problem. Because the agents contribute equally to the objective, replacing total utility by average utility would not change approximation guarantees. Any guarantee with fixed \(\rho>50/51\) would also satisfy the weaker \(50/51\) guarantee, so the stated hardness implication is valid.
For every \(n\geq1\), the chosen \(N=2^{\lceil\log_2 n\rceil}\) is a positive power of two satisfying \(N\geq n\). Thus the padding multiplicity \(N-n\) is nonnegative.
When \(n=1\), \(N=1\), and no padding is necessary. Every padded agent has zero utility for every feasible program, so padding preserves the original objective values.
Grouping identical utility vectors produces distinct binary maps. Each retained multiplicity \(c_t\) is positive, so each mass \(\mu_t=c_t/N\) is positive. The multiplicities sum to \(N\), which establishes normalization.
Since \(N\) is a power of two, every mass has a finite binary expansion. An existing zero type and the padded zero agents are grouped together, so the construction introduces no duplicate listed type.
The construction retains \(X\) and \(q\). Therefore it preserves the feasible programs exactly, including the requirement that the two slots partition all items.
Grouping merely collects equal summands, and padded zero agents contribute nothing. Consequently, for every feasible \(S\),
\[
U_\mu(S)=W(S)/N.
\]
Taking maxima over the same feasible set gives \(\mathrm{OPT}_\mu=W^\star/N\). Both identities remain valid when the optimum is zero. The approximation-transfer argument uses multiplication by \(N>0\), so it does not require division by a possibly zero optimum.
Sorting explicitly listed binary vectors permits polynomial-time grouping. The support bound \(\tau\leq n+1\) is valid. The numerators and denominator require \(O(\log(n+1))\) bits, including the case \(n=1\).
The stated encoding bound is valid under the usual indexed-item encoding. The item set is inherited from the source instance. Moreover, \(q=m/2\), so polynomial dependence on the numerical parameter \(q\) does not introduce a pseudopolynomial runtime: \(m\) is already represented by explicit utility vectors.
Substituting the two objective identities into the assumed guarantee yields exactly \(W(S)\geq\rho W^\star\). The returned program is already a feasible source solution, so no additional decoding argument is needed. This contradicts the cited hardness unless \(\mathrm{P}=\mathrm{NP}\).
For fixed \(q\), the item count \(m=2q\) is fixed, and exhaustive enumeration is polynomial in the remaining input length. For \(\rho>1\), the all-one type has utility and optimum equal to \(2\), making the requested guarantee impossible.
No additional clarification or repair 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.