Answer: Polynomial-time solvable.
Proposition 2.2 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateIsomorphism between two CDs of equal size can be tested in time which is polynomial in the size of the domain and 𝑛.
statement extracted from the paper’s text layer; consult the paper for the exact wording
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\).
Let \(m\geq 1\) be the number of alternatives, labelled by \([m]\). Rankings are strict linear orders, represented by elements of \(S_m\).
A society is given by its support: the list of types with positive mass, each with its mass as a binary rational. Masses sum to \(1\). Support size counts listed types, not all \(m!\) possible rankings.
Input consists of two such societies \(\mu,\nu\). Write \(\tau_\mu,\tau_\nu\) for their support sizes, \(\tau=\max\{\tau_\mu,\tau_\nu\}\), and \(L\) for the total input bit length; state running times in \(m,\tau,L\).
Both supports are promised to be Condorcet domains: for every triple of alternatives, some alternative never occupies some position among first, middle, and last in the rankings restricted to that triple.
For \(\rho=(a_1,\ldots,a_m)\), define \(\pi\cdot\rho=(\pi(a_1),\ldots,\pi(a_m))\). Unlisted rankings have mass zero. Decide whether some \(\pi\in S_m\) satisfies \(\nu(\pi\cdot\rho)=\mu(\rho)\) for every \(\rho\in S_m\).
Is this mass-preserving relabeling problem solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?
Known discrete result: relabeling isomorphism of two equally sized, unweighted Condorcet domains is decidable in time polynomial in their cardinality and the number of alternatives. This result does not state a complexity classification for distributions with rational masses.
The problem is polynomial-time solvable, even without the Condorcet-domain promise. The crucial fact is that choosing the image of one full ranking uniquely determines the relabeling.
Let \(D_\mu,D_\nu\subseteq S_m\) be the two supports. Fix any ranking \(\rho^*=(a_1,\ldots,a_m)\in D_\mu\); such a ranking exists because the masses sum to \(1\).
For each \(\sigma=(b_1,\ldots,b_m)\in D_\nu\), define \(\pi_\sigma\) by
\(\pi_\sigma(a_i)=b_i\) for every \(i\in[m]\).
Both lists contain every alternative exactly once, so \(\pi_\sigma\) is a permutation. Moreover, it is the unique permutation satisfying \(\pi_\sigma\cdot\rho^*=\sigma\): equality of the ordered lists forces every equation \(\pi_\sigma(a_i)=b_i\).
Consequently, any mass-preserving relabeling must be one of these at most \(\tau_\nu\) candidates. Indeed, positivity of \(\mu(\rho^*)\) forces its image to belong to \(D_\nu\).
First reject if \(\tau_\mu\ne\tau_\nu\). This rejection is valid because a mass-preserving relabeling maps one support bijectively onto the other.
Otherwise:
All mass comparisons are exact. For positive denominators, the binary rationals \(p/q\) and \(r/s\) are equal precisely when \(ps=rq\), so no floating-point arithmetic or expansion into repeated rankings is needed.
Completeness. Suppose a valid relabeling \(\pi\) exists. Then \(\sigma=\pi\cdot\rho^*\) belongs to \(D_\nu\). By uniqueness of the permutation taking \(\rho^*\) to \(\sigma\), the algorithm’s candidate \(\pi_\sigma\) equals \(\pi\). Every support and mass check therefore passes.
Soundness. Suppose a candidate \(\pi_\sigma\) passes. For every \(\rho\in D_\mu\), the algorithm has verified both \(\pi_\sigma\cdot\rho\in D_\nu\) and \(\nu(\pi_\sigma\cdot\rho)=\mu(\rho)\).
The action of a permutation on rankings is bijective, since applying its inverse reverses the action. Thus \(\pi_\sigma\cdot D_\mu\) has cardinality \(\tau_\mu\). It is contained in \(D_\nu\), whose cardinality is also \(\tau_\mu\), so \(\pi_\sigma\cdot D_\mu=D_\nu\).
Now let \(\rho\notin D_\mu\). If \(\pi_\sigma\cdot\rho\) belonged to \(D_\nu=\pi_\sigma\cdot D_\mu\), injectivity would imply \(\rho\in D_\mu\), a contradiction. Hence both \(\mu(\rho)\) and \(\nu(\pi_\sigma\cdot\rho)\) are zero. The required equality therefore holds for every ranking in \(S_m\).
An elementary implementation searches the target support by scanning its listed rankings. There are at most \(\tau\) candidates, at most \(\tau\) source rankings per candidate, and at most \(\tau\) target rankings per search.
Each ranking has \(m\) entries. Each rational’s encoding has at most \(L\) bits, and schoolbook multiplication compares two rational masses in \(O(L^2)\) bit operations. Including candidate construction, ranking transformations, comparisons, and elementary data access, a conservative bound for this implementation is \(O(\tau^3(m+L)^2)\) bit operations. This is polynomial in \(m,\tau,L\).
The argument applies to arbitrary supports of strict full rankings. Thus the rational masses introduce no hardness here, and the stated discrete Condorcet-domain result is unnecessary for this problem.
⟨structured verdict parsed — rendered above⟩
The prover’s argument is correct and fully resolves the task. It gives a polynomial-time algorithm for arbitrary explicitly listed supports of strict full rankings, so the Condorcet-domain promise is unnecessary.
No false statements, unjustified steps, missing hypotheses, or repair requirements were found.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.