Answer: Polynomial-time solvable, including the binary count and the complete list of value tables.
Theorem 18 — class: other
Given \(m\) alternatives, a rational distribution \(\mu\) supported on \(\tau\) rankings, and an explicitly listed subgroup \(U\le S_m\) of alternative relabelings, let \(U\mu=\{\psi\mu:\psi\in U\}\) and \(B(\nu)=\arg\max_{c}\sum_q\nu_q(m-\operatorname{rank}_q(c))\). Count and compactly describe the deterministic rules \(f:U\mu\to C\) satisfying \(f(\nu)\in B(\nu)\) and \(f(\psi\nu)=\psi f(\nu)\) for every \(\nu\in U\mu\) and \(\psi\in U\).
Let \(C=\{1,\ldots,m\}\), with \(m\ge2\). Rankings are strict linear orders. A society is given by its support: the list of \(\tau\) distinct rankings with positive binary rational masses \(\mu_q\), summing to \(1\); \(\tau\) is the support size, not the number of possible rankings.
The input also lists every element of a subgroup \(U\le S_m\), each as a permutation of \(C\). Let \(L\) be the total input bit length; state running times in \(m,\tau,L,|U|\).
Relabeling replaces each alternative \(c\) in a ranking by \(\psi(c)\), and \((\psi\nu)_q=\nu_{\psi^{-1}q}\), with unlisted rankings having mass zero. Let \(U\mu=\{\psi\mu:\psi\in U\}\), identifying equal distributions.
Let \(B(\nu)\) be the Borda winner set, retaining all score ties. Count exactly the distinct functions \(f:U\mu\to C\) satisfying \(f(\nu)\in B(\nu)\) and \(f(\psi\nu)=\psi f(\nu)\) for every \(\nu\in U\mu\) and \(\psi\in U\).
The computational output consists of the binary count and a list of the distinct functions, each represented by its value table on the distinct distributions in \(U\mu\).
Can this counting and description problem be solved in time polynomial in \(m,\tau,L,|U|\), or is it NP-hard under polynomial-time Turing reductions?
For finite profiles, when every profile stabilizer has only the identity alternative relabeling and reversal is excluded, equivariant refinements of an equivariant correspondence are parametrized by independent winner choices at orbit representatives; their number is the product of the winner-set sizes. [Bubboloni–Gori](https://arxiv.org/html/1506.06069)
No result settling the exact rational-distribution problem above was located.
The problem is polynomial-time solvable, including the complete list of functions.
Let
\[
\]
\(H=\operatorname{Stab}_U(\mu)=\{h\in U:h\mu=\mu\}\), and define
\(A=B(\mu)\cap\{c\in C:h(c)=c\text{ for every }h\in H\}\).
The exact count is \(|A|\). For each \(a\in A\), the corresponding function is
\(f_a(\psi\mu)=\psi(a)\).
In particular, there are at most \(m\) functions, each with at most \(|U|\) table entries.
We prove this characterization and give an exact polynomial-time algorithm.
Write a ranking as \(q=(q_1,\ldots,q_m)\), with the most preferred alternative first. Let \(\operatorname{pos}_q(c)\) be the position of \(c\) in \(q\). Use the Borda score
\(s_\nu(c)=\sum_q\nu_q\bigl(m-\operatorname{pos}_q(c)\bigr)\),
where the sum ranges over rankings with positive mass. Thus
\(B(\nu)=\{c\in C:s_\nu(c)=\max_{d\in C}s_\nu(d)\}\).
Relabeling preserves positions:
\(\operatorname{pos}_{\psi q}(\psi c)=\operatorname{pos}_q(c)\).
Moreover, the mass of \(\psi q\) in \(\psi\nu\) is \(\nu_q\). Consequently,
\(s_{\psi\nu}(\psi c)=s_\nu(c)\).
Since \(\psi\) is a bijection of \(C\), this proves
\(B(\psi\nu)=\psi B(\nu)\),
including all score ties.
Relabeling defines a group action: for \(g,h\in U\),
\(g(h\nu)=(gh)\nu\).
In particular, \(H\) is a subgroup of \(U\).
Proposition. Evaluation at \(\mu\) gives a bijection between the requested functions and \(A\).
Necessity. Suppose \(f\) satisfies the requirements, and put \(a=f(\mu)\). The winner requirement gives \(a\in B(\mu)\). For every \(h\in H\), equivariance gives
\(a=f(\mu)=f(h\mu)=h f(\mu)=h(a)\).
Thus \(a\in A\).
Also, for every \(\psi\in U\),
\(f(\psi\mu)=\psi f(\mu)=\psi(a)\).
Therefore \(a\) determines the entire function uniquely.
Sufficiency. Fix \(a\in A\), and define \(f_a(\psi\mu)=\psi(a)\). Three checks are required.
\(f_a(g(\psi\mu))=f_a((g\psi)\mu)=(g\psi)(a)=g f_a(\psi\mu)\).
Thus \(f_a\) satisfies both requirements. Finally, different \(a\)'s give different functions because \(f_a(\mu)=a\). This proves the proposition.
Consequently, the exact count is
\(N=\left|B(\mu)\cap\operatorname{Fix}_C(H)\right|\),
where \(\operatorname{Fix}_C(H)\) denotes the alternatives fixed by every element of \(H\). If this intersection is empty, the count is zero and the function list is empty.
Write the input masses as \(\mu_{q_i}=a_i/b_i\), with positive integers \(a_i,b_i\), for \(1\leq i\leq\tau\). Reduction to lowest terms is unnecessary.
Define
\(D=\prod_{i=1}^{\tau}b_i\)
and
\(w_i=a_i(D/b_i)\).
Each division is exact. We have
\(\mu_{q_i}=w_i/D\)
and
\(\sum_{i=1}^{\tau}w_i=D\).
The denominator bit lengths sum to at most \(L\), so \(D\) has at most \(L+1\) bits. Since the masses are positive and sum to one, each \(w_i\) satisfies \(1\leq w_i\leq D\).
Compute the integer Borda scores
\(S(c)=\sum_{i=1}^{\tau}w_i\bigl(m-\operatorname{pos}_{q_i}(c)\bigr)\).
These satisfy \(S(c)=D s_\mu(c)\). Multiplication by the positive integer \(D\) preserves every score comparison and tie, so their maximizers are exactly \(B(\mu)\).
Furthermore,
\(0\leq S(c)\leq(m-1)D\).
Thus all score calculations use integers with \(O(L+\log(m+1))\) bits. No expansion into \(D\) individual voters is needed.
Let \(n=|U|\). Use the following algorithm.
\(\{(\psi q_i,w_i):1\leq i\leq\tau\}\),
with the shared denominator \(D\).
\((\psi_1(a),\ldots,\psi_r(a))\),
where \(r=|U\mu|\).
For step 3, exact equality can be checked by matching rankings and their integer weights. Relabeling is bijective on rankings, so every transformed support still consists of exactly \(\tau\) distinct rankings. Equal transformed supports with equal corresponding weights represent equal distributions, including their zero masses on unlisted rankings.
The output includes the ordered domain \((\nu_1,\ldots,\nu_r)\) once, represented by its support lists. Each row then specifies one function's value on every distinct distribution. The proposition proves that these rows list all requested functions exactly once.
Set \(k=\lceil\log_2(m+1)\rceil\) and \(K=L+k+2\).
A deliberately conservative bound for a straightforward implementation is
\(O\bigl(n^2\tau^2m^2K^2\bigr)\)
elementary bit operations, using schoolbook integer arithmetic and direct support comparisons. Explicitly:
All these costs fit the displayed bound, which is polynomial in \(m,\tau,L,|U|\).
There are at most \(n\) distinct distributions and at most \(m\) functions. With the domain represented once, the output has size
\(O\bigl(n\tau(mk+K)+mnk+k\bigr)\)
bits. Thus the required explicit description also has polynomial size.
The related finite-profile framework appears in [Bubboloni–Gori](https://arxiv.org/html/1506.06069). The argument above handles the given rational distributions directly and permits arbitrary stabilizers.
⟨structured verdict parsed — rendered above⟩
The prover resolves the task correctly. The characterization of all admissible functions is rigorous, the algorithm uses exact arithmetic, and both its running time and explicit output size are polynomial in the requested parameters. No major or minor mathematical gaps were found.
The score definition assigns a ranking’s alternative in position \(j\) the score \(m-j\). This is a valid Borda convention.
The identity \(\operatorname{pos}_{\psi q}(\psi c)=\operatorname{pos}_q(c)\) follows directly from the prescribed relabeling action. The mass identity \((\psi\nu)_{\psi q}=\nu_q\) follows from the task’s definition of transformed distributions.
Consequently, the calculation \(s_{\psi\nu}(\psi c)=s_\nu(c)\) is correct. Because \(\psi\) bijectively permutes the alternatives, it also bijectively maps score maximizers. Thus \(B(\psi\nu)=\psi B(\nu)\), including ties.
Assessment: Correct, with all necessary hypotheses satisfied.
The action identity \(g(h\nu)=(gh)\nu\) agrees with the specified distribution action and permutation composition. Therefore the stabilizer \(H\) is indeed a subgroup.
For necessity, the prover correctly establishes that an admissible function’s value \(a=f(\mu)\):
These conclusions use precisely the winner and equivariance conditions required by the task.
For sufficiency, every required check is present:
Finally, evaluation at \(\mu\) distinguishes functions arising from different alternatives.
Assessment: The claimed bijection is fully established. The exact count is \(|B(\mu)\cap\operatorname{Fix}_C(H)|\), and there are at most \(m\) functions. No trivial-stabilizer assumption is needed.
The common denominator \(D=\prod_i b_i\) and weights \(w_i=a_i(D/b_i)\) are correctly defined even when input fractions are unreduced.
All stated arithmetic identities hold:
The bit-length bound for \(D\) follows from the sum of the input denominator bit lengths, which is at most \(L\). A numerically large denominator therefore does not create a superpolynomial binary representation.
The integer scores satisfy \(S(c)=D s_\mu(c)\). Since \(D>0\), maximizers and all ties are preserved exactly. The bound \(0\leq S(c)\leq(m-1)D\) follows from normalization and the range of individual Borda scores.
Assessment: Correct. All critically used integers have the claimed polynomial bit lengths; there is no implicit expansion into individual voters.
Relabeling is a bijection on strict rankings. Thus every transformed support retains exactly \(\tau\) distinct rankings and positive masses.
All transformed distributions use the same denominator \(D\). Accordingly, equality of their ranking supports and corresponding integer weights is necessary and sufficient for equality of distributions. Zero masses outside the listed support cause no additional complication.
Enumerating every explicitly listed permutation therefore produces the whole orbit. Removing duplicate distributions yields exactly the required domain. Comparing each transformed distribution with \(\mu\) also yields exactly \(H\).
Assessment: Correct. The algorithm respects the distinction between support size, group size, and number of distinct orbit distributions.
For each \(a\in A\), the row \((\psi_1(a),\ldots,\psi_r(a))\) gives the value of \(f_a\) on the ordered domain \((\nu_1,\ldots,\nu_r)\).
The proved well-definedness ensures that the chosen orbit representatives do not affect these values. The bijection ensures that every admissible function appears and that no function appears twice.
Providing the domain once through its support lists, using the shared denominator, makes the rows interpretable as the requested value tables.
Assessment: Correct and complete.
The individual bounds are consistent with the described implementation:
For \(m\geq2\), \(\tau\geq1\), and \(n=|U|\geq1\), these costs are dominated by \(O(n^2\tau^2m^2K^2)\).
There are at most \(n\) domain distributions and at most \(m\) functions. The claimed output-size bound accommodates their support representations, integer weights, shared denominator, table entries, and binary count.
Assessment: The explicit description requirement is met in polynomial time, not merely the counting requirement.
The argument handles arbitrary score ties, nontrivial stabilizers, repeated orbit distributions, the identity subgroup, and an empty set \(A\). In the last case, the binary count is zero and the function list is empty, as required.
The finite-profile reference is contextual: no step depends on importing its theorem or assuming its trivial-stabilizer hypotheses.
No mathematical repair or additional clarification is needed. The polynomial-time conclusion follows from the supplied proof and algorithm.
⟨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.