| paper | d4-journals-mss-2025-0012 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Polynomial-time solvable. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Proposition 2.2
statement extracted from the paper’s text layer
Given \(n\) alternatives and two distributions \(\mu,\nu\) over rankings in \(S_n\), each specified by its positive-support rankings and binary rational masses, with each support a Condorcet domain, decide whether there is a relabeling \(\pi\in S_n\) such that \(\nu(\pi\cdot\rho)=\mu(\rho)\) for every ranking \(\rho\).
Each ranking is a voter type, and its mass is its fraction of the electorate. Compare two such societies for exact equality after relabeling alternatives; the candidate relabelings can be checked using the paper’s normalization approach.
The Condorcet-domain condition may only restrict the supports: the weighted relabeling question also makes sense for arbitrary ranking distributions, so its connection to the paper’s study of domain structure is limited.
fatal: False
This mirror covers Proposition 2.2’s isomorphism question; it leaves the paper’s enumeration of maximal domains, maximum-size theorem, and structural observations untouched.
The strongest honest mirror I see is a weighted version of the paper’s Condorcet-domain isomorphism test. The paper’s Proposition 2.2, proved here, says that isomorphism between two Condorcet domains of equal size can be tested in time polynomial in the domain size and the number of alternatives. Its proof normalizes the domains to contain the identity order, then checks a number of candidate relabelings bounded by the domain size. This is a real polynomial-time result, but it is a small anchor: the paper gives no named hardness result or broader complexity classification.
Mass-preserving isomorphism of continuous Condorcet societies is my lead mirror. An instance consists of \(n\) alternatives and two distributions \(\mu,\nu\) over rankings in \(S_n\), given by their positive-support rankings and binary rational masses. Require each support to be a Condorcet domain; in applications, one could restrict to maximal domains, the paper’s main focus. A type is a complete ranking, and its mass is the fraction of that electorate holding the ranking. The question is whether there is a relabeling \(\pi\in S_n\) of the alternatives such that \(\nu(\pi\cdot\rho)=\mu(\rho)\) for every ranking \(\rho\). A solution is the witnessing \(\pi\), or a “no” answer. This is a feasibility question, not an optimization problem.
The regime is a large electorate in which many people submit the same complete ballot: for example, two large polling populations with relatively few distinct rankings, whose candidate labels have been anonymized. Their sizes may be in the millions while each has only \(\tau\) supported rankings. The shares matter because the question compares the composition of the populations, not merely which rankings are possible.
This is close to the paper’s problem in a concrete way: it keeps rankings as types and candidate relabeling as the equivalence being tested, while attaching population shares to those types. I would expect this weighted version to be tractable in \((n,\tau,L)\), where \(L\) is the mass encoding length. Fix a ranking in the first support; each possible image of that ranking in the second support determines at most one candidate relabeling. There are at most \(\tau\) such candidates, and each can be checked by comparing transformed rankings and their exact masses. Proposition 2.2 supplies the direct unweighted precedent; this weighted bound is an extension, not a claim made in the paper.
The mirror covers Proposition 2.2’s isomorphism question, not the paper’s full enumeration of maximal domains, its finite-degree classification, or its structural observations. A natural follow-up is whether one can find the relabeling minimizing total variation between two mass distributions, rather than requiring exact equality; the same candidate-relabeling idea suggests a tractable version. One could also study whether sampling noise changes the practical value of the test.
The weak point is that the paper tests isomorphism of *sets* of rankings, whereas this mirror asks for equality of the mass attached to each ranking after relabeling. That is a reasonable population-level extension, but it is not the paper’s stated problem, and its tractability does not show that continuization dissolves discrete hardness. The case is therefore a narrow, plausible mirror of one named polynomial-time result, not evidence for a larger complexity-landscape claim.
Proposition 2.2 is the one serious anchor: it states a named polynomial-time result, and a large electorate with repeated ballot types is a plausible regime. The objection is not that its continuous version would have the same answer, or that a polynomial result is uninteresting. It is that the proposition’s input is not a society.
A Condorcet domain is a set of admissible rankings. Its defining property quantifies over every odd electorate drawn from that set; an observed electorate and the shares of its ballot types do not enter. If the proposed mirror takes two domains as the supports of distributions and asks whether their supports are isomorphic, the masses are irrelevant: changing them arbitrarily leaves the question unchanged. That preserves Proposition 2.2, but does not make the population the computational object.
The mass-preserving repair is coherent, and the anonymized-polls scenario makes it more than a straw man. But it asks a different question: whether two *observed distributions* over rankings align under candidate relabeling. The Condorcet-domain condition then restricts the allowed supports without giving the question its purpose; the same alignment question works for arbitrary ranking distributions. A distance version, such as minimizing total variation over relabelings, makes the masses matter more, but moves still further toward comparing empirical profiles rather than studying the structure or computational properties of Condorcet domains.
So the strongest case against is a relevance boundary: the literal mirror leaves the population unused, while the version that uses population shares changes the object of study. I would not call this airtight. Comparing large populations up to candidate relabeling could itself be worthwhile, and authors interested in empirical domain identification might recognize it as a natural extension. But that would support a neighboring project; it does not clearly establish a worthwhile continuous mirror of the paper’s result.
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.