| paper | d4-conf-aaai-2017-0493 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 1 establishes a distortion bound, a result type the criteria explicitly exclude from computational results. The weighted-type threshold question is recognizable as a distortion question from the paper, but that does not make its theorem a computational result.
fails bit a — no named computational result to mirror
The proposed population analogue covers Theorem 1's scoring-rule lower-bound setting; it leaves the other scoring-rule and STV distortion results unaddressed.
There is a natural population-continuous version of the paper’s metric-distortion question. A complete voter type must include both a location \(x_t\) in the metric space and a ranking \(\succ_t\): voters with the same ranking but different locations can have different social costs. Give each of the \(\tau\) types a rational mass \(\mu_t\), with \(\sum_t\mu_t=1\). A scoring rule scores candidates using the weighted rankings; for STV, each mass follows its highest-ranked remaining candidate. The distortion is
\[
D_R(\mu)=
\frac{\max_{c\in R(\mu)}\sum_t\mu_t d(x_t,c)}
{\min_{c\in C}\sum_t\mu_t d(x_t,c)}.
\]
A concrete problem for a prover is: given a rational \(m\)-candidate scoring vector and threshold \(\rho\), does there exist a one-dimensional metric instance with at most \(2m\) location-ranking types and rational masses whose distortion is at least \(\rho\)? A yes-solution gives the candidate locations, voter types, and masses; a no-solution rules out every such witness. This is a population mirror of the paper’s worst-case distortion analysis.
The closest result to anchor it on is Theorem 1, proved here: for every scoring rule \(R_W\), \(\mathrm{Dist}_m(R_W)\ge 1+2\sqrt{\ln m-1}\). Its construction has \(2z\le 2m\) location-ranking types, at just two voter locations. Normalizing its integer counts gives rational masses directly. More generally, multiplying rational masses by a common denominator recovers an ordinary finite election with the same winners and distortion. A plausible regime is a large electorate concentrated in a small number of recurring ideal-point and ballot archetypes, with voter count far exceeding type count. The authors would likely recognize this as their metric-preference problem with population mass replacing headcount.
But Theorem 1 is a distortion bound, not a result about a problem being in P, NP-hard, FPT, or similar. The paper’s named theorems concern distortion bounds; it has no anchor meeting the requested computational-complexity criterion. The theorem supplies yes-instances for the proposed mirror, not a complexity classification. For a fixed metric and fixed society, scoring-rule distortion is easy to evaluate by computing scores and weighted distance sums; the harder additional question is how distortion can be optimized over masses or metric instances.
That is the weak point: this is a credible population-continuous analogue, but it largely preserves the paper’s existing performance analysis rather than opening a new complexity landscape. I would not assign it a Class A/B/C expectation from this paper.
The strongest objection is that there is no named computational result here to continuize. The paper’s theorems bound worst-case distortion; they do not classify the complexity of an algorithmic problem. The proposed threshold question turns that analysis into a decision problem, but that is a new problem layered on top of the paper, not a continuous version of one it studies.
For Theorem 1, the population change is also an exact reparameterization. If type \(t\) has \(n_t\) voters among \(n\), set \(\mu_t=n_t/n\). Weighted scores and social costs are then the original totals divided by \(n\), so the winners and distortion ratio are unchanged. Conversely, every rational mass vector in the proposed model can be multiplied by a common denominator to recover a finite election with exactly the same winners and distortion. The theorem’s own construction already uses at most \(2m\) location-and-ranking types, so the proposed witness restriction does not expose a new population regime.
That leaves two possible tasks. With a fixed metric and finite type menu, evaluating distortion is direct; for scoring rules, optimizing over masses can be formulated using linear score constraints and a fractional objective. If locations and geometries are quantified over instead, the task is the paper’s original worst-case distortion analysis. Either way, the continuous formulation does not give Theorem 1 a new computational target. The same normalization issue applies to the STV distortion bounds.
A weighted STV winner problem or a metric-adversary optimization problem could still be a sensible research project. But it would be an adjacent problem chosen by the continuization programme, not a computational result anchored in this paper. That distinction is where the negative case is strongest. It is not a proof that no useful project can be built around these models; it is a reason to reject Theorem 1 as the promised computational mirror.
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.