Answer: \(\mathrm{NP\text{-}hard}\).
Theorem 4 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateIt is NP-hard to approximate MDJR and MDEJR within a factor of 1 𝑘 1−𝜖 for any 𝜖> 0. We will simultaneously prove these theorems by constructing a hard ballot instance that is used for all of them. We will make sure the instance we constructed has no ℓ-cohesive group with ℓ> 1. Notice that the JR degree and the EJR degree for any committee are always the same for instances with only 1-cohesive groups.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given candidates \(C\), committee size \(k\), an explicit finite support \(T\subseteq 2^C\), and rational masses \(\mu_A\ge 0\) summing to \(1\), with some candidate supported by mass at least \(1/k\), choose \(W\in\binom{C}{k}\) maximizing \(\operatorname{jrdeg}_\infty(\mu,W)=\min_{c:\sum_{A\ni c}\mu_A\ge 1/k}\max\{0,1/k-\sum_{A\ni c,\,A\cap W=\varnothing}\mu_A\}\); determine whether a polynomial-time algorithm can guarantee \(\operatorname{jrdeg}_\infty(\mu,W)\ge (1/k)^{1-\varepsilon}\operatorname{OPT}_\infty(\mu)\), where \(\operatorname{OPT}_\infty(\mu)=\max_{W'\in\binom{C}{k}}\operatorname{jrdeg}_\infty(\mu,W')\).
Definitions. The input explicitly lists rational masses \(\mu_A\ge 0\) for approval types \(A\subseteq C\), with \(\sum_A\mu_A=1\), and an integer \(k\). For a size-\(k\) committee \(W\), let \(\delta_{\mathrm{EJR}}(W)\) be the infimum, over \(\ell\in[k]\), \(L\subseteq C\) with \(|L|=\ell\), and \(0\le g_A\le\mu_A\) supported on \(A\supseteq L\) with \(\sum_A g_A\ge\ell/k\), of \(\sum_A g_A\mathbf{1}[|A\cap W|\ge\ell]\). Assume at least one such triple exists.
Target. Is maximizing \(\delta_{\mathrm{EJR}}(W)\) over \(W\subseteq C\) with \(|W|=k\) solvable in polynomial time, or is it NP-hard?
Nearest known results. For finite approval profiles, maximizing the corresponding EJR degree (MDEJR) is NP-hard to approximate within \((1/k)^{1-\varepsilon}\) for every \(\varepsilon>0\). The same theorem establishes this for the JR-only version, where \(\ell=1\).
The answer depends on what “explicitly lists” means:
The first interpretation is the usual weighted-profile encoding. The hardness proof below is direct and already holds when every positive-mass approval type has size \(2\) and the only feasible value of \(\ell\) is \(1\).
Fix a committee \(W\), an integer \(\ell\), and \(L\subseteq C\) with \(|L|=\ell\). Define
\[ s_L:=\sum_{A\supseteq L}\mu_A \]
and
\[ b_{L,W}:=\sum_{\substack{A\supseteq L\\ |A\cap W|<\ell}}\mu_A. \]
Thus \(s_L\) is the total mass eligible for the pair \((\ell,L)\), while \(b_{L,W}\) is the eligible mass not receiving at least \(\ell\) approved committee members.
If \(s_L\ge \ell/k\), then the minimum over the variables \(g_A\) associated with this fixed pair \((\ell,L)\) equals
\[ \max\left\{0,\frac{\ell}{k}-b_{L,W}\right\}. \]
For every feasible \(g\), at most \(b_{L,W}\) mass can be chosen from types satisfying \(|A\cap W|<\ell\). Since the total chosen mass is at least \(\ell/k\), the mass chosen from types satisfying \(|A\cap W|\ge\ell\) is at least
\[ \max\left\{0,\frac{\ell}{k}-b_{L,W}\right\}. \]
This proves the lower bound.
For attainability, first suppose \(b_{L,W}\ge\ell/k\). Because the variables \(g_A\) are fractional, one can choose exactly \(\ell/k\) mass from the bad types, obtaining objective value \(0\).
Now suppose \(b_{L,W}<\ell/k\). Choose all bad mass and then choose exactly \(\ell/k-b_{L,W}\) mass from good types. This is possible because
\[ s_L-b_{L,W}\ge \frac{\ell}{k}-b_{L,W}. \]
The resulting objective value is exactly \(\ell/k-b_{L,W}\). This proves the lemma. \(\square\)
Consequently,
\[ \delta_{\mathrm{EJR}}(W) = \min_{\substack{1\le\ell\le k,\ |L|=\ell\\ s_L\ge\ell/k}} \max\left\{0,\frac{\ell}{k}-b_{L,W}\right\}. \]
In particular, the fractional nature of \(g_A\) is fully accounted for by this closed formula.
We use the following standard \(\mathrm{NP\text{-}complete}\) problem:
Given a simple \(3\)-regular graph \(G=(V,E)\) and an integer \(k\), decide whether \(G\) has a vertex cover of size at most \(k\).
We may restrict to instances satisfying \(n/2\le k\le n\), where \(n:=|V|\). Indeed, if \(S\) is an independent set in a \(3\)-regular graph, all \(3|S|\) edges incident with \(S\) lead to \(V\setminus S\), which has total degree \(3|V\setminus S|\). Hence \(|S|\le|V\setminus S|\). The complement of every vertex cover is independent, so every vertex cover has size at least \(n/2\). Instances with \(k<n/2\) are therefore automatically negative.
Let \(G=(V,E)\) be a simple \(3\)-regular graph, let \(n:=|V|\), and let \(m:=|E|=3n/2\). Define the approval instance as follows:
The positive masses sum to \(m\cdot(1/m)=1\), and the construction has \(m\) positive-mass approval types, so it is polynomial under sparse explicit-support encoding.
For each vertex \(v\), its approving mass is
\[ s_{\{v\}}=\frac{\deg(v)}{m}=\frac{3}{3n/2}=\frac{2}{n}. \]
Since \(k\ge n/2\), we have \(1/k\le2/n\). Thus every pair \((1,\{v\})\) is feasible. In particular, the promise that at least one triple exists is satisfied.
For \(\ell=2\), a set \(L\) has positive approving mass only if \(L\) is an edge. Because the graph is simple, in that case
\[ s_L=\frac{1}{m}=\frac{2}{3n}. \]
But \(k\le n\), and therefore
\[ \frac{2}{k}\ge\frac{2}{n}>\frac{2}{3n}=s_L. \]
Hence no pair with \(\ell=2\) is feasible. For \(\ell\ge3\), no positive-mass approval type contains \(L\), so \(s_L=0<\ell/k\).
Therefore the full EJR-degree objective coincides with its \(\ell=1\), JR-only part on these instances.
For \(v\in V\), let \(r_W(v)\) denote the number of edges incident with \(v\) that are disjoint from \(W\). For \(L=\{v\}\), the bad eligible mass is
\[ b_{\{v\},W}=\frac{r_W(v)}{m}. \]
The lemma therefore gives
\[ \delta_{\mathrm{EJR}}(W) = \min_{v\in V} \max\left\{0,\frac{1}{k}-\frac{r_W(v)}{m}\right\}. \]
It follows immediately that \(\delta_{\mathrm{EJR}}(W)\le1/k\).
If \(W\) is a vertex cover, every edge intersects \(W\), so \(r_W(v)=0\) for every \(v\). Hence
\[ \delta_{\mathrm{EJR}}(W)=\frac{1}{k}. \]
Conversely, suppose \(W\) is not a vertex cover. There is then an uncovered edge \(e=\{u,v\}\) with \(e\cap W=\varnothing\). Consequently \(r_W(u)\ge1\), and thus
\[ \max\left\{0,\frac{1}{k}-\frac{r_W(u)}{m}\right\}<\frac{1}{k}. \]
Therefore \(\delta_{\mathrm{EJR}}(W)<1/k\).
We have proved the exact equivalence
\[ \delta_{\mathrm{EJR}}(W)=\frac{1}{k} \quad\Longleftrightarrow\quad W\text{ is a vertex cover}. \]
A vertex cover of size at most \(k\) can be enlarged to one of size exactly \(k\), because \(k\le n\). Thus
\[ G\text{ has a vertex cover of size at most }k \quad\Longleftrightarrow\quad \max_{|W|=k}\delta_{\mathrm{EJR}}(W)=\frac{1}{k}. \]
This is a polynomial-time reduction. Hence maximizing \(\delta_{\mathrm{EJR}}\) is \(\mathrm{NP\text{-}hard}\) under sparse explicit-support encoding. The reduction also shows hardness for the JR-only version directly, without needing to transfer the finite-profile approximation theorem through a fractional-coalition relaxation.
Suppose instead that the input contains all \(T:=2^{|C|}\) values \(\mu_A\), including zero entries. Let \(N\) be the input length, so \(N\ge T\).
There are at most \(T\) committees and at most \(T\) possible sets \(L\). For each pair \((W,L)\), the quantities \(s_L\) and \(b_{L,W}\) can be computed by scanning the \(T\) approval types. The formula from Section 1 therefore yields an exact exhaustive algorithm using at most \(O(T^3)\) rational arithmetic operations. Since \(T\le N\), this is polynomial in the dense input length. Exact rational sums and comparisons also have polynomial bit complexity.
Thus the finite-profile hardness result cannot be transferred to the dense encoding: producing all \(2^{|C|}\) entries would itself be an exponential expansion.
⟨structured verdict parsed — rendered above⟩
The prover correctly derives the closed form for the fractional coalition optimization and gives a valid reduction from Vertex Cover on simple \(3\)-regular graphs. The reduction establishes NP-hardness under sparse support encoding, while exhaustive enumeration is polynomial in the length of a dense \(2^{|C|}\)-entry encoding.
There is one minor formal omission in restricting the source instances to \(n/2\le k\le n\). It is routine to resolve and does not affect the substance of the classification.
For fixed \((\ell,L,W)\), the eligible types divide into:
Every feasible selection has total mass at least \(\ell/k\). Since at most \(b_{L,W}\) can come from bad types, its good mass is at least
\[
\max\left\{0,\frac{\ell}{k}-b_{L,W}\right\}.
\]
Both attainability cases are correct:
Thus the displayed formula for \(\delta_{\mathrm{EJR}}(W)\) is correct. Replacing the infimum by a minimum is justified by the explicit attainability argument and the finiteness of the choices of \(\ell\) and \(L\).
The cited source problem—Vertex Cover on simple \(3\)-regular graphs—is a standard NP-complete problem.
The independent-set calculation is correct: if \(S\) is independent, its \(3|S|\) incident edges all cross to \(V\setminus S\), whose total degree is \(3|V\setminus S|\). Hence \(|S|\le|V\setminus S|\), so every vertex cover has size at least \(n/2\).
The statement that one may restrict to \(k\le n\) is not explicitly justified. Instances with \(k>n\) are automatically positive, so a formal many-one reduction to the restricted source language needs to specify how such trivial instances are normalized. This is a routine preprocessing detail and is only a minor gap.
The construction is polynomial under sparse support encoding:
The rational masses have polynomial encoding length.
For every vertex \(v\),
\[
s_{\{v\}}=\frac{3}{m}=\frac{2}{n}.
\]
Because \(k\ge n/2\), this is at least \(1/k\), so all singleton constraints are feasible.
For \(\ell=2\), only edge sets \(L\) have positive mass, and then
\[
s_L=\frac1m=\frac{2}{3n}<\frac2n\le\frac2k.
\]
Thus no such pair is feasible.
For \(\ell\ge3\), every approval type has size \(2\), so \(s_L=0<\ell/k\). Therefore only \(\ell=1\) contributes. All inequalities and quantifiers here are correct.
For \(L=\{v\}\), the bad eligible types are exactly uncovered edges incident with \(v\), so
\[
b_{\{v\},W}=\frac{r_W(v)}m.
\]
The resulting formula for \(\delta_{\mathrm{EJR}}(W)\) is correct.
If \(W\) is a vertex cover, every \(r_W(v)=0\), yielding value \(1/k\). If \(W\) is not a vertex cover, an uncovered edge has an endpoint \(u\) with \(r_W(u)\ge1\), and the corresponding term is strictly below \(1/k\). Hence
\[
\delta_{\mathrm{EJR}}(W)=\frac1k
\quad\Longleftrightarrow\quad
W\text{ is a vertex cover}.
\]
Enlarging a cover of size at most \(k\) to size exactly \(k\) is valid when \(k\le n\), since supersets of vertex covers remain vertex covers. The reduction therefore establishes sparse-encoding NP-hardness.
With \(T=2^{|C|}\) explicitly represented entries, there are at most \(T\) committees and \(T\) possible sets \(L\). Scanning all \(T\) approval types for every pair gives \(O(T^3)\) rational arithmetic operations. Since \(T\le N\), this is polynomial in the dense input length.
The claim about polynomial bit complexity is also sound: the bit lengths of exact sums of explicitly supplied rationals remain polynomial in the total input bit length. Costs for manipulating candidate subsets introduce additional polynomial factors but do not affect the conclusion.
State explicitly how source instances with \(k>n\) are handled when claiming restriction to \(n/2\le k\le n\). A one-line description of the normalization to a fixed admissible positive instance, or an explicit citation of the bounded-\(k\) formulation of cubic Vertex Cover, would make the reduction fully formal.
⟨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.