| paper | d4-conf-aaai-2021-0185 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\)-complete, and therefore \(\mathrm{NP}\)-hard. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
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\).
A finite set of candidates and a distribution \(\mu\) over \(2\)-dimensional voter types, each type defined by an ideal point and the common approval radius \(1/2\). Choose a size-\(k\) committee maximizing the mass-weighted PAV score \(\sum_i\mu_i H_{|W\cap A_i|}\), or decide whether that score reaches \(q\).
The mirror covers the PAV instance of Theorem 1’s \(2\text{D}\)-VR hardness result. It leaves the theorem’s other Thiele rules, Theorem 2’s MAV result, the one-dimensional algorithm, and the experimental observations unaddressed.
The strongest mirror is a high-multiplicity version of the paper’s PAV winner-determination problem in the \(2\text{D}\)-VR model. The society becomes continuous through voters’ mass; candidates and the committee remain finite and discrete.
Anchor. Theorem 1, proved in this paper, states: for every non-linear concave function \(w:\mathbb{N}\to\mathbb{R}\), it is NP-hard to decide whether a committee of a given size has at least a given \(w\)-Thiele score in a \(2\text{D}\)-VR election, even when all voters have the same approval radius. PAV is one such rule, with \(w(j)=H_j=\sum_{\ell=1}^j 1/\ell\) and \(H_0=0\). The paper’s proof builds hardness from Independent Set on almost integral penny graphs; it is the geometry and committee choice that carry the reduction.
The continuous question — Continuous \(2\text{D}\)-VR PAV Score. An instance consists of a finite candidate set \(C\), with rational ideal points \(y_c\in\mathbb{Q}^2\) and candidate radii zero; a support of \(\tau\) voter types, each with rational ideal point \(x_i\in\mathbb{Q}^2\), common approval radius \(1/2\), and positive rational mass \(\mu_i\), where \(\sum_i\mu_i=1\); and a committee size \(k\) and rational threshold \(q\). Type \(i\) approves
\[
A_i=\{c\in C:\|x_i-y_c\|_2\leq 1/2\}.
\]
The question is whether there is a committee \(W\subseteq C\), \(|W|=k\), such that
\[
\sum_{i=1}^{\tau}\mu_i H_{|W\cap A_i|}\geq q.
\]
A qualifying committee is the solution. This is the per-capita PAV score: each unit of population has the same approval ballot as its type, and the committee receives the mass-weighted average satisfaction.
A plausible regime is a large citywide consultation choosing a fixed-size committee of representatives or proposals. Millions of residents can be grouped into opinion archetypes with the same two-dimensional ideal point and common willingness to compromise, while candidates occupy fixed positions in that issue space. The support \(\tau\) can be hundreds while the population is millions. This is an instance regime, not a claim that every committee election has high multiplicity. The paper’s own spatial voter model and its common-radius hardness restriction make this a recognizable extension of its problem.
The authors should recognize the mirror: the approval relation and PAV objective are unchanged; the voter sum is replaced by an expectation over voter mass. Indeed, a discrete election with \(n_i\) voters of type \(i\) gives \(\mu_i=n_i/n\), and the continuous score is exactly the discrete total PAV score divided by \(n\). Theorem 1’s reduction therefore transfers to the continuous decision problem by setting the masses to the normalized voter counts and scaling the threshold. The reduction uses a common radius of \(1/2\), so this hardness holds under the stated restriction. Replicating every voter the same number of times leaves the masses and answer unchanged, allowing arbitrarily large populations per represented type.
I expect this problem to be Class B: hardness transfers. The result does not show hardness caused by a continuum; it shows that moving voter counts to rational masses does not remove hardness already encoded in the spatial candidate geometry and committee choice. Theorem 1 covers this PAV member of its wider family of non-linear concave Thiele rules. I would not extend the claim to the paper’s experimental observations or its other rules on the strength of this anchor.
The mirror opens questions about whether the problem admits useful algorithms when \(\tau\) is small, and how its exact or approximate complexity depends on \(m\), \(\tau\), and the bit length of the masses and coordinates. The anchor itself only establishes hardness when the input can grow; it says nothing about fixed \(\tau\).
That is the weakest point too: the reduction’s support grows with its geometric construction, so this is not hardness for a small fixed set of opinion archetypes. Also, rational masses preserve the normalized discrete score exactly, making this a credible continuization but a modest one: it identifies the high-multiplicity form of the authors’ problem and shows hardness survives, rather than revealing a new tractability boundary.
I cannot make a strong negative case against this anchor. Theorem 1 is a named computational hardness result, and PAV is one of its stated cases. Its voters are interchangeable for the objective once their approval ballots are fixed, so voter mass is a natural replacement for voter counts. The proposed mirror preserves the paper’s \(2\text{D}\)-VR restriction, and a citywide consultation with repeated approval archetypes is a plausible high-multiplicity regime.
The strongest skeptical point is that the mirror can look like weighted PAV on a geometrically constrained approval profile, rather than a new continuous phenomenon. The paper’s hardness reduction also means the anchor may yield a Class B result rather than a tractability gain. But neither point defeats it under ChoCo’s criteria: the population is the object being continuized, and a dull or hardness-preserving answer does not make a well-posed question unworthy. The exact correspondence between normalized voter counts and rational masses is useful as the bridge, not evidence of a novelty collision. Existing high-multiplicity work likewise supports the regime rather than disqualifying it.
The practical caveat is that the archetype story is stylized, and the paper does not establish hardness for a fixed small support size \(\tau\). That limits what this anchor shows; it does not rule out a worthwhile mirror. The proponent’s single anchor survives, so the material does not support the requested universal negative case.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.