| paper | Voting with Preference Intensities |
| authors | — |
| venue | AAAI 2023 |
| 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 contains no named theorem asserting algorithmic complexity, hardness, or an algorithmic approximation guarantee for a computational problem. Its weighted-population formulations are faithful and authors would recognise them, but they only restate distortion arguments and do not satisfy bit (a).
fails bit a — no named computational result to mirror
The proposed mirror covers the top- and uniform-decisiveness results (Theorems 1–7), voluntary POII (Theorems 8–9), and mandatory reporting (Theorems 10–12) as weighted distortion formulations, but none yields a ChoCo computational-complexity result.
The strongest honest positive case is conditional: this paper has a very natural population mirror, but it does not contain an eligible ChoCo anchor under the programme’s strict definition. Theorem 1 through Theorem 12 are distortion bounds, not named complexity results: none states membership in P, NP-hardness, W[1]-hardness, FPT, or an exact/approximation algorithm with a complexity guarantee. Thus the paper cannot support a full Class A/B/C verdict as written.
The best near-miss anchor is Theorem 4, proved in this paper. It gives a constructive randomized voting rule \(f_{\mathrm{dec}}\) with distortion
\[ O\!\left(\frac{\alpha m+1}{\alpha\sqrt m+1}\right), \]
and the proof obtains the explicit bound \(4(\alpha m+1)/(\alpha\sqrt m+1)\). This has a clean continuous-population form.
Define a voter type as a complete ranking \(\pi\) of the \(m\) alternatives, with the first adjacent comparison marked decisive and all later comparisons ordinary. A society is a rational distribution \(\mu\) over these ranking types. Thus \(\mu_\pi\) is the fraction of the population reporting ranking \(\pi\); it is not a lottery over outcomes. The many agents could be millions of residents choosing among a fixed set of public projects, with recurring demographic or need-based cohorts sharing the same ranking and the same decisive top gap. The number of agents is enormous, while the number of supported types may be dozens or hundreds.
For a type \(\pi\), let \(U_\alpha(\pi)\) be the unit-sum utility vectors satisfying
\[ u_{\pi_1}\geq u_{\pi_2}\geq\cdots\geq u_{\pi_m}, \qquad u_{\pi_2}\leq \alpha u_{\pi_1}. \]
If \(v_{\pi,a}\) is the aggregate utility mass of type \(\pi\) for alternative \(a\), require \(v_\pi/\mu_\pi\in U_\alpha(\pi)\). For a lottery \(x\in\Delta(A)\), define
\[ D_\alpha(x;\mu) = \sup_v \frac{\max_a \sum_{\pi}v_{\pi,a}} {\sum_{\pi,a}x_a v_{\pi,a}}. \]
The continuous problem is:
Given \(m\), \(\alpha\), and \(\mu\), output a lottery \(x\) satisfying
\[ > D_\alpha(x;\mu) > \leq > \frac{4(\alpha m+1)}{\alpha\sqrt m+1}. > \]
The paper’s \(f_{\mathrm{dec}}\) is the natural witness: apply its stable-lottery component to the mass-weighted profile, mix it with the uniform lottery over alternatives having positive top mass, and mix in the plurality winner determined by maximum top mass. Every counting argument in Theorem 4 becomes the corresponding statement about masses. The authors should recognise this as their model with a high-multiplicity profile, not as a weakened utility or outcome model.
This problem looks like Class A, conditional on an efficient implementation of the stable-lottery component over a weighted histogram. For a supplied intensity profile, the distortion-optimal lottery is also naturally expressible through the linear programme already mentioned in the paper’s footnote. The paper itself does not establish the required input-size or oracle complexity, so this is a proposed ChoCo problem rather than a result already proved there.
A second, even more population-sensitive near-miss is Theorem 8, also proved here. It studies the price of ignoring intensities (POII), with lower bound
\[ \Omega\!\left( \frac{(1-\alpha)\sqrt m}{1-\alpha^m}+1 \right). \]
Its continuous version is:
Input \(m\), \(\alpha\), and a rational distribution \(\rho\) over ordinary rankings. The designer sees only \(\rho\). An intensity completion is any distribution \(\mu\) over ranking-plus-intensity types whose projection onto rankings is \(\rho\). For each completion, define \(D_\alpha(x;\mu)\) as above and \(D_\alpha^*(\mu)=\min_y D_\alpha(y;\mu)\). Output an intensity-oblivious lottery \(x\), or decide whether
\[ > \sup_{\mu:\operatorname{proj}(\mu)=\rho} > \frac{D_\alpha(x;\mu)}{D_\alpha^*(\mu)} > \leq K. > \]
Theorem 8’s construction transfers especially cleanly: the \(\sqrt m\) groups simply receive mass \(1/\sqrt m\), so no divisibility assumption on \(n\) is needed. The lower bound is therefore not an artefact of finite population size. The fixed-completion version should be LP-tractable; the robust version over all intensity completions is a plausible continuum-specific optimization problem, with the main difficulty being separation over intensity patterns rather than individual voters.
The further questions are whether the weighted stable lottery can be implemented in polynomial time, whether the robust POII problem has a compact separation oracle, and whether the mandatory-reporting bound in Theorem 12 or the uniform-decisiveness bounds in Theorems 5–7 yield sharper continuous optimization problems.
The weakest point is decisive: these are faithful high-multiplicity reformulations, but they do not yet expose a named computational result from the paper. The paper studies the quality of voting rules, not the complexity of computing them. The fact that its proofs survive replacing counts by masses is strong evidence that the population mirror is sensible; it is not, by itself, a ChoCo complexity theorem. So my positive conclusion is: excellent continuous-population object, probably an LP/robust-optimization Class A direction, but no admissible ChoCo anchor unless the programme accepts constructive distortion theorems as computational results.
The proponent’s own concession is fatal under ChoCo’s stated eligibility rule: this paper contains no named computational result. Theorem 1 through Theorem 12 are bounds on the distortion of voting rules. They do not assert membership in P, hardness, approximation complexity, parameterized tractability, or an algorithm for an explicitly posed computational problem. The paper’s computational content is only implicit in evaluating a voting rule, and no complexity claim is made about that evaluation.
Theorem 4 is nevertheless the strongest possible near-miss, so it deserves a charitable reconstruction. A society can certainly be represented by a distribution over rankings with a decisive top gap. The proof’s counting arguments become mass arguments, and rational masses can be expanded into a finite electorate without changing the distortion ratio. Thus the proposed continuous statement is mathematically legitimate.
But that legitimacy does not produce a worthwhile continuization of the theorem. The theorem says that a particular rule works on every profile. On a weighted profile, its plurality and top-support components are immediate weighted counts; the remaining stable-lottery component is simply the same rule evaluated on a weighted histogram. If it is efficiently computable, this is inherited implementation machinery, not a computational consequence of Theorem 4. If it is not efficiently computable, the resulting question is the complexity of the stable-lottery rule from the earlier literature, not a complexity result exposed by this paper.
One can improve the proposal by asking for the distortion-optimal lottery for a supplied distribution. That is a legitimate problem, but it is no longer Theorem 4: it replaces a fixed constructive witness by a new optimization problem. More importantly, the paper already says that the fixed-profile optimum is obtained by a small modification of an LP. Since the utility-feasible sets are convex, all agents with the same reported ranking and intensity can be aggregated into one weighted representative. The continuous version therefore gives ordinary row compression of an LP, not the exponential-type pricing or mass-transfer structure that makes a ChoCo mirror valuable.
Theorem 8 has the best population interpretation, but it fails for the same deeper reason. Its \(\sqrt m\) groups can be assigned mass \(1/\sqrt m\), so the lower-bound construction survives perfectly in a continuum. That proves the high-multiplicity regime is sensible; it does not create a computational problem. The theorem is a worst-case information-loss statement over profiles, not an algorithmic statement about processing a society.
The proposed robust version—observe only a distribution \(\rho\) over rankings, then optimize against every compatible intensity completion—is a coherent new problem. But it is a problem about hidden intensity information and robust mechanism design, not about continuizing the population. If the full intensity distribution is supplied, the problem reduces to the paper’s LP. If only \(\rho\) is supplied, the missing object is precisely the latent information state; population mass merely supplies coefficients. All of the real combinatorics lie in the possible intensity patterns and cardinal-utility constraints, whose size is governed by \(m\), not by the number of agents.
There is also a type-space problem that the proposed mirror suppresses. In the paper, two agents with the same reported ranking and intensity need not have the same cardinal utility vector; distortion deliberately quantifies over those unreported utilities. So ranking-plus-intensity is not literally a complete type in ChoCo’s sense. One can repair this by defining a type as a report together with its utility uncertainty set. Because those sets are convex, aggregate utility mass can again be represented by one vector per report type. That repair is mathematically sound, but it confirms the diagnosis: the continuous society is only a weighted reformulation of the finite profile, while the substantive problem is uncertainty over utilities.
Theorem 12 and Theorems 5–7 do not provide a third escape. Their mandatory-reporting and uniform-decisiveness variants likewise transfer by replacing group cardinalities with masses. They remain asymptotic distortion bounds, with no population-dependent computational task attached. A robust optimization problem could be invented around them, but it would be a new problem about reporting or information elicitation rather than a computational mirror of a result in this paper.
The negative case should not claim that no sensible weighted model exists. Millions of voters divided into recurring preference cohorts are entirely plausible here, and the proponent is right that the literal continuum is not the obstruction. The stronger and more defensible conclusion is narrower: every proposed anchor is either an automatic weighted restatement of a distortion theorem, an LP already implicit in the paper, or a newly invented robust-information problem. None is a named computational result whose population continuization opens a ChoCo complexity landscape. Under the programme’s strict standard, this paper has no worthwhile continuous 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.