| paper | Distortion in Voting with Top-t Preferences |
| authors | Allan Borodin, Daniel Halpern, Mohamad Latifian, Nisarg Shah |
| 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 contains named theorems, but they concern voting-rule distortion and information-theoretic limits, not computational complexity results of the required kind. The weighted high-multiplicity reformulation is legitimate and recognizable, but the exact robust optimization problem proposed by the proponent is new rather than a result of this paper. Thus bit (a) fails even though a direct population analogue exists.
fails bit a — no named computational result to mirror
The only potentially new computational formulation, optimizing the report-only distribution \(D\), is introduced by the proponent, while the direct weighted \(f_{\mathrm{mix}}\) version merely compresses duplicated voters.
fatal: True
The mirror covers Theorem 4's first-moment committee-selection construction and descriptive weighted transfers of Proposition 1 and Theorem 2; it leaves the higher-moment and metric-distortion results outside the computational mirror.
The strongest honest positive case is a continuous mirror of the paper’s first-moment committee-selection problem. It is a good population continuation, although the paper itself does not contain a named NP-hardness, \(P\), FPT, or parameterized-complexity result. Its results are distortion guarantees and information-theoretic lower bounds. Thus, this is a constructive approximation anchor for ChoCo, not evidence that the paper has already charted a complexity class.
My lead anchor is Theorem 4, proved in the paper. It constructs the rule \(f_{\mathrm{mix}}\) and proves
\[ \operatorname{dist}(f_{\mathrm{mix}}) \le \min\left(\frac{2m}{k},\,4\max\left(\frac{m}{t},\sqrt m\right)\right). \]
Theorem 4 is especially suitable because the rule is explicit: it combines a uniformly random committee with a committee generated from a stable lottery. The stable-lottery existence theorem used there is Theorem 3, cited from Cheng et al. [2020]; their polynomial-time approximate construction is the relevant algorithmic subroutine, not a result proved by the present authors.
I would call the continuous problem Continuous Top-\(t\) Committee Distortion.
An instance consists of candidates \(C\), committee size \(k\), top-\(t\) reporting, and a finite catalogue \(\Theta\) of complete voter types. A type \(\theta\in\Theta\) contains a top-\(t\) report \(\sigma_\theta\) and a normalized cardinal utility vector \(u_\theta\in\mathbb{Q}_{\ge 0}^{m}\), with \(\sum_{c\in C}u_\theta(c)=1\), consistent with that report. Types with the same report but different utilities remain distinct: the complete type includes everything relevant to welfare.
The society is a rational mass distribution \(\mu\in\Delta(\Theta)\). The voting rule does not see \(\mu\), only the reported mass vector \(\rho\), where \(\rho_\sigma=\sum_{\theta:\sigma_\theta=\sigma}\mu_\theta\). Thus cardinal utilities remain hidden exactly as in the paper’s uncertainty model. For a committee \(X\), welfare is
\[ W_\mu(X)=\sum_{\theta\in\Theta}\mu_\theta \max_{c\in X}u_\theta(c). \]
Given \(\rho\), the action is to output a distribution \(D\) over \(k\)-committees. Its robust distortion is
\[ \max_{\mu:\,\mu\text{ induces }\rho} \frac{\max_{Y\in\binom{C}{k}}W_\mu(Y)} {\mathbb{E}_{X\sim D}[W_\mu(X)]}. \]
The required solution is a report-only rule \(D=D(\rho)\) achieving the bound from Theorem 4, or an \(\varepsilon\)-approximate version of it.
The continuous analogue of \(f_{\mathrm{mix}}\) is direct. Canonically complete each top-\(t\) report to a full ranking. When \(k\le\sqrt m\), let \(\ell\) be an integer near \(k\sqrt m\), compute a stable lottery \(\Lambda\) over \(\ell\)-committees using weighted masses, sample \(S\sim\Lambda\), and then sample a uniformly random \(k\)-subset of \(S\). Mix this with a uniformly random \(k\)-committee. Stability becomes a mass inequality: for every competing committee \(S'\),
\[ \mathbb{E}_{S\sim\Lambda} \left[ \sum_{\sigma}\rho_\sigma \mathbf{1}\{S'\succ_\sigma S\} \right] \le \frac{|S'|}{\ell}. \]
For \(k>\sqrt m\), use the uniform rule as in the paper.
This is genuinely a population continuization, not continuity in the outcome space. Committees remain discrete, voters’ reports remain ordinal, and utilities remain cardinal and hidden. Only the society changes from \(n\) named voters to masses of repeated types.
The regime is plausible in a large public consultation, citizen-assembly selection, or platform decision problem. There may be millions of participants but only a few hundred recurring preference-and-utility archetypes: for example, residents with the same priorities over a fixed set of projects, or users with the same value profile over a fixed product slate. The relevant regime is \(n\gg\tau\), where \(\tau=|\Theta|\) is perhaps hundreds or thousands. A rational mass vector is exactly the high-multiplicity representation of a finite profile: multiply all masses by a common denominator \(N\), and one obtains \(N\rho_\sigma\) ordinary voters of each report type. Welfare and distortion ratios are unchanged by this blow-up.
The paper’s proof should survive this replacement almost verbatim. Its arguments use sums over voters, normalization of utilities, and inequalities about the fraction of voters preferring one committee to another. All of these become weighted sums over types. Theorem 4’s bound therefore transfers to rational populations, and approximate stable-lottery algorithms should be able to process weighted type masses without dependence on the expanded population size \(N\). This is precisely the kind of high-multiplicity compression ChoCo is meant to study.
I expect the approximate construction problem to be Class A: tractable through the stable-lottery optimization, with running time measured in \(m\), \(\tau\), the encoding length of the masses and utilities, and \(1/\varepsilon\). That claim is a proposed ChoCo result, not something established by this paper. The exact version—finding the optimal report-only distribution \(D\), rather than the particular \(f_{\mathrm{mix}}\) guarantee—could have a different complexity and is an important follow-up.
Two results calibrate the mirror without serving as additional anchors. Proposition 1, proved here, gives a single-winner rule with distortion \(O(\max(\sqrt m,m/t))\). Theorem 2, also proved here, shows that every randomized single-winner rule has matching lower-bound order for \(p=1\). Both bounds transfer under rational blow-up, so the continuous model does not trivialize the paper’s central tradeoff: reporting more than the top \(t\) candidates still ceases to help asymptotically once \(t\) reaches the \(\sqrt m\) scale.
The weakest point is source anchoring. Theorem 4 is a constructive distortion theorem, not a theorem saying that a named computational problem lies in \(P\), is NP-hard, or has some parameterized classification. The proposed mirror therefore does not by itself supply a ChoCo complexity result. Its positive value is narrower: it gives a faithful, nontrivial high-multiplicity optimization problem whose known continuous rule and tight distortion barriers lift cleanly, and whose exact and approximate computational complexity are now well-posed questions.
The negative case is strongest at the level of source anchoring: this paper contains no numbered computational result of the kind ChoCo is meant to continuize. Theorem 4, Proposition 1, Theorem 2, and the committee lower bounds are distortion guarantees or information-theoretic impossibility results. They do not classify an algorithmic problem, give a complexity bound, or identify an optimization problem whose tractability depends on population multiplicity. Theorem 3 is an externally cited existence and approximate-construction result, not a computational result of this paper.
The proposed Theorem 4 mirror is mathematically faithful, but that is precisely why it does not provide a worthwhile ChoCo problem. The paper’s rule already depends only on the reported profile. Replacing the voter sum by a weighted sum over report types gives the same construction and the same proof. For rational masses, multiplying by a common denominator literally recovers an ordinary profile with duplicated voters. Every quantity in the proof—stable-lottery inequalities, welfare, and the \(n/t\) term—is just replaced by its normalized weighted version.
This is not an objection that “continuity does not help.” The deeper problem is that Theorem 4 never posed a population-sensitive computational problem in the first place. It proved that a particular report-to-lottery map has a certain worst-case ratio. Computing that map on weighted report counts is merely an implementation of the already-proved rule. Even granting the cited polynomial-time stable-lottery routine, the continuous version contributes no new pricing problem, relaxation, complexity parameter, or algorithmic boundary.
The proponent’s alternative—computing the optimal report-only distribution—does not repair the anchoring problem. It asks for a new robust mechanism-design problem:
\[ \min_{D} \max_{\mu:\,P\mu=\rho} \frac{\max_{Y\in\binom{C}{k}} W_\mu(Y)} {\mathbb{E}_{X\sim D}[W_\mu(X)]}. \]
Theorem 4 only supplies one feasible \(D\) with a guarantee; it does not claim that this \(D\) is optimal or study the displayed optimization problem. That problem may be interesting, but it is a new problem inspired by the paper, not a continuous mirror of one of its computational results.
There is also a mismatch in what constitutes the “type.” The paper’s uncertainty is over arbitrary cardinal utilities consistent with a reported top-\(t\) ranking. If utilities are included in complete types, then the algorithm cannot use the actual society distribution \(\mu\), because those utilities are hidden. If a finite catalogue \(\Theta\) of possible utility vectors is supplied, the model has been restricted to a new finite uncertainty set. If one preserves the paper’s original uncertainty set, the catalogue is generally an infinite family of utility vectors, not a finite high-multiplicity type space. Thus the proposed continuous society is either hidden and computationally irrelevant to the rule, or revealed and no longer represents the paper’s information model.
The same objection defeats the supposed backup anchors. Proposition 1 is simply a rule with a distortion guarantee; Theorem 2 is a lower bound against every randomized rule. Their weighted versions follow by the same duplication argument, but neither becomes a computational problem. Theorem 2 cannot supply a ChoCo complexity result merely because its adversarial utility profile is written as a mass distribution.
There are certainly plausible repeated-preference populations in this voting setting, so I would not argue that high multiplicity is nonsensical here. The honest conclusion is narrower and stronger: the population continuation is valid but vacuous as a ChoCo contribution. It reformulates an already population-scale-invariant distortion analysis, while the only potentially new optimization problem is not a result of the paper. The paper therefore offers no worthwhile continuous computational mirror for the programme’s stated purpose.
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.