| paper | Comparing Ways of Obtaining Candidate Orderings from Approval Ballots |
| authors | Théo Delemazure, Chris Dong, Dominik Peters, Magdalena Tydrichova |
| venue | IJCAI 2024 |
| filed under | voting · structured |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 1
statement extracted from the paper’s text layer
Given candidates \(C\), rational masses \(\mu_A\) over nonempty approval types \(A\subseteq C\) with \(\sum_A\mu_A=1\), and a rational threshold \(q\), does there exist an axis \(\preceq\) such that \(\sum_A\mu_A\mathbf{1}[A\text{ is not an interval of }\preceq]\le q\)?
A high-multiplicity approval-ballot society with types \(A\in 2^C\setminus\{\emptyset\}\), mass distribution \(\mu\), axis \(\preceq\) as the decision variable, and objective minimizing the population mass of non-interval ballots.
The mirror covers Theorem 1's computational content for Voter Deletion, and naturally extends to the other four rules. It leaves Theorems 2 and 3, Proposition 8, the axiomatic analysis, and the empirical experiments outside the mirror.
The strongest positive case is a direct high-multiplicity version of the paper’s Voter Deletion rule. It is not a change to the candidate space or to the axis: only the population of approval ballots becomes continuous.
The computational anchor is Theorem 1, which states that “the VD, MF, BC, MS, and FT rules are NP-complete to compute, even for profiles in which every ballot approves at most 2 candidates.” The theorem is stated by this paper, although the short version omits its proofs and sends the reader to Delemazure et al. (2024). The hardness of VD and BC is attributed explicitly to Booth (1975); hardness for MF, MS, and FT follows from their coincidence with VD or BC on profiles whose ballots have size at most two.
My lead mirror is Continuous Voter-Deletion Axis, \(\mathrm{VD}_\infty\).
An instance consists of a finite candidate set \(C\), a finite support \(S\subseteq 2^C\setminus\{\emptyset\}\), rational masses \(\mu_A\ge 0\) for \(A\in S\) with \(\sum_{A\in S}\mu_A=1\), and, for the decision version, a rational threshold \(q\). The mass \(\mu_A\) is the fraction of the population with approval ballot \(A\). A solution is an axis \(\preceq\), identified with its reversal, minimizing
\[ \operatorname{loss}_{\mathrm{VD}}(\mu,\preceq) = \sum_{A\in S}\mu_A\, \mathbf{1}[A\text{ is not an interval of }\preceq]. \]
Equivalently, after choosing \(\preceq\), one deletes the mass of all voters whose ballots are not intervals. The decision question is whether some axis has loss at most \(q\); the optimization question asks for an optimal axis and its loss.
This is exactly the population version of the authors’ rule. Given a discrete profile \(P\) with \(n_A\) ballots of type \(A\), set \(\mu_A=n_A/n\). Then, for every axis,
\[ \operatorname{loss}_{\mathrm{VD}}(\mu,\preceq) = \frac{\operatorname{cost}_{\mathrm{VD}}(P,\preceq)}{n}. \]
Thus the optimal axes are identical. The objective is simply “the fraction of voters that must be treated as mavericks” rather than “the number of voters deleted.” It does not introduce an unrelated probabilistic noise model: \(\mu\) is the population composition, and the objective is the normalized total loss.
A plausible regime is a large approval survey over a fixed candidate slate. Millions of respondents may repeatedly exhibit the same approval patterns, while the number of candidates is moderate. The paper’s French-election data already points in this direction: \(20{,}076\) voters were observed over \(11\) candidates, for at most \(2^{11}-1=2047\) nonempty approval types. The same model applies to large collections of bills, user evaluations, or policy questions, where each recurring approval set is a type. Two agents are the same type precisely when the paper’s rule treats them identically: they approve the same candidates. Their mass is their population share.
This mirror is particularly credible because the paper itself defines every rule through a voter-additive cost function and motivates scoring rules as maximum-likelihood or aggregate-loss objectives. Replacing a finite sum over voters by an expectation over ballot types is therefore the ordinary high-multiplicity formulation of their problem, not a tractable surrogate invented after the fact.
I expect \(\mathrm{VD}_\infty\) to lie in Class B: hardness transfers. For the hardness instances in Theorem 1, every ballot has size at most two. Hence the relevant type universe has size at most
\[ m+\binom{m}{2}, \]
and the masses can be uniform rational values. Repeating every voter type \(K\) times makes the population arbitrarily larger without changing \(\mu\) or the optimal axis. The hardness therefore survives when the population is highly repetitive. The combinatorics lives in ordering the candidates, not in individuating voters. This is exactly the programme’s expected Class B phenomenon.
The same construction gives natural siblings \(\mathrm{MF}_\infty\), \(\mathrm{BC}_\infty\), \(\mathrm{MS}_\infty\), and \(\mathrm{FT}_\infty\), obtained by minimizing
\[ \sum_A \mu_A\operatorname{cost}_R(A,\preceq) \]
for the corresponding rule \(R\). But I would not dilute the case by presenting all five as separate claims: \(\mathrm{VD}_\infty\) is the cleanest anchor. The mirror covers the computational content of Theorem 1, not the axiomatic results such as Theorems 2 and 3 or the experiments.
It generates useful follow-up questions: whether weighted almost-C1P axis selection admits approximation guarantees; whether it is fixed-parameter tractable under restrictions on \(m\), the support graph, or the number of exceptional types; how robust the optimal axis is to perturbations of \(\mu\); and how many samples are needed to recover an approximately optimal population axis from data.
The weakest point is also clear: for unrestricted exact optimization, continuization gives no computational improvement here. The continuous problem is essentially the weighted, normalized form of the discrete one, and Theorem 1’s hardness remains. If “continuous mirror” is expected to mean a tractable relaxation, this example is disappointing. But under ChoCo’s stated trichotomy that is a legitimate and informative outcome: it is a convincing population mirror whose hardness transfers, showing that this problem stops benefiting precisely because its difficulty lies in the candidate ordering rather than in population multiplicity.
The strongest negative argument is that \(\mathrm{VD}_\infty\) is merely weighted almost-C1P axis selection: for every profile \(P\), setting \(\mu_A=n_A/n\) preserves the objective exactly, since \(\operatorname{loss}_{\mathrm{VD}}(\mu,\preceq)=\operatorname{cost}_{\mathrm{VD}}(P,\preceq)/n\). Thus the continuous formulation does not expose a new population-level phenomenon or make the axis problem easier.
That observation, however, is not a valid defeat under the programme’s criteria. A continuous mirror need not be tractable; Class B is explicitly an intended outcome. Nor is “the combinatorics lies in the candidates” an objection. The question is whether the high-multiplicity version is sensible, and here it plainly is.
The proposed type is complete for the paper’s problem: two voters with the same approval set are indistinguishable to every objective considered. Voter Deletion is anonymous and voter-additive, and its objective is literally the fraction of the population whose ballots are maverick. No identity, arrival time, private price, or other information is discarded. A large approval survey, recurring user-review patterns, or repeated evaluations of a fixed candidate slate all provide plausible high-multiplicity regimes. If one instead introduces latent voter attributes, their push-forward distribution over approval sets gives exactly the same \(\mu\); retaining those attributes would change the problem rather than improve its mirror.
The hardness transfer is also stronger than the proponent needs. Theorem 1 already gives hardness when every ballot approves at most two candidates. Consequently, the relevant support contains at most \(m+\binom{m}{2}\) approval types. Any such discrete instance can be represented by rational masses, and duplicating every voter arbitrarily many times creates a population with arbitrarily large multiplicity without changing the normalized objective or the optimal axes. This is a genuine compressed high-multiplicity instance, not an objectionable individual-by-individual encoding.
Nor can one appeal to degeneration: the loss is a population fraction, so the disappearance of any one voter is precisely appropriate, while aggregate maverick mass remains nonzero. Existing consecutive-ones and high-multiplicity work would support the model rather than collide with it; the paper does not cite a continuous computational treatment of this population problem.
So the negative case is honestly weak. One may argue that this mirror is less exciting because continuization does not yield a tractable relaxation, but the programme explicitly forbids treating that as a reason to reject a well-posed Class B problem. The proponent’s \(\mathrm{VD}_\infty\) anchor survives, and therefore the universal claim that no worthwhile continuous mirror exists cannot be sustained.
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.