Answer: \(\mathrm{NP}\)-complete, and therefore \(\mathrm{NP}\)-hard.
Theorem 1 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateFor each non-linear concave function w: N → R, deciding if there is a committee of a given size with at least a given w-Thiele score is NP-hard for 2D-VR elec- tions, even if the voters have the same approval radii.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite candidate set \(C\) with rational ideal points \(y_c\in\mathbb{Q}^2\) and zero candidate radii, a support of \(\tau\) voter types with rational ideal points \(x_i\in\mathbb{Q}^2\), common approval radius \(1/2\), and binary-rational masses \(\mu_i>0\) summing to \(1\), a committee size \(k\), and a rational threshold \(q\), decide whether there is a committee \(W\subseteq C\), \(|W|=k\), such that \(\sum_{i=1}^{\tau}\mu_i H_{|W\cap A_i|}\ge q\), where \(A_i=\{c\in C:\|x_i-y_c\|_2\le 1/2\}\) and \(H_j=\sum_{\ell=1}^{j}1/\ell\) with \(H_0=0\).
Let \(C\) be a set of \(m\ge1\) candidates with ideal points \(y_c\in\mathbb Q^2\) and candidate radii zero. A society is given by its support: a list of \(\tau\ge1\) voter types with ideal points \(x_i\in\mathbb Q^2\), common approval radius \(1/2\), and positive binary-rational masses \(\mu_i\) summing to \(1\). Here \(\tau\) is the support size, not the number of possible types.
Type \(i\) approves \(A_i=\{c\in C:\|x_i-y_c\|_2\le1/2\}\); boundary candidates are approved, and empty approval sets are allowed. Given an integer \(1\le k\le m\) and a binary-rational threshold \(q\in\mathbb Q\), a committee is a subset \(W\subseteq C\) with \(|W|=k\). Its mass-weighted PAV score is \(\sum_{i=1}^{\tau}\mu_iH_{|W\cap A_i|}\), where \(H_0=0\) and \(H_j=\sum_{\ell=1}^{j}1/\ell\). Let \(L\) be the total binary input length.
Is deciding whether such a committee has score at least \(q\) solvable in polynomial time, or is it NP-hard? State running times in \(m,\tau,L,k\).
For finite electorates, PAV score-threshold decision is NP-hard for two-dimensional voter-range elections even when every voter has approval radius \(1/2\). This result does not explicitly impose rational ideal points; no separate continuous classification is reported here.
The decision problem is \(\mathrm{NP}\)-complete, even with dyadic masses and with every nonempty approval set containing at most two candidates.
The rational-coordinate restriction requires an additional argument beyond the stated finite-electorate hardness result. The proof below supplies that argument using a fixed geometric separation margin.
A penny representation of a graph \(G=(V,E)\) assigns a point \(p_v\in\mathbb R^2\) to each vertex such that distinct centers have distance at least \(1\), with equality precisely for adjacent vertices.
We use the following consequence of the explicit construction underlying penny-graph hardness:
Independent Set is \(\mathrm{NP}\)-hard on penny graphs of maximum degree at most \(3\), even when a penny representation is supplied whose coordinates can be approximated to any prescribed rational accuracy in polynomial time.
Here polynomial time includes the size of the representation. To verify the representation requirement, the construction starts with a polynomial-size orthogonal integer-grid drawing and replaces edges by chains of disks, with a fixed local displacement to adjust parity. All ordinary centers are integral; the displaced centers use fixed algebraic offsets. These constructions appear in [Cerioli et al., Theorem 1.2 and Corollary 1.3](https://www.numdam.org/item/10.1051/ita/2011106.pdf) and are reproduced for cubic planar Independent Set in [Godziszewski et al., Section 4.2](https://comsoc-community.org/assets/proceedings/comsoc-2021/GodziszewskiEtAl.pdf).
For completeness, the displacement replacing the middle center between \((-1,0)\) and \((1,0)\) can use
\[ \text{ } \]
\(a=(-1/8,\sqrt{15}/8),\qquad b=(1/8,-\sqrt{15}/8).\)
The three consecutive squared distances are
\((-1-a_1)^2+a_2^2=1,\qquad \|a-b\|_2^2=1,\qquad (1-b_1)^2+b_2^2=1.\)
The two nonconsecutive squared distances are \(3/2\). Translations and quarter-turns of this fixed gadget introduce only coordinates in \(\mathbb Q(\sqrt{15})\), with polynomial encoding length. Approximating them is therefore effective in polynomial time, for example by rational bisection for \(\sqrt{15}\).
Take an instance \((G,r)\) from this hard family, with \(1\le r\le |V|\). Write \(n=|V|\), \(e=|E|\), and \(d_v=\deg_G(v)\).
First contract the supplied drawing by a factor of \(3/4\). Choose rational candidate points \(y_v\) satisfying
\(\|y_v-(3/4)p_v\|_2\le \varepsilon,\qquad \varepsilon=1/100.\)
The preceding representation property lets us compute these points in polynomial time with polynomial encoding length.
For each edge \(uv\in E\), place a voter type at the rational midpoint
\(x_{uv}=(y_u+y_v)/2.\)
This type approves exactly the candidates \(u\) and \(v\).
Indeed, its distance to either endpoint is at most
\(\frac12\bigl((3/4)\|p_u-p_v\|_2+2\varepsilon\bigr)=3/8+\varepsilon<1/2.\)
For any other vertex \(w\), let \(z=(p_u+p_v)/2\). The parallelogram identity gives
\(\|p_w-z\|_2^2=\frac{\|p_w-p_u\|_2^2+\|p_w-p_v\|_2^2}{2}-\frac{\|p_u-p_v\|_2^2}{4}\ge 3/4.\)
Here both distances involving \(w\) are at least \(1\), while \(\|p_u-p_v\|_2=1\). Consequently,
\(\|y_w-x_{uv}\|_2\ge 3\sqrt{3}/8-2\varepsilon>1/2.\)
The last inequality follows already from \(\sqrt{3}>3/2\), since \(9/16-1/50>1/2\).
We can also realize a singleton approval set \(\{v\}\) by placing a voter at \(y_v\). Every other candidate is at distance at least
\(\|y_u-y_v\|_2\ge 3/4-2\varepsilon>1/2.\)
Thus all required approvals hold strictly. Boundary conventions cause no difficulty.
Set
\(N=e+\sum_{v\in V}(3-d_v)=3n-e.\)
Because the maximum degree is at most \(3\), we have \(N>0\). Let \(M\) be the smallest power of two satisfying \(M\ge N\).
Construct the society as follows:
An empty-approval type has a polynomial-size rational realization: if \(B\) is an integer greater than every candidate coordinate in absolute value, use the point \((B+2,B+2)\).
Every included mass is positive and dyadic. Their sum is \(1\). Set
\(k=r,\qquad q=3k/M.\)
To calculate a committee’s score, identify a committee \(W\) with its selected vertices and let \(e_G(W)\) denote the number of edges with both endpoints in \(W\).
For an edge voter, let \(t=|W\cap\{u,v\}|\). Since \(t\in\{0,1,2\}\),
\(H_t=t-\frac12\,\mathbf 1_{\{t=2\}}.\)
Summing over edge voters, and then adding singleton voters, yields
\[ \text{ } \]
\(M\,\operatorname{PAV}(W)=\sum_{v\in W}d_v-\frac12e_G(W)+\sum_{v\in W}(3-d_v)=3k-\frac12e_G(W).\)
The empty-approval type contributes zero. Therefore,
\(\operatorname{PAV}(W)\ge q\quad\Longleftrightarrow\quad e_G(W)=0.\)
Thus a size-\(k\) committee reaches the threshold exactly when its vertices form an independent set. An independent set of size at least \(r\) contains one of size exactly \(r=k\), so the reduction preserves both answers.
The constructed instance has
\(m=n,\qquad \tau\le e+n+1\le (5/2)m+1.\)
Since \(N\le 3m\), we also have \(M<2N\le 6m\). Masses and the threshold consequently have \(O(\log m)\) bits. Coordinates and the complete output have polynomial encoding length, and the reduction runs in polynomial time. This proves \(\mathrm{NP}\)-hardness for the stated input model.
A certificate lists \(k\) distinct candidates.
Compute each approval by comparing the rational squared distance with \(1/4\). No square-root calculation is necessary.
To bound score arithmetic, put
\(D=k!,\qquad T_j=DH_j\quad (0\le j\le k).\)
Every \(T_j\) is an integer, and these integers have \(O(k\log(k+1))\) bits. They can be computed using
\(T_0=0,\qquad T_j=T_{j-1}+D/j.\)
Write \(\mu_i=a_i/b_i\) and \(q=a_q/b_q\), with positive denominators, and set
\(R=b_q\prod_{i=1}^{\tau}b_i.\)
The total input-length bound implies that \(R\) has \(O(L)\) bits. For \(t_i=|W\cap A_i|\), threshold verification is the integer comparison
\(\sum_{i=1}^{\tau}a_i(R/b_i)T_{t_i}\ge a_q(R/b_q)D.\)
All integers involved have
\(B=O(L+k\log(k+1))\)
bits. Using schoolbook arithmetic, certificate verification takes
\(O\bigl((m\tau+k+\tau k)B^2\bigr)\)
bit operations. Hence the problem belongs to \(\mathrm{NP}\), completing the \(\mathrm{NP}\)-completeness proof.
Although the unrestricted problem is \(\mathrm{NP}\)-complete, the following exact bounds apply.
Committee enumeration. After computing approvals and the integer score coefficients, enumerate all size-\(k\) committees. The running time is
\(O\left(\left[m\tau+k+\tau+\binom{m}{k}\tau(k+1)\right]B^2\right).\)
In particular, this is polynomial in \(m,\tau,L\) for each fixed \(k\).
Dynamic programming for fixed support size. Process candidates sequentially. A state records
\((s,t_1,\ldots,t_\tau)\in\{0,\ldots,k\}^{\tau+1},\)
where \(s\) is the number selected and \(t_i\) counts selected candidates approved by type \(i\). Initially only the zero state is reachable. For each candidate, either skip it or select it, increasing \(s\) and precisely those \(t_i\) whose types approve it. Discard states with \(s>k\).
Induction over processed candidates proves that the table records exactly the attainable count vectors. At the end, evaluate the exact score of every reachable state with \(s=k\).
There are at most \((k+1)^{\tau+1}\) states, giving the conservative bit-operation bound
\(O\left(\left[m\tau+k+\tau+m\tau(k+1)^{\tau+1}\right]B^2\right).\)
Since \(k\le m\), this is polynomial in \(m,L\) for every fixed support size \(\tau\). The hardness result concerns instances in which both \(k\) and \(\tau\) may grow.
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The output establishes \(\mathrm{NP}\)-completeness for the rational-coordinate, mass-weighted problem in USER_TASK. The rationalization argument supplies a uniform separation margin, the reduction preserves the decision answer, and the verification and algorithmic bounds are valid. I found no mathematical issues requiring repair.
The required source is stronger than abstract hardness for penny graphs: the reduction needs maximum degree at most three and a polynomially computable geometric representation.
The citations support these requirements. [Cerioli et al., Theorem 1.2 and Corollary 1.3](https://www.numdam.org/item/10.1051/ita/2011106.pdf) construct penny graphs by replacing edges of a planar graph of maximum degree three with disk chains, starting from a polynomial-size orthogonal grid drawing. [Godziszewski et al., Section 4.2](https://comsoc-community.org/assets/proceedings/comsoc-2021/GodziszewskiEtAl.pdf) explicitly describe the resulting degree-two and degree-three vertices and use Independent Set hardness with the geometric representation supplied.
The prover’s fixed algebraic coordinates make the approximation requirement concrete. Checking the listed gadget:
Thus the local distance claims are correct. Integral translations and quarter-turns preserve the stated fixed algebraic coordinate form. Polynomial-time rational approximation is justified.
The output therefore does not rely solely on the finite-electorate hardness statement whose coordinate encoding was left unspecified in USER_TASK.
For an edge \(uv\), the original distance is exactly \(1\). Contracting and perturbing its endpoints gives the stated midpoint-to-endpoint bound:
\(\|x_{uv}-y_u\|_2,\|x_{uv}-y_v\|_2\le 3/8+1/100<1/2.\)
For every other vertex \(w\), both original distances to the endpoints are at least \(1\). The parallelogram identity is applied correctly and yields the squared midpoint-distance bound \(3/4\).
The perturbation loss is at most \(2\varepsilon\): one \(\varepsilon\) comes from the candidate point and at most one from the midpoint. Hence the stated exclusion bound is valid:
\(\|y_w-x_{uv}\|_2\ge 3\sqrt{3}/8-1/50>1/2.\)
The numerical justification also checks: \(9/16-1/50=217/400>1/2\).
Consequently each edge type approves exactly its two endpoints, with strict inequalities.
A voter placed at \(y_v\) approves \(v\). Every other candidate is at distance at least \(3/4-1/50=73/100>1/2\), so the singleton approval claim is correct.
For the empty type, the chosen integer \(B\) exceeds every candidate coordinate in absolute value. Each coordinate difference from \((B+2,B+2)\) is greater than \(2\), so no candidate is approved. Such a \(B\) has polynomial encoding length and is computable from the rational coordinates.
Boundary approval conventions therefore cause no problem.
The handshake identity gives the stated normalization:
\(N=e+\sum_v(3-d_v)=3n-e.\)
Maximum degree three implies \(e\le 3n/2\), so \(N>0\). Every included singleton mass is positive; the empty type is included only when its mass is positive. All masses have power-of-two denominator \(M\), and their numerators sum to \(M\).
The construction satisfies all relevant input restrictions:
The support and encoding bounds are correct. In particular, \(e\le 3m/2\) gives \(\tau\le (5/2)m+1\), and \(M<2N\le 6m\) gives logarithmic encoding length for masses and threshold.
The identity \(H_t=t-\tfrac12\mathbf 1_{\{t=2\}}\) is correct for all three possible edge-voter counts.
Summing the linear edge contributions counts each selected vertex once per incident edge. Each edge wholly inside the committee contributes exactly one penalty of \(1/2\). Singleton contributions fill the degree deficit to three. Therefore the stated identity is correct:
\(M\operatorname{PAV}(W)=3k-\tfrac12e_G(W).\)
Since \(e_G(W)\) is nonnegative and \(M>0\), the threshold is reached exactly when \(e_G(W)=0\).
The distinction between an independent set of size at least \(r\) and a committee of size exactly \(r\) is handled correctly by taking a subset. Both directions of the decision reduction follow.
The certificate has polynomial length, and distinctness and cardinality can be checked within the stated conservative running time.
Squared rational distances permit exact approval tests, including equality at the boundary. No numerical approximation is involved in verification.
The arithmetic construction is valid:
The bound \(B=O(L+k\log(k+1))\) accommodates the intermediate products and sums. It also covers negative or unrestricted rational thresholds.
The verification bound \(O((m\tau+k+\tau k)B^2)\) is conservative and polynomial in the input parameters. Thus membership in \(\mathrm{NP}\) is established.
Committee enumeration exhausts precisely the \(\binom{m}{k}\) feasible committees. Its stated bound includes approval preprocessing, arithmetic preprocessing, and evaluating each committee. The conclusion for fixed \(k\) follows.
The dynamic-programming state contains all information needed for subsequent transitions and final scoring. The skip/select transitions correctly track attainable vectors, and the state bound \((k+1)^{\tau+1}\) is valid.
The stated dynamic-programming running time conservatively covers transitions and final score evaluations. Because \(k\le m\), polynomial time for every fixed \(\tau\) follows.
These parameter-dependent algorithms are consistent with hardness when both \(k\) and \(\tau\) can grow.
No mathematical repair or additional clarification is necessary. The claimed classification and the requested running-time statements are established.
⟨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.