| paper | d4-conf-atal-2014-0061 |
| 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→P discrete result → its continuous mirror
Answer: Polynomial-time solvable: in \(\mathrm{P}\), with running time polynomial in \(m,\tau,L\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 3
statement extracted from the paper’s text layer
Given candidates \(C \cup \{p\}\), a common order \(L\), fixed \(r \ge 3\), and \(\tau\) ranking types that are 2-peaked with respect to \(L\), each with rational mass \(\mu_t \ge 0\) and \(\sum_t \mu_t = 1\), plus a rational deletion budget \(\rho\), does there exist deleted mass \(x_t \in [0,\mu_t]\) with \(\sum_t x_t \le \rho\) such that \(p\) is the unique \(r\)-approval winner among the remaining mass; that is, \(\sum_t (\mu_t-x_t)a_{t,p} > \sum_t (\mu_t-x_t)a_{t,c}\) for every \(c \in C\), where \(a_{t,c}\) indicates whether type \(t\) ranks \(c\) in its top \(r\)?
Each type is a complete 2-peaked ranking under \(L\), with mass \(\mu_t\). Choose deletion amounts \(x_t \in [0,\mu_t]\) minimizing \(\sum_t x_t\), subject to the remaining mass making \(p\)'s \(r\)-approval score strictly exceed every rival's; a budgeted decision version uses \(\sum_t x_t \le \rho\).
The event-day example does not explain why an organizer may discard valid ballots based on their rankings, so it supports only settings where an authorized chair controls which ballots count.
fatal: False
The mirror covers Theorem 3's unique-winner vote-deletion result for fixed \(r \ge 3\) in 2-peaked elections; it does not cover the paper's other control actions or parameterized results.
My strongest mirror is the paper’s vote-deletion result. Theorem 3, proved in this paper, says that for every fixed constant \(r\ge 3\), constructive control by deleting votes in \(r\)-approval is NP-complete even when the election is restricted to 2-peaked votes with a given harmonious order. The proof establishes the unique-winner case by reduction from Vertex Cover on bounded-degree-3 graphs; the paper says the corresponding nonunique-winner results follow as well. I would mirror the unique-winner version, which the proof treats directly.
Call the mirror Minimum-Mass 2-Peaked \(r\)-Approval Deletion Control. An instance gives candidates \(C\cup\{p\}\), a common order \(L\), a fixed \(r\ge3\), and a list of \(\tau\) complete rankings \(\pi_t\), each 2-peaked with respect to \(L\), with rational masses \(\mu_t\ge0\) summing to \(1\). It also gives a deletion budget \(\rho\in[0,1]\). A solution is a vector \(x_t\) of deleted mass, where \(0\le x_t\le\mu_t\) and \(\sum_t x_t\le\rho\), such that \(p\) is the unique winner among the remaining mass. Writing \(a_{t,c}=1\) if \(c\) is in the top \(r\) of \(\pi_t\), and \(0\) otherwise, the winning condition is
\[
\sum_t(\mu_t-x_t)a_{t,p}>\sum_t(\mu_t-x_t)a_{t,c}
\quad\text{for every }c\in C.
\]
The decision question is whether such an \(x\) exists within budget \(\rho\); the optimization version minimizes the mass removed. This mirrors the paper’s operation, target, scoring rule, and winner condition. For a discrete election with \(N\) voters, type counts \(n_t\), and deletion limit \(R\), the corresponding masses are \(\mu_t=n_t/N\) and \(\rho=R/N\). The continuous version allows an arbitrary fraction of each type’s mass to be removed.
This has a plausible high-multiplicity setting in the paper’s own event-day example: a city or large organization chooses a date from a commonly ordered calendar, with many respondents sharing each of a modest number of ranking patterns. The rankings can have two peaks, as when people have two clusters of favored dates. A platform or organizer that controls which submitted ballots count can face the paper’s deletion-control question in this setting, with the budget understood as a fraction of the electorate. A ranking is a sufficient type here: the problem uses no voter-specific attributes, and voters with the same ranking contribute identically to every candidate’s score.
I expect this continuous problem to be tractable (Class A). For the listed support, the inequalities are linear in the \(\tau\) deletion variables. To handle the unique-winner condition, maximize a common slack \(\epsilon\) subject to \(S_x(p)\ge S_x(c)+\epsilon\) for every \(c\), along with the mass bounds and budget. A solution exists exactly when the optimum slack is positive. This is a rational linear program with \(\tau+1\) variables and a number of constraints polynomial in \(m\) and \(\tau\). Thus the paper’s discrete hardness has a straightforward continuous counterpart whose decision version is in P. The 2-peaked restriction remains part of the instance; the algorithm does not need to exploit it.
The scope is deliberately narrow: this mirrors Theorem 3 and the hardness of deleting votes for fixed \(r\ge3\), not the paper’s other control actions or its parameterized results. It also raises a useful bridge question: for discrete high-multiplicity elections with only a modest number of ranking types, what approximation or additive-error guarantee can convert a fractional deletion plan into an integral one? A related question is which realistic cohort-level restrictions on deletion preserve the LP structure.
The weakest point is the regime, not the type definition. The paper’s hardness reduction uses one vote per graph vertex; it does not itself exhibit many voters per type. So the result is a computational anchor for the mirror, not evidence that its hard instances already look like high-multiplicity societies. The case rests on a separate, plausible large-electorate scenario and on deletion of ballot mass being meaningful there. If the application requires indivisible, individually targeted ballots, this mirror would miss that feature; where the organizer acts on large interchangeable cohorts, the mass version is a direct continuization of the authors’ problem.
The strongest objection is to the event-day scenario, not to the formal mirror. A real organizer usually cannot remove valid ballots just because their rankings help a candidate; legitimate exclusion depends on provenance or eligibility, which rankings do not capture. If the mirror is meant to represent that real process, its types and deletion operation are incomplete.
But this does not defeat the better version of the mirror. The paper’s abstract problem allows a chair to delete registered votes, and an election or platform can plausibly give a chair that authority. If eligibility matters, it can be included in the type; voters identical on every feature the operation uses can be treated as mass. The paper itself studies only constructive control and uses no voter-specific attributes that would prevent that grouping.
The resulting question is well-posed: for each listed ranking type, choose deleted mass \(x_t\) with \(0\le x_t\le\mu_t\), and ask whether the remaining society makes \(p\) the unique winner within budget \(\rho\). Its score constraints are linear; maximizing a common winning margin handles strict uniqueness. For a discrete election with \(N\) voters, the corresponding masses are \(n_t/N\) and \(R/N\). That correspondence makes this a direct high-multiplicity mirror of Theorem 3.
I cannot honestly defeat this anchor. The realistic scenario may be contestable, but the paper’s abstract operation has a plausible cohort setting, and the model needs no unnatural change to make mass meaningful. The negative case is weak here.
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.