| paper | Plurality Veto: A Simple Voting Rule Achieving Optimal Metric Distortion |
| authors | Fatih Erdem Kizilkaya, David Kempe |
| venue | IJCAI 2022 |
| filed under | voting · distortion |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c22r1) |
| judge confidence | high |
| authors would recognise it | yes |
The paper’s numbered results establish distortion and matching properties, but none states the complexity or tractability of a computational problem such as polynomial-time solvability or hardness. Theorem 1 and Theorem 3 are rule-level distortion guarantees, which the rubric expressly excludes from bit \(a\). The scheduled mass mirrors are coherent continuous analogues, but they cannot supply the missing computational anchor.
fails bit a — no named computational result to mirror
The proposed mirror covers population versions of Theorems 1 and 3, while leaving Theorem 2 as supporting matching machinery, communication bounds, peer-selection geometry, and incentive questions outside scope.
The paper contains no NP-hardness, FPT, or other explicit complexity classification. Its relevant anchors are algorithmic distortion theorems, both proved in the paper. My strongest mirror is Theorem 1; Theorem 3 is a useful second anchor.
The natural regime is a large public consultation or election with a fixed, moderate slate of policy candidates. Millions of agents can share one of relatively few complete rankings, because they belong to recurring constituencies or stance profiles. Let \(T\) be the ranking types and let \(\mu_t\) be the fraction of the population of type \(t\), with \(n\gg |T|\). Candidates and voters are still embedded in the paper’s latent metric space; only the rankings are observed. The processing order can be a publicly fixed order of type blocks, which the paper explicitly permits because PLURALITYVETO works for any voter order.
My lead problem is Continuous PluralityVeto Metric Distortion. An instance consists of \(C\), a finite ranking-type set \(T\), a rational society distribution \(\mu\), and a finite ordered schedule of type blocks whose masses sum to one. Define the initial residual score of candidate \(c\) by \(r_c(0)=\sum_{t:\operatorname{top}(t)=c}\mu_t\). Process population mass continuously according to the schedule: an infinitesimal mass of type \(t\) decrements the residual score of its bottom-ranked candidate among those with positive residual score. The last candidate remaining is the output \(c_{\mathrm{PV}}\).
For a compatible metric realization \(d\), write \(SC_\mu(c;d)=\int d(x,c)\,dx\), where \(x\) ranges over voter mass. The continuous task is to compute \(c_{\mathrm{PV}}\) and guarantee
\[ SC_\mu(c_{\mathrm{PV}};d)\le 3\min_{a\in C}SC_\mu(a;d) \]
for every metric consistent with the ranking types. The solution is the candidate produced by the mass process; its objective value is its worst-case metric distortion.
This is a faithful population analogue of Theorem 1, “The distortion of PLURALITYVETO is 3,” proved in the paper. The proof lifts cleanly: every infinitesimal veto can be paired with an equal mass of voters whose top choice is the vetoed candidate. For the final candidate \(c_{\mathrm{PV}}\), each processed voter ranks \(c_{\mathrm{PV}}\) at least as high as the paired voter’s top choice. Thus the discrete perfect matching becomes a measure-preserving fractional coupling, and the paper’s Lemma 1 applies by integration. The continuous problem should therefore be Class A: with rational masses and type-block schedules, the residual process has only polynomially many score-change events and can be simulated exactly.
The second anchor is Continuous \(\kappa\)-Round PluralityVeto. Its input adds a rational \(\kappa\in[0,1)\). Run the same process only until population mass \(\kappa\) has been processed, obtaining residual scores \(r_c(\kappa)\). Output the candidate distribution
\[ w_c=\frac{r_c(\kappa)}{1-\kappa}. \]
The task is to compute \(w\) such that, for every compatible metric realization,
\[ \sum_{c\in C}w_c\,SC_\mu(c;d) \le 3\min_{a\in C}SC_\mu(a;d). \]
This mirrors Theorem 3, “The distortion of \(k\)-ROUNDPLURALITYVETO is at most 3,” also proved here. The discrete parameter \(k\) becomes a population fraction \(\kappa=k/n\); \(\kappa=0\) is continuous random dictatorship, while the endpoint \(\kappa=1\) recovers the deterministic mirror above. The paper’s flow proof becomes a flow of mass, with sideways transport replaced by a coupling between voter-type mass and candidate residual mass. This also looks Class A for finite \(T\): computing \(w\) is polynomial, and the distortion certificate is a finite transportation/flow argument after types are aggregated.
Theorem 2 provides supporting evidence but I would not count it as a third anchor. Its fractional veto construction already uses arbitrary weights \(p\) and \(q\), and after aggregation it becomes an ordinary finite transportation problem. That is useful machinery for the two mirrors, but presenting it as a separate contribution would risk padding the case.
The weakest point is the order. A continuum has no canonical “next voter,” whereas PLURALITYVETO is explicitly sequential and order-dependent. My mirror therefore includes a finite type-block schedule as part of the policy. This is defensible because the paper allows any order, but it means the mirror covers a scheduled or batched version of the rule, not an order-free social choice function. A second weakness is that the paper proves a distortion guarantee rather than an optimization or complexity classification; this mirror shows that the algorithmic distortion theorem survives continuization, but it does not yet produce the programme’s preferred hardness-versus-tractability landscape.
The main follow-up questions are whether the best continuous rule has distortion strictly below \(3\), whether the guarantee is independent of the schedule, how much schedule randomization helps, and how precisely the continuous rule rounds back to finite elections without losing its guarantee.
The negative case is stronger than claiming that the proposed mirrors are formally invalid. They are formally valid. The problem is that neither anchor is a computational result in ChoCo’s sense. Theorem 1 and Theorem 3 are distortion guarantees for an already very simple voting rule, not complexity, optimization, approximation, or parameterized results. The continuous versions therefore need to create a new computational problem; merely computing the rule on weighted votes does not do so.
For Theorem 1, once an explicit distribution \(\mu\) and a type-block schedule are supplied, the proposed process is just a weighted simulation of PLURALITYVETO. Candidate \(c\)’s initial score is
\[ r_c(0)=\sum_{t:\operatorname{top}(t)=c}\mu_t. \]
During a block of type \(t\), one decreases the score of the currently lowest active candidate until either the block ends or that candidate is eliminated. There are only schedule-boundary events and candidate-elimination events, so the process is exactly simulable with rational arithmetic. If the masses have denominator \(N\), it is literally the discrete process on \(N\) cloned voters, processed in the corresponding block order. The “continuous perfect matching” is likewise just the discrete matching proof with sums replaced by masses.
That is a legitimate weighted implementation, but it does not expose the kind of computational phenomenon the programme is designed to study: there is no exponential-variable LP, no pricing problem, no meaningful separation question, and no population-driven combinatorial obstacle. The continuous input is only a succinct encoding of a process that already aggregates immediately.
More seriously, \(\mu\) alone does not determine the proposed winner. PLURALITYVETO is order-dependent; the paper explicitly identifies the dependence of the outcome on the voter-processing order as a difficulty. A distribution over ranking types contains no order. Supplying a type-block schedule repairs the definition, but makes the schedule an additional temporal input rather than part of the continuous society. Using a random schedule introduces a distribution over sequences; taking all schedules produces a possible-winner or schedule-robustness problem. Those could be interesting sequential-mechanism questions, but they are new problems whose substance comes from scheduling, not from continuizing the population.
There is also a modelling mismatch in the metric objective. A ranking distribution \(\mu\) does not determine
\[ SC_\mu(c;d)=\int d(x,c)\,dx, \]
because voters with the same ranking may have different latent distances. If those distances are part of the type, then the type is a joint ranking-and-metric type, potentially drawn from a continuum rather than the finite ranking set \(T\). If they remain adversarial latent data, then the continuous society is still only \(\mu\), while the actual objective depends on an unrepresented individual-level metric. The paper’s universal distortion proof survives this issue, but precisely because it avoids computing the metric: the metric information contributes no new continuous computational object.
Theorem 3 has the same defect. For fixed \(\kappa\), the residual distribution
\[ w_c=\frac{r_c(\kappa)}{1-\kappa} \]
is obtained by the same weighted scan. The flow argument lifts to a mass coupling with no substantive algorithmic change. Optimizing over \(\kappa\), schedules, or schedule distributions could be worthwhile, but then the research question is optimal scheduling or robust mechanism design. It is not the computational content of Theorem 3, whose claim is simply that every permitted stopping time has distortion at most \(3\).
Theorem 2 reinforces rather than rescues this conclusion: the paper already permits arbitrary weights \(p\) and \(q\) and proves a fractional matching statement. Continuizing the electorate adds another layer of weighted notation to machinery that is already fractional.
The proponent is right that recurring constituencies make a high-multiplicity ranking profile sensible. Thus the negative case is not that a formal mirror cannot be written, nor that its proof would fail. It is that the only faithful mirrors are direct weighted restatements with trivial computation, while every version with genuine computational content must add ordering, metric-type, or mechanism-design structure absent from the population model. On the evidence of this paper, neither Theorem 1 nor Theorem 3 supplies a worthwhile ChoCo 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.