| paper | The Complexity of Subelection Isomorphism Problems |
| authors | Piotr Faliszewski, Krzysztof Sornat, Stanisław Szufa |
| venue | AAAI 2022 |
| filed under | voting · theory |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c22r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 3
statement extracted from the paper’s text layer
Given finite candidate sets \(A,B\) with \(|A|\le |B|\), rational distributions \(\mu\) and \(\nu\) over complete rankings of \(A\) and \(B\), and rational \(\lambda\in(0,1]\), does there exist \(S\subseteq B\) with \(|S|=|A|\), a bijection \(\sigma:A\to S\), and masses \(0\le x_\rho\le\nu_\rho\) such that \(\sum_\rho x_\rho=\lambda\) and, for every ranking \(\pi\) of \(A\), \(\sum_{\rho:\,\sigma^{-1}(\rho|_S)=\pi}x_\rho=\lambda\mu_\pi\)?
Two high-multiplicity electorates are distributions over complete ranking types: \(\mu\) and \(\nu\) supply mass, while \(S\), \(\sigma\), and \(x_\rho\) choose the candidate restriction, relabelling, and retained voter mass; the decision objective is to meet the target distribution, or optionally maximize \(\lambda\).
The fractional reduction and its claimed \(W[1]\) parameterization remain unproved under the proposed rational encoding, so the exact complexity transfer is still a technical conjecture.
fatal: False
The mirror covers Theorem 3, but leaves Theorem 2, Theorems 5 and 7, Propositions 6 and 10–11, approximation and ETH refinements, and the statistical-culture experiments untreated.
The strongest case is for Theorem 3, the paper’s main hardness result:
“SUBELECTION ISOMORPHISM is NP-complete and W[1]-hard with respect to the size of the smaller election.”
This theorem is proved in the paper by reduction from CLIQUE; it is not merely cited. I would make it the lead anchor.
A faithful population mirror is Mass-Subelection Isomorphism\(_\infty\). An instance consists of two finite candidate sets \(A\) and \(B\), with \(|A|\le |B|\); a rational distribution \(\mu\) over complete rankings of \(A\); a rational distribution \(\nu\) over complete rankings of \(B\); and a rational retention level \(\lambda\in(0,1]\). The distributions describe two large electorates. A voter type is a complete ranking, and its mass is the fraction of the relevant electorate having that ranking.
The question is whether one can choose a candidate subset \(S\subseteq B\) with \(|S|=|A|\), a bijection \(\sigma:A\to S\), and retained masses \(x_\rho\in[0,\nu_\rho]\) for rankings \(\rho\) of \(B\), such that the retained mass is exactly \(\lambda\) and, for every ranking \(\pi\) of \(A\), the mass whose restriction to \(S\), relabelled by \(\sigma^{-1}\), becomes \(\pi\) is exactly \(\lambda\mu_\pi\). Formally, the requirement is
\[ \sum_{\rho:\,\sigma^{-1}(\rho|_S)=\pi} x_\rho=\lambda\mu_\pi \]
for every \(\pi\). Equivalently, after deleting candidates outside \(S\) and retaining a mass \(\lambda\) of the larger society, the resulting normalized society must be isomorphic to \(\mu\). One may also formulate the optimization version, which maximizes \(\lambda\).
This is directly the paper’s operation: delete candidates and voters from the larger election, restrict the remaining rankings, and ask for isomorphism. The only change is that voter deletion becomes divisible mass deletion. The parameter \(\lambda\) preserves the cardinality information that normalization would otherwise lose: if the original elections have \(n_1\) and \(n_2\) voters, set \(\lambda=n_1/n_2\). A finite instance embeds by taking \(\mu_\pi=n_{1,\pi}/n_1\), \(\nu_\rho=n_{2,\rho}/n_2\), and restricting \(x_\rho\) to multiples of \(1/n_2\). Dropping that grid is exactly the high-multiplicity relaxation.
The regime is plausible in two large electorates made up of recurring voting cohorts: for example, residents of many repeated local constituencies, members of institutional or demographic blocs, or repeated polling panels facing the same candidate slate. Within a cohort, agents have the same complete ranking and are indistinguishable for the problem. The number of people can be enormous while the number of distinct ranking types remains moderate; multiplying every cohort by \(M\) increases population size without changing the type description. This is a genuine high-multiplicity scenario, not an assumption that every named voter has disappeared.
I expect Mass-Subelection Isomorphism\(_\infty\) to be Class B: hardness should transfer. The combinatorics in Theorem 3 lives primarily in the candidate set, not in the individuality of voters. In the paper’s CLIQUE reduction, \(E_K\) represents the smaller election and \(E_G\) the larger one. Set \(\mu\) and \(\nu\) to the corresponding normalized vote-type distributions and set \(\lambda=|V(E_K)|/|V(E_G)|\). If \(G\) contains a \(k\)-clique, the associated candidate subset and edge-voter mass give a feasible continuous solution.
Conversely, the special candidates \(\alpha_G,\beta_G\) and the four vote patterns attached to each edge force any feasible solution to retain their analogues. Each positive-mass target pattern corresponding to a pair of clique vertices can only be supplied, after restriction, by a source edge joining the corresponding candidate pair. Thus every pair in the selected \(k\)-candidate set must be an edge of \(G\). Fractional voter mass does not manufacture a missing edge pattern; it can split existing supply but cannot create support that is absent. This is the key reason the reduction appears to survive continuization.
The expected parameterized consequence is W[1]-hardness in the size of the target description, such as \(|A|+|\operatorname{supp}(\mu)|\), since the constructed target has \(k+2\) candidates and \(4\binom{k}{2}\) vote types. For fixed candidate subset and bijection, feasibility is only a rational flow or linear feasibility problem. The difficult part is choosing the candidate subset and relabelling, exactly where the CLIQUE structure remains. Under explicit rational supports, the decision problem should plausibly be NP-complete as well.
The mirror deliberately covers only Theorem 3. It does not claim to continuize the whole paper, nor does it rely on the polynomial voter-subelection cases in Theorem 2 or the experimental statistical-culture section. Those can generate separate questions, but they are unnecessary for the positive case.
The weakest point is that the paper’s proof is written for integral voter collections, whereas the proposed problem permits fractional mass from a type to be split among several target types after candidate restriction. The support-preservation argument above must therefore be proved formally; it cannot simply be assumed from the discrete reduction. There is also a weaker representational risk: in arbitrary elections, distinct rankings may be nearly as numerous as voters, so the population compression may be modest. Both objections are confined to the strength of the continuization, however. In the repeated-cohort regime, mass is the honest primitive, and the candidate-side obstruction identified by Theorem 3 remains a natural computational problem even when voter multiplicity becomes continuous.
The immediate follow-up questions are whether the fractional version is indeed NP-complete and W[1]-hard, whether fixed candidate matchings change its complexity, whether approximate isomorphism becomes an LP once the candidate map is fixed, and how solutions round back to finite elections with bounded loss.
The strongest objection is that continuization removes the voter-side combinatorics that make Theorem 3 interesting. For fixed candidate subset \(S\) and bijection \(\sigma\), every source ranking \(\rho\) restricts to exactly one target ranking. Thus feasibility reduces to coordinatewise supply constraints
\[ \sum_{\rho:\,\sigma^{-1}(\rho|_S)=\pi}\nu_\rho \ge \lambda\mu_\pi \]
for every target type \(\pi\). Fractional voter deletion contributes no combinatorial structure: it merely selects enough mass from each fibre. The proposed problem is therefore mainly a weighted search over candidate subsets and relabellings, rather than a continuous population problem in any substantive sense.
The cohort story is also weaker for the paper’s actual hard instances than it first appears. The CLIQUE construction gives essentially one distinct ranking type per edge gadget, so the number of types grows with the number of voters. Scaling each gadget by a large multiplicity produces a valid high-multiplicity instance, but it does not exploit a compact recurring population structure. A more natural maximum-retained-mass or approximate-distribution variant would be a useful profile-alignment problem, but it would be a new weighted similarity problem rather than a meaningful continuous counterpart of the paper’s finite subelection operation.
That is the best negative case, but it does not survive the programme’s standards. Voter identity is explicitly irrelevant in subelection isomorphism: voters are reordered, and only their multiset of rankings matters. Repeated ballot cohorts are entirely plausible, so there is no valid “no multiplicity” objection. Nor is candidate-side hardness a reason to reject the mirror; the programme explicitly treats hardness transfer as a worthwhile Class B outcome.
Indeed, the proposed reduction appears to survive fractional deletion. With \(q=4\binom{k}{2}\) target voters and \(Q=4|E(G)|\) source voters, setting \(\lambda=q/Q\) makes every target gadget demand mass \(1/Q\). A source ranking restricts to one target ranking, and if a selected pair of ordinary candidates is a non-edge, the four corresponding target patterns have no source support. Fractional mass can split existing supply, but cannot manufacture those absent patterns. The special candidates likewise remain detectable through the support of the ranking distribution.
The claims of NP-completeness and W[1]-hardness for a particular encoding still require proof, especially if the parameter is defined using support size rather than the paper’s election size. That is a technical vulnerability, not a fundamental obstruction. I therefore cannot honestly defeat this anchor: Theorem 3 has a natural high-multiplicity mirror, and the universal claim that no worthwhile continuous mirror exists is not supportable.
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.