k - ApprovalVeto: A Spectrum of Voting Rules Balancing Metric Distortion and Minority Protection

The paper has no named theorem asserting the complexity of a computational problem: Theorem 4 gives a distortion guarantee, while Theorem 2 is a structural matching characterization. The weighted continuous core mirror is recognizable and tractable, but it is already supplied by the paper's fractional-weight machinery; the exact metric-distortion LP is a new problem rather than a continuization of a computational result here.

The objection that survived

The proposed exact metric-distortion LP is not a computational result stated by the paper, while the only algorithmic candidate is already covered by its fractional-weight characterization and weighted-core computation.

What the mirror covers

The possible-winner/core-membership characterization has a natural weighted-type formulation, but the distortion bounds and minority-protection results remain performance and axiomatic statements rather than computational mirrors.

Open questions for a prover

The case FOR (proponent)

The paper has no theorem explicitly classifying a problem as NP-hard, in P, W[1]-hard, or FPT. The closest named computational result is Theorem 2, whose perfect-matching characterization immediately yields a polynomial-time possible-winner test. The strongest continuous-mirror case therefore uses Theorem 4 as the substantive anchor and Theorem 2 as its algorithmic foundation.

The natural regime is a large public-choice election—say, selecting a windfarm site, infrastructure plan, or policy—where millions of residents belong to a few stable preference clusters. A type is a complete ranking of the \(m\) candidates, together with any type-level cost information used in the metric model. The society is a rational distribution \(\mu\) over \(\tau\) types, with \(n\gg \tau\). Mass, rather than named voters, is the operative quantity: a coalition with mass \(0.17\) is the continuous counterpart of \(17\%\) of the electorate.

The paper itself makes this mirror unusually plausible. Section 2 says that the veto-core and matching characterizations extend to fractional voter weights. Thus the continuous model is not an invented weakening of \(k\)-ApprovalVeto. Each unit of population contributes \(k\) approval/veto tokens, and the sequential veto process is represented by a fractional matching of those tokens.

The lead anchor is Theorem 4, proved in this paper: every candidate in the \(k\)-approval veto core has utilitarian metric distortion at most
\[ 2\min(k+1,m)-1, \]
and the bound is tight. The upper-bound proof invokes Lemma 1 from Berger et al. and Lemma 2 from Anshelevich et al.; the paper supplies the theorem’s application to \(k\)-ApprovalVeto and its matching lower-bound construction through Lemma 3.

The corresponding problem is Continuous \(k\)-ApprovalVeto Utilitarian Distortion. An instance is
\[ (C,T,\mu,k,w,\rho), \]
where \(C\) is the candidate set, \(T\) is an explicit finite set of ranking types, \(\mu\) is a rational distribution over \(T\), \(k\in\{1,\ldots,m\}\), \(w\in C\), and \(\rho\) is a rational threshold.

Define
\[ a_{\mu,k}(c)=\sum_{t:\,c\in\operatorname{top}_k(t)}\mu_t. \]
The continuous \(k\)-approval veto core is defined by the fractional version of the paper’s matching characterization. For a metric \(\delta\) on \(T\cup C\) consistent with the rankings, let
\[ \operatorname{sc}^+_{\mu,\delta}(c) =\sum_{t\in T}\mu_t\,\delta(t,c), \]
and
\[ D^+_\mu(w) =\sup_{\delta\sim\succ} \frac{\operatorname{sc}^+_{\mu,\delta}(w)} {\min_{c\in C}\operatorname{sc}^+_{\mu,\delta}(c)}. \]

The problem asks whether \(w\) belongs to the continuous veto core and whether \(D^+_\mu(w)\le\rho\); equivalently, it may ask for the exact value of \(D^+_\mu(w)\), together with a worst-case metric witness. The action is selecting \(w\) from the continuous core, and the objective is its worst-case social-cost ratio.

This is expected to be Class A. For each possible optimal candidate \(c^\star\), normalize
\[ \operatorname{sc}^+_{\mu,\delta}(c^\star)=1, \]
impose that \(c^\star\) is socially optimal, and maximize
\[ \sum_t\mu_t\delta(t,w). \]
Metric inequalities, ranking-consistency inequalities, and the social-cost constraints form a linear program of size polynomial in \(m\), \(\tau\), and the encoding length. The continuous counterpart of Theorem 4 should therefore satisfy the same bound
\[ D^+_\mu(w)\le 2\min(k+1,m)-1. \]
The finite lower-bound elections in the paper are already rational empirical distributions, so they embed directly into this measure formulation.

The second anchor is Theorem 2, cited from Kizilkaya and Kempe [38], which states that the following are equivalent: \(w\) can win for some veto order, \(w\) is not coalition-blocked, and the \(k\)-domination graph \(G_k(w)\) has a perfect matching. Its continuous problem is Continuous Veto-Core Membership.

Given \((C,T,\mu,k,w)\), construct a flow network with source-to-type capacity \(k\mu_t\), an edge from type \(t\) to candidate \(c\) whenever \(w\succeq_t c\), and candidate-to-sink capacity \(a_{\mu,k}(c)\). Ask whether there is a flow of value \(k\). A feasible flow is the solution certificate; a minimum cut certifies non-membership.

This is again Class A. If \(\mu_t=p_t/q\), multiplying capacities by \(q\) produces an integral network. Max-flow integrality then gives an exact two-way dictionary: the continuous instance is equivalent to the finite election obtained by creating \(p_t\) voters of type \(t\). Thus this is genuinely a high-multiplicity reformulation, not merely an analogy. The paper’s fractional-weight remark makes the model recognizable to its authors, although it also means this particular core-membership result is probably not a new discovery for ChoCo.

I would not use Theorem 3 as a formal anchor, despite its appealing mass interpretation. Its content is primarily axiomatic minority protection, and axiomatic continuization is outside the programme’s scope. One can nevertheless define the obvious computational extension by replacing coalition size with mass:
\[ \lambda_\mu(S) =\sum_{t:\,C\setminus S\succ_t S}\mu_t, \]
and asking for the largest \(\ell\) such that every \(S\ni w\) satisfies
\[ \lambda_\mu(S)\le \frac{|S|}{\ell+1}. \]
That verification problem is likely polynomial for explicit \(T\), since every relevant \(S\) is a bottom segment of some ranking type. It is useful as a consistency check, but it should not carry the verdict.

The weakest point is that the paper is not itself a complexity paper. Its principal results are distortion and protection guarantees, and the fractional-weight generalization underlying Theorem 2 is already acknowledged. Moreover, the original metric-distortion model permits voters with the same ranking to have different latent distances; a high-multiplicity mirror must either regard those distances as part of the type or accept a type-homogeneous restriction. That is a real modelling choice.

The rest of the case survives because the restriction is exactly the programme’s high-multiplicity premise: agents of one type are indistinguishable in every respect used by the problem. The core, the metric objective, the possible-winner semantics, and the tradeoff controlled by \(k\) all remain intact. What continuization adds is the computational question the paper does not ask: can these guarantees and winner-selection problems be solved exactly from a compressed distribution \(\mu\), with complexity measured in \(m\), \(\tau\), and bit length rather than in the number of individual voters? For the explicit-type version, the answer appears to be yes, with flow and LP machinery.

The case AGAINST (opponent, writing after the proponent)

The negative case is strong because the paper has no qualifying computational anchor. Theorem 4 is a tight distortion guarantee, not a complexity theorem; Theorem 3 is axiomatic; and Theorem 2 is a structural characterization whose algorithmic consequence is ordinary perfect matching. Turning Theorem 4 into “compute the exact distortion of \(w\)” therefore invents a new optimization problem rather than continuizing a computational result of the paper.

Theorem 2 is the least defensible anchor for the proponent. The paper explicitly says that the veto-core characterization already extends to fractional and non-uniform voter weights, and attributes the general result to Kizilkaya and Kempe [38]. Computing the proportional veto core is also already treated algorithmically by Ianovski and Kondratev [32]. The proposed flow with capacities \(k\mu_t\) and \(a_{\mu,k}(c)\) is exactly that weighted formulation. For rational \(\mu\), denominator-clearing produces a finite cloned election with no loss of information. This is a sensible high-multiplicity representation, but it is already the paper’s recognized generalization, not a new ChoCo problem.

Theorem 4 does not rescue the case. A population of ranking types with rational masses can certainly be defined, and its utilitarian costs can be written as integrals. But the theorem’s content then transfers by replacing voter sums with weighted sums; it does not generate a computational question. The proposed LP for \(D^+_\mu(w)\) is a standard finite metric-distortion LP that the proponent has added themselves. Its polynomial solvability would be a result about that newly introduced exact-distortion problem, not about the theorem’s stated contribution.

There is also a fidelity problem. In the paper, voters sharing a ranking may nevertheless occupy different positions in the adversarial metric. A metric on \(T\cup C\) identifies all members of a type with one representative and restricts the admissible metrics. To preserve the paper exactly, one must retain a distribution of latent distance profiles inside each ranking class. If those profiles are included in the type, the type space becomes a distribution over cardinal vectors or embeddings rather than the paper’s finite ranking types. If they are not included, the mirror studies a type-homogeneous restriction. Either choice is repairable, but neither gives the proponent the claimed direct continuation: the first abandons the finite high-multiplicity model, while the second changes the distortion domain.

The same dichotomy defeats stronger variants. Keeping explicit finite types makes the model a denominator-cleared weighted election and leaves only routine flow or LP machinery. Allowing richer within-type cardinal heterogeneity creates a new distributional metric model. Using percentile or egalitarian distortion merely replaces weighted sums by quantiles or maxima; it does not restore a missing computational result from the source.

Theorem 3 cannot provide a hidden third anchor. Its contribution is a protection axiom, and its mass version would be a newly posed verification problem outside the programme’s population-computational remit. The fact that one can enumerate or optimize over solidly vetoed candidate subsets does not turn the paper’s axiomatic theorem into a computational theorem.

Thus the paper supports a reasonable weighted-election follow-up, and the high-multiplicity regime is not nonsensical. That is the honest weakness of the negative case: someone could study it productively. But it is not a worthwhile continuous mirror of this paper in the programme’s strict sense. The only apparent computational anchor is already covered by the paper’s fractional-weight machinery; the other proposed anchor requires inventing a new optimization problem whose “continuity” is just rational mass substitution.

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.