| paper | Discovering Consistent Subelections |
| authors | — |
| venue | AAMAS 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 3
statement extracted from the paper’s text layer
Given a finite candidate set \(C\), ranking types \(T=\mathcal{L}(C)\), a rational distribution \(\mu\) over \(T\), an integer \(q\), and rational \(\alpha\), decide whether there exist \(C'\subseteq C\) with \(|C'|\ge q\) and an order \(\pi\) on \(C'\) such that \(\sum_{t\in T:\,t|_{C'}=\pi}\mu_t\ge\alpha\); equivalently, maximize the mass of types agreeing on the selected candidate order.
A high-multiplicity ordinal society has ranking types \(t\in T\) with masses \(\mu_t\); the decision variables are \(C'\) and \(\pi\), and the objective is the total mass of types whose restriction to \(C'\) equals \(\pi\), subject to candidate threshold \(q\) and mass threshold \(\alpha\).
For fixed \(C'\), all eligible mass can be included wholesale, so the mirror may be only a weighted reformulation and may not expose new continuous-optimization structure.
fatal: False
It covers Theorems 1, 3, and 9, together with mass versions of Max-ID, Max-AN, MaxClone, and the related parameterized formulations. It leaves the closest-subelection swap-distance ILPs, empirical map visualizations, elicitation application, and approximate or structured-domain extensions.
The strongest mirror is for the paper’s hidden-identity problem. I would use three anchors, with Theorem 3 as the lead: Theorem 3 proves here that Hidden-ID is NP-complete; Theorem 9 proves here that Hidden-AN is NP-complete; and Theorem 1 proves here that Hidden-Clones is solvable in polynomial time.
The common population model is straightforward. Fix the candidate set \(C\), let \(T\) be the set of rankings of \(C\), and represent the society by a rational distribution \(\mu\) over \(T\). The input lists the positive-mass types and their weights; individual voters are absent. A finite profile with \(n_t\) voters of type \(t\) becomes \(\mu_t=n_t/n\). Conversely, any rational \(\mu\) can be realized by a high-multiplicity finite profile.
The natural regime is a large consumer or opinion population ranking a fixed slate of products or political issues. There may be millions of people but only a moderate number of recurring preference types: demographic, cultural, ideological, or market segments. The number of agents is therefore much larger than the number of distinct rankings. Mass means percentage of the population, and the decision is which candidate subset and which population mass to report as a coherent hidden segment. Candidates remain discrete; only the population is continuous.
My lead problem is \(\textsc{Mass-Hidden-ID}_{\infty}\), mirroring Theorem 3. An instance consists of \(C\), \(\mu\), an integer \(q\), and a rational threshold \(\alpha\). For \(C'\subseteq C\) and an order \(\pi\) on \(C'\), define \(I_\mu(C',\pi)=\sum_{t:\,t|_{C'}=\pi}\mu_t\). The question is whether there exist \(C'\) with \(|C'|\ge q\) and an order \(\pi\) such that \(I_\mu(C',\pi)\ge\alpha\). A solution is \(C'\), \(\pi\), and selected masses \(y_t\) satisfying \(0\le y_t\le\mu_t\), \(y_t=0\) unless \(t|_{C'}=\pi\), and \(\sum_t y_t\ge\alpha\). The optimization version maximizes \(\sum_t y_t\).
This is almost exactly the paper’s question with “at least \(n'\) voters” replaced by “at least an \(\alpha\)-fraction of society.” If \(E\) has \(n\) voters, set \(\mu_t\) to the fraction of voters with ranking \(t\) and \(\alpha=n'/n\). Then the finite and continuous decision problems are equivalent. The problem is not weakened by allowing fractional mass: all voters of an eligible type are interchangeable, and the optimum is simply the total mass of eligible types.
I expect \(\textsc{Mass-Hidden-ID}_{\infty}\) to be Class B: hardness transfers. Theorem 3’s reduction encodes satisfiability in the choice of literal candidates and the common order, not in any genuinely individual-specific attribute of voters. Repeating every type an arbitrarily large number of times makes the population high-multiplicity without changing the instance. Under an explicit-support representation, the weighted decision problem is also plainly in NP, so NP-completeness is a reasonable expectation. The natural follow-up questions concern the parameterized complexity in \(q\), the number of supported types, or the number of candidates, as well as approximate identity where a small mass of voters may disagree.
The second mirror is \(\textsc{Mass-Hidden-AN}_{\infty}\), corresponding to Theorem 9. Here \(q\ge2\), and a solution consists of \(C'\), an order \(\pi\) on \(C'\), and two selected masses: one whose restriction to \(C'\) is \(\pi\), and one whose restriction is the reverse order \(\pi^{-1}\). The two masses must be equal. Equivalently, define \(B_\mu(C',\pi)=\sum_{t:\,t|_{C'}=\pi}\mu_t\). The maximum antagonistic mass for \(C'\) and \(\pi\) is \(2\min\{B_\mu(C',\pi),B_\mu(C',\pi^{-1})\}\). The decision question asks whether this quantity is at least \(\alpha\) for some \(|C'|\ge q\).
This is a particularly convincing continuization because the defining condition already asks for two equal-sized camps. Equal cardinality becomes equal mass without any conceptual change. Setting \(\alpha=n'/n\) gives an exact embedding of the finite problem, and Theorem 9’s candidate-side reversal construction survives it. I therefore expect this problem also to be Class B, with hardness coming from the agenda and the reversal structure rather than from population multiplicity. Further questions include unequal-mass polarization, maximizing the product rather than the smaller camp, and allowing approximately reversed rankings.
The third, cleaner algorithmic mirror is \(\textsc{Mass-Hidden-Clones}_{\infty}\), based on Theorem 1. Given \(C\), \(\mu\), \(q\), and \(\alpha\), choose exactly \(q\) candidates and maximize the mass of types for which those candidates form a clone set. For a ranking type \(t\), this means that the positions occupied by \(C'\) form one contiguous interval. Define \(G_\mu(C')=\sum_{t:\,C'\text{ is contiguous in }t}\mu_t\). The question is whether some \(|C'|=q\) has \(G_\mu(C')\ge\alpha\), with the selected mass again recorded by variables \(y_t\le\mu_t\).
I expect this problem to be Class A. The proof of Theorem 1 lifts directly: for every supported ranking type, enumerate its \(q\)-candidate intervals, aggregate the weight of each candidate set, and accept if some set reaches mass \(\alpha\). This takes time polynomial in the number of supported types, the number of candidates, and the encoding length of the weights. Thus the continuous version preserves the paper’s polynomial result while giving it the more natural population interpretation of “what percentage of society treats these alternatives as clones?”
The mirror covers the paper’s exact discovery problems: hidden identity, hidden antagonism, and hidden clones. It does not claim to continuize the map-of-elections experiments, the elicitation procedure, approximate subelections, or the proposed single-peaked and single-crossing extensions. Those could generate further mirrors, but they are not needed for this case.
The weakest point is that the identity and antagonism mirrors may look like weighted restatements rather than problems requiring new continuous-optimization machinery. Exact common rankings can also be brittle when the candidate set is very large. That criticism is real. Still, the paper itself describes its discoveries as significant population groups and reports results as percentages, so \(\alpha\)-mass is recognizably the same question. More importantly, a valid continuous mirror need not become easy: Theorem 3 and Theorem 9 would naturally become Class B examples, while Theorem 1 supplies a genuine Class A lift. That combination is a credible computational-continuization programme rather than a claim that continuity dissolves every difficulty.
The strongest negative case is that these are not really continuous computational problems at all: every property in the paper depends only on a voter’s ranking, so any latent continuum of consumers or citizens collapses under the ranking map to the finite distribution \(\mu\). The proposed variables \(y_t\) add nothing: for a chosen candidate set, one simply takes all eligible mass. Thus identity, antagonism, and clones become weighted pattern-counting problems, with no continuous decision variable, geometry, or mass-transfer structure.
That criticism is real, but it does not defeat the anchors under ChoCo’s stated standards.
For Theorem 3, the consumer or political-population scenario is entirely credible. A large population with recurring preference types is precisely a high-multiplicity regime. The quantity
\[
I_\mu(C',\pi)=\sum_{t:t|_{C'}=\pi}\mu_t
\]
is a meaningful percentage of society sharing a coherent view on a selected agenda. The fact that the hardness is driven by candidate selection, or that the rational version compresses repeated voters, is not an objection here: Class B hardness transfers are explicitly part of the programme. Approximate identity would be a further, defensible question rather than a reason the exact one is meaningless.
The same applies to Theorem 9. Equal cardinality naturally becomes equal mass, and antagonistic camps are a plausible description of polarized consumer or ideological populations. Divisibility does make the optimum
\[
2\min\{B_\mu(C',\pi),B_\mu(C',\pi^{-1})\},
\]
but that is a legitimate continuous formulation, not a collapse of the concept. Forbidding partial type-mass selection would preserve whole groups but merely return to a weighted high-multiplicity variant.
Theorem 1 is the hardest anchor to attack. For \(C'\), the continuous objective
\[
G_\mu(C')=\sum_{t:C'\text{ is contiguous in }t}\mu_t
\]
is exactly the population percentage treating those candidates as a clone block. The paper’s interval enumeration lifts directly, including for nontrivial \(2\le q<m\). It is algorithmically elementary, but the programme does not require every Class A result to use sophisticated continuous optimization.
So the honest negative verdict is weak. One can argue that these mirrors are likely to produce only immediate weighted versions of the paper’s algorithms and hardness results, rather than the kind of new continuous optimization landscape ChoCo seeks. But that is a novelty-and-payoff objection, not a fundamental failure of continuization. The proponent has supplied three sensible high-multiplicity population problems, including both Class A and Class B examples. I cannot honestly defend the universal claim that no worthwhile continuous mirror exists.
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.