| paper | Metric Distortion of Line-up Elections: The Right Person for the Right Job |
| authors | Christopher Jerrett, Yue Han, Elliot Anshelevich |
| venue | AAAI 2025 |
| filed under | voting · distortion |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
The paper has no named theorem asserting the complexity or solvability of a computational problem; its numbered results concern distortion guarantees and mechanism performance. A weighted-population version of Corollary 3.7 is plausible and recognisable, but it is a routine high-multiplicity restatement and cannot overcome failure of bit (a).
fails bit a — no named computational result to mirror
The mirror covers only the ordinal-voter iterative-election guarantee behind Theorem 3.6 and Corollary 3.7; it leaves the position-preference and candidate/position-location variants untouched.
The strict answer is that this paper has no qualifying named complexity anchor. Its numbered results are distortion guarantees and lower bounds, not theorems that a problem is in P, NP-hard, FPT, and so on. Thus a literal ChoCo screening would record “no anchored computational mirror.”
The strongest positive case, if named approximation mechanisms are admitted as computational anchors, is nevertheless quite concrete.
My lead anchor is Corollary 3.7, proved in this paper:
“Iterative election with plurality veto gives a distortion of at most 7.”
Its proof rests on Theorem 3.6, also proved here, which gives \(2\delta_{\mathrm{itr}}+1\); the value \(\delta_{\mathrm{itr}}=3\) comes from cited standard-election results of Gkatzelis–Halpern–Shah and Kizilkaya–Kempe. This is an approximation/algorithmic result, although not a complexity-class result.
The corresponding problem is Continuous Robust Line-up Election with Ordinal Voter Types.
An instance contains finite candidates \(C\), positions \(P\), with \(|P|=\ell\le m=|C|\), and a rational mass distribution \(\mu\) over finitely many voter-profile types. A type specifies, for every position \(p\), a strict ranking of candidates according to the paper’s quantity \(d(v,c)+d(c,p)\). The mass \(\mu_t\) is the fraction of the electorate having that complete observable profile.
The mechanism is not given the hidden distances. It receives only the weighted ordinal profile. A compatible realization is any common metric space containing voters, candidates, and positions whose induced rankings agree with the profile. For an injective matching \(M:P\to C\), define
\[ SC_d(M)= \sum_t \mu_t\sum_{p\in P} \bigl(d(t,M(p))+d(M(p),p)\bigr), \]
and
\[ \operatorname{dist}(M)= \sup_{d\text{ compatible}} \frac{SC_d(M)} {\min_{M'}SC_d(M')}. \]
The task is: given the rational weighted ordinal profile, output an injective matching with distortion at most \(7\).
The continuous algorithm is exactly the paper’s iterative election, with sums over voters replaced by weighted sums over types. Process positions in a fixed order. At each step, restrict every type’s ranking to the remaining candidates, run weighted plurality veto—equivalently, choose the candidate with minimum weighted last-place mass—and remove the winner. The output remains an integral matching; no fractional assignment is introduced.
This should be tractable, Class A, for the stated seven-distortion task. Each round requires only weighted tallying over the \(\tau\) types, so the running time is polynomial in \(\tau,m,\ell\) and the mass bit-length. The proof of Theorem 3.6 survives verbatim after replacing voter sums by mass-weighted sums. Rational-clone fidelity is exact: clearing denominators produces a finite election with repeated voter clones, while every social cost is multiplied by the same denominator and every distortion ratio is preserved.
A credible regime is a large professional association, university, club, or public organization choosing \(\ell\) role-holders from a fixed candidate pool. There may be millions of members but only a few dozen recurring constituency profiles—departmental, geographic, ideological, or occupational cohorts—with identical ordinal judgments about candidates for each role. Candidates and positions remain the finite combinatorial objects; the population is the part that is naturally represented by proportions. This is close to the authors’ own committee and sports-team motivation, and it does not alter their common-metric assumption or their information restriction.
The mirror covers only the ordinal-voter-preference result leading to Corollary 3.7. It does not claim to continuize every location-information variant in the paper. Natural follow-up questions are whether the optimal robust matching can be computed exactly, whether the bound \(7\) can be improved under weighted profiles, and whether exact distortion admits a separation formulation over compatible metric completions.
The weakest point is substantial: the mirror is primarily a high-multiplicity compression of an approximation theorem, not a new complexity landscape. The paper contains no source hardness to dissolve, and the proof adds no LP, pricing, or genuinely new continuous optimization. Moreover, if nearly every voter has a distinct ranking profile, then \(\tau\approx n\) and the computational gain disappears. I would therefore present this as a defensible positive extension—probably orange rather than a clean green result—not as a fully compliant ChoCo Class-A anchor under the strict complexity-theorem rule.
The strongest negative point is decisive under ChoCo’s stated screening rule: this paper has no qualifying computational anchor. Corollary 3.7 is a distortion guarantee for a voting mechanism, not a theorem about the complexity of an exact, approximation, or parameterized computational problem. The same is true of Theorems 3.2–5.3. Thus a continuous mirror would not be continuizing one of the paper’s computational results; it would be inventing a new problem around a distortion theorem.
The proposed Corollary 3.7 mirror is mathematically legitimate in a narrow sense, but it is too thin to justify programme time. Weighted plurality veto merely replaces voter counts by weighted counts. The output is still an ordinary integral matching, and the algorithm is just repeated tallying over candidates. Clearing denominators and cloning voters proves precisely that this is a compressed representation of the original finite procedure. It introduces no mass-transfer problem, exponential-variable LP, separation problem, or new complexity boundary. The paper’s proof already works for arbitrary voter weights; writing the sums as integrals adds notation rather than computational content.
There is also a modelling defect in the proposed type space. A ranking vector is not a complete type for this paper’s objective. Two voters can have identical rankings for every position while having very different cardinal distances to candidates. Those distances determine both the social cost of the chosen matching and the omniscient benchmark in the distortion denominator. The expression \(d(t,c)\) in the proposed mirror silently replaces an entire class of compatible latent voters by one representative metric point. The clone argument establishes fidelity only for the restricted scenario in which all members of a cohort have identical latent distances, not for the paper’s ordinal-information model generally.
The obvious repair does not rescue the anchor. If a type records its full cardinal distance vector and the distribution of such types is known, the optimum is simply a minimum-weight bipartite matching with edge weight
\[ \int d(v,c)\,d\mu(v)+d(c,p). \]
The population distribution contributes only aggregate edge coefficients. If those cardinal types are hidden and only weighted rankings are given, a faithful model must optimize over all measures or metric completions consistent with the rankings. That is a new robust metric-completion problem, absent from the paper and from the proposed mirror; it cannot be presented as the continuous version of Corollary 3.7.
The population axis is not intrinsically nonsensical here. Large organizations with repeated voter cohorts are plausible, and additive social cost makes mass a meaningful quantity. That is why the universal claim “no scenario could work” is too strong in an absolute modelling sense. If ChoCo admits any weighted extension of a distortion theorem as an anchor, this paper is a defensible weak or orange candidate.
But under the programme’s actual standard, the negative case wins: the paper supplies no named computational result, and its best apparent mirror is a routine weighted restatement of an already polynomial finite mechanism, with its proposed type definition not fully faithful to the hidden metric objective. It should not receive a green computational-continuization verdict.
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.