| paper | d4-conf-atal-2021-0052 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: polynomial-time solvable · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Proposition 1
statement extracted from the paper’s text layer
Given \(m\) candidates \(C\) and a finite-support distribution \(\mu\) over approval ballots \(A\subseteq C\), with binary-rational masses summing to \(1\), let \(a_c=\sum_{A:c\in A}\mu_A\). For \(q=\tfrac12\), return a largest-cardinality shortlist \(S\subseteq C\) maximizing \(\Phi_\mu(S)=\frac{\sum_{c\in S}(2a_c-1)}{\sqrt{|S|}}\) for nonempty \(S\), with \(\Phi_\mu(\emptyset)=0\).
Types are approval ballots \(A\subseteq C\), each carrying mass \(\mu_A\). The decision is a shortlist \(S\subseteq C\); its objective is \(\Phi_\mu(S)=\frac{\sum_{c\in S}(2a_c-1)}{\sqrt{|S|}}\), where \(a_c\) is candidate \(c\)’s approval share. Return a largest-cardinality maximizer.
The mirror covers Proposition 1’s \(q\)-NCSA computation result; it leaves the paper’s other axiomatic results, clustering connection, and experiments aside.
The strongest mirror is the paper’s \(q\)-NCSA computation result. Its Proposition 1, proved in this paper, says that for every \(q\in[0,1]\), the \(q\)-NCSA score of a shortlist \(S\) is
\[
\frac{1}{|S|^q}\sum_{c\in S}(2\score_E(c)-n),
\]
that \(q\)-NCSA is a shortlisting method, and that its winner set can be computed in polynomial time. The proposition’s displayed formula appears to have a typo: it says to sum over \(C\), but Rule 6 and the proof sum over \(S\).
Here is a continuous version for the concrete choice \(q=\tfrac12\). An instance consists of candidates \(C\) and a finite-support distribution \(\mu\) over approval ballots \(A\subseteq C\), with each positive mass \(\mu_A\) a binary rational and \(\sum_A\mu_A=1\). The voter types are the complete approval sets; mass \(\mu_A\) is the fraction of the electorate with ballot \(A\). Write \(a_c=\sum_{A:c\in A}\mu_A\) for candidate \(c\)’s approval share. For a nonempty shortlist \(S\), define
\[
\Phi_\mu(S)=\frac{\sum_{c\in S}(2a_c-1)}{\sqrt{|S|}},
\qquad \Phi_\mu(\emptyset)=0.
\]
The problem, Continuous \(1/2\)-NCSA Shortlisting, is to return a largest-cardinality shortlist maximizing \(\Phi_\mu(S)\). A solution is that shortlist. This is the paper’s \(q\)-NCSA objective with approval counts normalized by electorate size: the discrete score is \(n\Phi_\mu(S)\), so the maximizing shortlist is unchanged.
This is a plausible high-multiplicity regime for a large nomination or recommendation process: many people approve among a moderate candidate set, and recurring ballot patterns mean the number of distinct approval sets \(\tau\) is far smaller than the number of participants. The type definition is exact—people share a type precisely when they submit the same approval set. The authors should recognize the mirror: it preserves their ballots, candidate approval shares, objective, and tie convention, while expressing approval as a population fraction.
The continuous problem is tractable. Aggregate the \(\tau\) ballot masses into the \(m\) approval shares, sort candidates by share, and evaluate the possible non-tiebreaking prefixes. Proposition 1’s efficiency and non-tiebreaking properties justify considering those prefixes. For \(q=\tfrac12\), the objective values can be compared exactly with rational arithmetic and square-root comparisons. The resulting algorithm is polynomial in \(m,\tau\), and the input bit length. This is a tractability anchor only; the paper contains no comparable named hardness result to anchor.
The mirror covers the \(q\)-NCSA computation result, not the paper’s other axiomatic results, clustering connection, or experiments. Further questions include the exact bit complexity when rational \(q\) varies as input, and the robustness of the chosen shortlist to small changes in ballot mass.
The weakest point is that this is a modest computational mirror. The paper already proves polynomial-time computability, and \(q\)-NCSA depends only on candidate approval shares, so the continuous version does not expose a difficult pricing problem or a new optimization bottleneck. It supports the claim that the paper’s computational question has a natural population-continuous form; it does not make a strong case that continuization changes the complexity landscape.
The strongest negative point is that this is a very thin computational mirror. The continuous \(1/2\)-NCSA problem depends only on the \(m\) approval shares, not on the full distribution over ballot types. After computing those shares, one sorts candidates and checks at most \(m+1\) prefixes. The paper already gives the corresponding polynomial-time computation, so the continuous version uses the same short algorithm and opens no pricing or optimization problem.
But that does not defeat the anchor. The population interpretation is exact: in a large nomination process, people with the same approval ballot are a natural voter type, and the mass model preserves the ballots and the rule’s objective. The shortlist remains discrete, as it should; the society is what becomes continuous. The mirror is well-posed, and the paper contains no continuous computational treatment that already answers it. The fact that the resulting algorithm is simple is not a valid objection under the programme’s criteria.
There is a narrow labeling point: the result is Proposition 1, rather than a Theorem, Lemma, or Corollary. It nevertheless explicitly proves polynomial-time computability, so dismissing it on that basis would be a technicality. I cannot honestly defeat this anchor. The negative case is weak here, and the proposed mirror survives.
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.