| paper | How to Sample Approval Elections? |
| authors | Stanisław Szufa, Piotr Faliszewski, Łukasz Janeczko, Martin Lackner, Arkadii Slinko, Krzysztof Sornat, Nimrod Talmon |
| venue | IJCAI 2022 |
| filed under | voting · theory |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c22r1) |
| judge confidence | high |
| authors would recognise it | yes |
Proposition 2
statement extracted from the paper’s text layer
Given candidate sets \(C,D\) with \(|C|=|D|=m\), rational distributions \(\mu\) over approval types \(2^C\) and \(\nu\) over approval types \(2^D\), and a rational threshold \(\delta\), decide whether there exist a bijection \(\sigma:C\to D\) and nonnegative transport masses \(\pi_{A,B}\) satisfying \(\sum_B\pi_{A,B}=\mu_A\), \(\sum_A\pi_{A,B}=\nu_B\), and \(\sum_{A,B}|\sigma(A)\triangle B|\pi_{A,B}\le\delta\).
Two societies are distributions \(\mu\) and \(\nu\) over approval-set types. The decision variables are a candidate bijection \(\sigma:C\to D\) and transport masses \(\pi_{A,B}\); the objective is \(\min_{\sigma,\pi}\sum_{A,B}|\sigma(A)\triangle B|\pi_{A,B}\), the normalized anonymous alignment cost.
The result is auxiliary to the paper's main statistical-culture and visualization contribution, and the mirror may be lower priority if ChoCo is restricted to intervention or winner-outcome problems.
fatal: False
The mirror covers Proposition 2 and the isomorphic Hamming metric. It leaves Proposition 1, the statistical cultures, approvalwise-distance analysis, maps, cohesiveness experiments, and PAV-runtime experiments untouched.
The strongest mirror is the paper’s isomorphic Hamming distance, anchored on Proposition 2, which is proved in this paper:
“Computing the isomorphic Hamming distance between two approval elections is NP-hard.”
I would use this as the lead, and would not pad the case with Proposition 1: its polynomial-time sampling result concerns generating individual ballots, not a computational problem on a continuous population.
Call the continuous problem Continuous Isomorphic-Hamming Distance. An instance consists of two candidate sets \(C\) and \(D\), with \(|C|=|D|=m\), and two approval societies \(\mu\) and \(\nu\). A voter type is an approval set, so the type spaces are \(2^C\) and \(2^D\). The mass \(\mu_A\) is the fraction of the first society approving exactly \(A\subseteq C\), and \(\nu_B\) is defined analogously. The masses are rational and supplied by their nonzero supports; the total mass of each society is \(1\). Given a rational threshold \(\delta\), ask whether there exist a candidate bijection \(\sigma:C\to D\) and nonnegative matching masses \(\pi_{A,B}\) such that \(\sum_B\pi_{A,B}=\mu_A\), \(\sum_A\pi_{A,B}=\nu_B\), and \(\sum_{A,B}|\,\sigma(A)\triangle B\,|\pi_{A,B}\le\delta\). Equivalently, the optimization version minimizes that last expression.
The action is therefore an anonymous alignment plan: relabel the candidates and match mass from approval type \(A\) in one society to approval type \(B\) in the other. The objective is the normalized total number of approval disagreements. This is a population-level version of exactly the comparison the paper makes; it does not make outcomes fractional and does not replace approval voting by a different rule.
The regime is a large participatory-budgeting or public-consultation platform with a fixed menu of proposals and many repeated voter types. For example, millions of residents may be drawn from a few hundred neighbourhood, organizational, or recommendation-template cohorts, with every member of a cohort submitting the same approval ballot. Thus \(n\) may be in the millions while the number of observed approval types is \(r\ll n\), even though the ambient type space has size \(2^m\). This is not a claim that every \(p\)-IC election has high multiplicity: independent random ballots may produce many distinct types. The mirror belongs to the repeated-template or organized-cohort scenario, which is plausible for recurring consultations and participatory-budgeting platforms.
The paper’s authors should recognize this as their problem rather than a simplified substitute. Their discrete definition minimizes over a candidate bijection and a permutation of voters. Once voters with identical ballots are grouped, the permutation is precisely a transportation plan \(\pi\) between ballot types. Indeed, if \(\mu_A=n_A/n\) and \(\nu_B=n'_B/n\) arise from finite elections, the transportation problem has integral margins after scaling by \(n\), so it has an integral optimum. The continuous objective is therefore exactly the paper’s isomorphic Hamming distance divided by \(n\), not merely a loose relaxation. It extends the same question to arbitrary population proportions and removes dependence on named individuals.
I expect this problem to be Class B: hardness transfers. For a fixed candidate bijection \(\sigma\), the inner problem is a minimum-cost transportation problem and is polynomial-time solvable. Continuization therefore eliminates the combinatorics of matching millions of named voters. But the outer candidate relabeling remains. Every discrete election is represented by its empirical distribution, so an instance of Proposition 2 maps directly to a rational continuous instance with the same optimum up to normalization. Hence NP-hardness survives. The reduction’s combinatorics live in the number of candidates and their relabeling, not in population multiplicity.
That classification is still valuable for ChoCo. It identifies exactly where continuization stops helping: anonymous population matching becomes flow, while candidate alignment preserves the discrete hardness. It also generates further questions: is the problem fixed-parameter tractable or approximable in \(m\) or in the number \(r\) of ballot types; do restrictions such as bounded approval-set size or Euclidean approval structure make the candidate-alignment layer tractable; and how does this continuous metric compare with the paper’s approvalwise distance when societies are generated by its resampling, noise, Euclidean, or urn models?
The weakest point is that high multiplicity is not inherent in the paper’s statistical cultures. In particular, the paper’s \(p\)-IC model may generate a society with many distinct ballots, so the repeated-cohort interpretation is a scenario added by the mirror rather than supplied by the authors’ experiments. Moreover, Proposition 2 is a supporting computational observation, while the paper’s main contribution is statistical modelling and visualization. Still, the metric itself is central to the map-of-elections framework, and the proposed mirror is an exact population formulation of that metric. It gives the programme a precise, defensible Class B result rather than pretending that this paper supports a tractability claim it does not.
The negative case is honestly weak: Proposition 2 supplies a genuine mirror, and the proposed continuization is not merely cosmetic.
For empirical societies with ballot multiplicities \(\mu_A=n_A/n\) and \(\nu_B=n'_B/n\), fixing a candidate bijection \(\sigma\) turns the voter-permutation part of isomorphic Hamming distance into a transportation problem. Because the margins become integral after multiplying by \(n\), the transportation polytope has an integral optimum. Hence the continuous objective is exactly the paper’s distance divided by \(n\), not a surrogate:
\[ d_{\mathrm{iso}}(E,F) = n\min_{\sigma,\pi} \sum_{A,B} |\sigma(A)\triangle B|\,\pi_{A,B}. \]
This satisfies the programme’s type criterion: an approval set is a complete voter type for this problem, and voter identity is deliberately irrelevant because the paper minimizes over voter permutations. A repeated-cohort interpretation—large consultations in which many residents use identical organizational or template ballots—is also perfectly plausible. The fact that \(p\)-IC elections may have little multiplicity does not defeat it, since the programme explicitly evaluates instance regimes rather than requiring every statistical culture to be high-multiplicity.
Nor can one object that the remaining hardness is caused by candidate relabeling. That is precisely a valid Class B outcome: continuization removes the population-matching layer while preserving the candidate-alignment layer. Calling this an inert restatement would contradict the programme’s own rule that hardness surviving in the continuous mirror is a worthwhile result.
The strongest available objection is therefore one of fit rather than validity. Proposition 2 is auxiliary to the paper’s main contribution: the paper ultimately uses the approvalwise distance and studies statistical cultures, maps, cohesiveness, and PAV runtimes. The continuous problem above is a pairwise distribution-alignment problem, not bribery, control, winner robustness, or manipulation. If ChoCo restricts “computational social choice” to those intervention and outcome problems, it could reasonably decline to count this mirror as central.
That objection does not establish the requested universal negative. The metric is central to the paper’s framework, its continuous version is an exact high-multiplicity formulation, and a continuous PAV problem,
\[ \max_{W:|W|=k}\sum_A \mu_A h(|A\cap W|), \]
would provide a second natural mirror of the paper’s computational content. It too is a valid high-multiplicity version, regardless of whether it remains hard.
Thus none of the decisive negative grounds applies: there is a named computational result, multiplicity is meaningful, identity is already quotiented out, the continuum does not degenerate, and no prior continuous treatment has been identified. The honest conclusion is that this paper does support at least one worthwhile continuous mirror; the negative case can challenge its priority within ChoCo, but cannot defeat the anchor.
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.