| paper | Selecting the Most Conflicting Pair of Candidates |
| authors | Théo Delemazure, Łukasz Janeczko, Andrzej Kaczmarczyk, Stanisław Szufa |
| venue | IJCAI 2024 |
| filed under | multiwinner · multiwinner |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
The paper’s numbered results concern axioms and impossibility properties, not the complexity or algorithms of a computational problem. Continuous MaxNash Conflict Pair is a direct, author-recognizable high-multiplicity restatement, but it cannot satisfy the mandatory computational-anchor bit. Therefore the grade is red despite the clean continuous analogue.
fails bit a — no named computational result to mirror
The mirror covers the MaxNash rule and its pairwise conflict objective, while leaving the axiomatic impossibility results, other rule properties, metrics, and experiments outside the computational mirror.
The paper has no qualifying computational anchor. Its named results are axiomatic: Proposition 1 and Theorem 1 give impossibility results about axioms; Proposition 2, proved by the authors with details deferred to the full version, establishes axioms for MaxSum and MaxNash; Proposition 3 does the same for MaxSwap; and Proposition 4 establishes balance preference. None asserts NP-hardness, membership in \( \mathrm{P} \), fixed-parameter tractability, approximation complexity, or an algorithmic classification. The experiments and the unnumbered observation about polynomial-time pair selection do not repair that gap.
The strongest honest positive case is therefore a prospective mirror of Proposition 2, not a formally admissible anchor. My lead would be Continuous MaxNash Conflict Pair.
Take \(m\) candidates \(C\), let \(T\) be the set of complete rankings of \(C\), and give each ranking \(t\) a rational mass \(\mu_t\), with \(\sum_t\mu_t=1\). For a pair \(\{a,b\}\), write \(d_t(a,b)=|t(a)-t(b)|\), and define
\[ q^+_\mu(a,b)=\sum_{t:a\succ_t b}\mu_t d_t(a,b), \qquad q^-_\mu(a,b)=\sum_{t:b\succ_t a}\mu_t d_t(a,b). \]
The instance is \((C,\mu)\). The task is to output every unordered pair maximizing
\[ S_\mu(a,b)=q^+_\mu(a,b)\,q^-_\mu(a,b). \]
This is exactly the paper’s MaxNash rule with voter counts replaced by population masses. A solution is a maximizing pair, with all ties retained as in the paper’s rule.
The natural regime is a very large issue-ranking or political-preference population: millions of respondents, perhaps \(m=10\)–\(20\) issues, and only \(K\) distinct complete rankings represented, where \(K\ll n\). The repeated types could arise from ideological or institutional cohorts, or from a survey instrument producing a finite collection of recurring ranking patterns. Since the paper’s rule uses only rankings, a type needs no hidden individual attributes: agents with the same ranking are genuinely indistinguishable for this problem. Mass is their fraction of the population, and the decision variable is the selected pair of candidates.
This is an author-recognizable mirror. If \(\mu_t=n_t/n\), then
\[ q^+_\mu(a,b)=\frac{1}{n}\sum_{v:a\succ_v b}v(ab), \qquad q^-_\mu(a,b)=\frac{1}{n}\sum_{v:b\succ_v a}v(ba), \]
so \(S_\mu(a,b)\) is the discrete MaxNash score divided by \(n^2\). Thus all winners and ties are preserved exactly after clearing denominators. The continuous model does not fractionalize rankings, replace individual choices by coalitions, or change the conflict objective.
Its expected classification is Class A, but weakly so: enumerate candidate pairs and compute the two weighted sums. With a support list of \(K\) ranking types this takes \(O(Km^2)\) arithmetic operations; with the full type vector it takes \(O(\tau m^2)\), where \(\tau=m!\). The same construction gives a continuous MaxSwap problem by maximizing \(\min(q^+_\mu,q^-_\mu)\), corresponding to Proposition 3, but I would not present it as a second anchor.
The useful follow-up questions are genuinely continuous ones: minimum population mass that must change before the winning conflict pair changes; robust pair selection under an \(L_1\) perturbation budget; and the paper’s proposed extension from pairs to larger committees, for example maximizing the minimum continuous conflict score over all pairs in a committee.
The weakest point is decisive: this mirror is mainly high-multiplicity compression, not a new computational phenomenon. The discrete problem is already easy, so continuization does not unlock column generation, eliminate population-driven hardness, or create a meaningful complexity separation. I would therefore argue that the paper contains a sensible continuous population analogue, with Proposition 2 as its closest mathematical handle, but I would not claim that it passes ChoCo’s strict named-computational-anchor gate.
I would reject the mirror. The decisive point is that this paper supplies no qualifying computational anchor at all. Proposition 1 and Theorem 1 are impossibility results about axioms; Propositions 2–4 establish axiomatic properties of rules. The experiments are descriptive. Nothing states a complexity classification, algorithmic theorem, approximation result, or parameterized result for a computational problem. Thus there is no paper result whose high-multiplicity computational analogue ChoCo could classify.
The proposed Continuous MaxNash Conflict Pair is a legitimate normalization, but it does not repair that absence. For any distribution \(\mu\), its quantities are simply
\[ q^+_\mu(a,b)=\mathbb{E}_{t\sim\mu} [\mathbf{1}_{a\succ_t b}|t(a)-t(b)|], \qquad q^-_\mu(a,b)=\mathbb{E}_{t\sim\mu} [\mathbf{1}_{b\succ_t a}|t(a)-t(b)|]. \]
The rule then scans the \(O(m^2)\) candidate pairs and maximizes \(q^+_\mu(a,b)q^-_\mu(a,b)\). The entire ranking distribution is relevant only through these \(O(m^2)\) pairwise moments. A political or ideological continuum, a finite collection of cohorts, and a survey distribution over rankings all collapse to exactly the same statistics. Refining types with identities, locations, ideology, or other attributes does nothing unless the rule is changed to use those attributes.
That is not merely the observation that the continuous answer happens to be easy. A simple Class A result could still be valuable. The more fundamental problem is that the paper has no computational question here beyond evaluating a finite collection of explicitly defined pair scores. There is no mass-transfer decision, exponentially large configuration space, pricing problem, or population-driven combinatorial structure for continuization to expose. Replacing voter counts by expectations is a representation change, not a new computational object.
The strongest rescue would be to ask for the minimum population mass whose rankings must change before the selected pair changes, or for robust pair selection under an \(L_1\) uncertainty budget. Those could be sensible new projects, but they are generic robustifications of any finite voting rule. They introduce an intervention metric and an adversarial uncertainty model absent from the paper; they are not continuous versions of any named theorem. The same objection applies to the proposed committee extension: maximizing the minimum conflict score over a committee would be a new candidate-subset problem based on the already-computed score matrix, not a population continuization of a result proved here.
A continuous MaxSwap analogue is no stronger. It replaces the product by
\[ \max_{\{a,b\}}\min(q^+_\mu(a,b),q^-_\mu(a,b)), \]
but remains the same pairwise aggregation followed by a scan. The axioms can certainly be rewritten for measures, perhaps using couplings in place of voter bijections, but that would produce continuous axiomatic social choice—which the programme explicitly places out of scope—not computational complexity theory.
The fair conclusion is therefore narrower than “no distributional model is possible.” A high-multiplicity electorate of issue-ranking voters is perfectly sensible, and the paper can be given a mathematically clean continuous restatement. But the restatement is not a worthwhile ChoCo mirror: the paper contributes axioms, rules, and empirical interpretation, not a computational problem whose complexity landscape continuization could reveal. The negative case is weakest only if ChoCo is willing to fund generic robustness or new committee-optimization problems detached from the paper’s actual results. Under the programme’s stated computational-anchor standard, it should not.
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.