Answer: —
Theorem 1 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateMaximin with linear order tie-breaking does not converge for the dynamics BR, TOP, TB, KT, and SWAP. 5For a, b ∈π(C), the Kendall-Tau distance between them is de- fined as dist(a, b) = |{i, j} ∈C×C|(i ≻a j and j ≻b i) or (j ≻a i and i ≻b j)}|.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given candidates \(C\), a fixed linear tie-break, and finitely many delegated voter blocs \(t\) with rational masses \(\mu_t>0\), \(\sum_t\mu_t=1\), shared truthful rankings \(r_t\), and current ballots \(b_t\), set \(P_\mu(a,b)=\sum_{t:\,a\succ_{b_t} b}\mu_t\) and \(\mathrm{mm}_\mu(c)=\min_{d\ne c}P_\mu(c,d)\). Start from \(b_t=r_t\). At each step, one bloc changes its whole ballot to a best response: the new winner is strictly preferred under \(r_t\) to the current winner, and no alternative ballot gives that bloc a more-preferred winner. Decide whether an infinite legal sequence is reachable from the truthful state, equivalently whether a directed cycle is reachable among the finitely many ballot profiles.
Given candidates \(C\) with \(m=|C|\ge 2\) and a fixed linear tie-break, a society is given by its support: the list of \(\tau\) delegated bloc types, each with a positive binary rational mass \(\mu_t\), where \(\sum_t\mu_t=1\), and a strict truthful ranking \(r_t\). Types include delegate identity, so distinct blocs may share a ranking; \(\tau\) is the support size, not the number of possible rankings. Let \(L\) be the total input bit length; state running times in \(m,\tau,L\).
Each bloc controls one strict ballot \(b_t\) over all candidates and changes its entire mass together; masses and bloc identities remain fixed. Initially \(b_t=r_t\).
For distinct candidates \(a,d\), set \(P_\mu(a,d)=\sum_{t:a\succ_{b_t}d}\mu_t\). The Maximin winner \(W(b)\) maximizes \(\min_{d\ne a}P_\mu(a,d)\), with ties resolved by the given order.
A legal move replaces exactly one ballot \(b_t\) by any strict ranking \(b'_t\), holding all other ballots fixed, such that \(W(b')\succ_{r_t}W(b)\) and no alternative ballot for that bloc yields a winner strictly preferred to \(W(b')\). All ballots attaining that best winner are allowed; the scheduler is arbitrary, with no fairness requirement.
Is deciding whether an infinite legal sequence exists from the truthful profile—equivalently, whether a directed cycle is reachable in the ballot-profile graph—in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard?
Discrete Maximin with linear tie-breaking can cycle under strictly improving best responses starting from truthful ballots. [Koolyk et al. (2017)](https://www.ijcai.org/proceedings/2017/0039.pdf)
For weighted plurality with fixed candidate scores, deciding existence of a cycle of a specified length under simultaneous group beneficial direct moves is \(\mathrm{NP}\)-complete; this concerns different rules and moves. [Goldberg et al. (2026)](https://ifaamas.org/Proceedings/aamas2026/pdfs/MDLZ8000.pdf)
No complexity classification for the exact rational-mass Maximin reachability problem above was identified in the literature searched.
I do not resolve whether the unrestricted problem is in $\mathrm{P}$ or is $\mathrm{NP}$-hard.
I prove two additional structural results:
I also give self-contained proofs of the polynomial-time best-response oracle, the $\mathrm{PSPACE}$ upper bound, and the polynomial-time algorithm when both the number of candidates and the number of distinct masses are fixed.
Throughout, “earlier” refers to the fixed tie-break. A string such as $\mathrm{BCAD}$ denotes the strict ballot $B\succ C\succ A\succ D$.
Proposition. If some bloc has mass greater than $1/2$, the truthful profile has no legal move. From an arbitrary initial profile, every legal sequence has length at most one.
Proof. Let the bloc have mass $\mu>1/2$, and let $p$ be the first candidate in its current ballot. For every $x\ne p$,
$$ P_\mu(p,x)\ge \mu>\frac12, \qquad P_\mu(x,p)\le 1-\mu<\frac12. $$
Thus $p$ has score greater than $1/2$, while every rival has score less than $1/2$. The winner is always the first candidate in this bloc’s ballot, independently of all other ballots.
Consequently, no other bloc can change the winner. The dominant bloc can attain its truthful first choice by placing it first. If a legal move occurs, it must elect that candidate, after which no further legal move is possible. At truthfulness, this candidate already wins. $\square$
In particular, two blocs with unequal masses have no legal move from truthfulness.
Suppose the two masses are $1/2$. Fix one bloc’s ballot, whose first candidate is $q$.
Lemma. The other bloc can elect exactly the candidates that are no later than $q$ in the tie-break.
Proof. The fixed ballot contributes $1/2$ to every support $P_\mu(q,x)$, so $q$ always has score at least $1/2$. For any $p\ne q$,
$$ \operatorname{score}(p)\le P_\mu(p,q)\le \frac12. $$
If $p$ is later than $q$, it therefore cannot win.
Conversely, submitting a ballot with $q$ first elects $q$: both ballots then put $q$ first, giving it score $1$.
Let $p$ be earlier than $q$. Submit a ballot beginning with $p\succ q$, followed by all other candidates. Both $p$ and $q$ have score $1/2$. Every other candidate $x$ lies below $q$ in both ballots, so
$$ P_\mu(x,q)=0. $$
Thus all other candidates have score $0$, and $p$ wins the tie against $q$. $\square$
The best attainable winner is therefore the bloc’s truthfully most preferred candidate in this initial segment of the tie-break. This characterization permits every ballot attaining that winner.
Proposition. With two blocs and three candidates, every legal sequence from truthfulness has length at most two.
Proof. Unequal masses are covered by Proposition 1.1. Assume equal masses, and name the candidates so that the tie-break is $A$ before $B$ before $C$.
If a truthful ballot has $A$ first, then $A$ wins regardless of the other ballot: its score is at least $1/2$, every rival’s score is at most $1/2$, and $A$ wins all ties. That bloc already obtains its truthful first choice, and the other bloc cannot change the winner. Hence the truthful profile is terminal.
If both truthful ballots have the same first candidate, that candidate wins and both blocs obtain their first choice, again making the profile terminal.
The remaining case has truthful first candidates $B$ and $C$. Call these blocs $1$ and $2$, respectively. Their possible truthful rankings are
$$ r_1\in\{\mathrm{BAC},\mathrm{BCA}\}, \qquad r_2\in\{\mathrm{CAB},\mathrm{CBA}\}. $$
We examine both possibilities for $r_2$.
If $r_1=\mathrm{BAC}$, all three candidates have score $1/2$, and $A$ wins. Bloc $2$ already obtains its best attainable winner against a ballot with $B$ first. Bloc $1$ can improve only by electing its first choice $B$.
Any replacement ballot electing $B$ must have $B$ first. If it instead has $A$ first, $A$ necessarily wins; if it has $C$ first, both ballots have $C$ first and $C$ wins. Of the two ballots with $B$ first, $\mathrm{BAC}$ elects $A$, while $\mathrm{BCA}$ elects $B$. Thus the only legal move leads to $(\mathrm{BCA},\mathrm{CAB})$.
If $r_1=\mathrm{BCA}$, this same profile is already truthful.
At $(\mathrm{BCA},\mathrm{CAB})$, the winner is $B$. Only bloc $2$ can improve, and its best attainable winner is $A$. Any ballot electing $A$ must have $A$ first: a ballot with $B$ first makes $B$ unanimously preferred to $A$, and a ballot with $C$ first makes $C$ unanimously preferred to $A$.
After this move, the ballot with $A$ first fixes the winner at $A$ against every possible ballot of bloc $1$. Bloc $2$ still faces a ballot with $B$ first, so its best attainable winner remains $A$. The resulting profile is terminal.
This exhausts all truthful profiles. There are at most two legal moves. $\square$
For two candidates and any number of blocs, truthfulness is also terminal: a bloc’s truthful ballot already maximizes the support for its preferred candidate and minimizes the opponent’s support. Reversing that ballot cannot improve its winner.
Use tie-break $A$ before $B$ before $C$ before $D$, equal masses $1/2$, and truthful rankings
$$ r_1=\mathrm{BCAD}, \qquad r_2=\mathrm{CABD}. $$
Consider the following profiles. Scores are listed in candidate order $(A,B,C,D)$.
| State | Bloc $1$ | Bloc $2$ | Scores | Winner |
|---|---|---|---|---|
| $0$ | $\mathrm{BCAD}$ | $\mathrm{CABD}$ | $(0,1/2,1/2,0)$ | $B$ |
| $1$ | $\mathrm{BCAD}$ | $\mathrm{DABC}$ | $(1/2,1/2,0,1/2)$ | $A$ |
| $2$ | $\mathrm{BDAC}$ | $\mathrm{DABC}$ | $(0,1/2,0,1/2)$ | $B$ |
| $3$ | $\mathrm{BDAC}$ | $\mathrm{CABD}$ | $(1/2,1/2,1/2,0)$ | $A$ |
The sequence is
$$ 0\longrightarrow 1\longrightarrow 2\longrightarrow 3\longrightarrow 0. $$
The table follows directly from counting the two ballots. For example, at state $0$, both ballots put $C$ above $A$, so $A$ has score $0$. Candidate $B$ has supports $1/2,1/2,1$ against $A,C,D$, respectively; candidate $C$ has supports $1,1/2,1$ against $A,B,D$. Thus $B$ and $C$ tie at $1/2$, and $B$ wins.
To verify legality:
Each move changes exactly one indivisible bloc ballot. State $0$ is truthful, so this is a reachable cycle.
Consequently, the minimum support size permitting a truthful cycle is two. For two blocs, four is the minimum candidate count permitting such a cycle. Appending additional candidates below $A,B,C,D$ in every displayed ballot and truthful ranking gives examples for every $m\ge4$.
The preceding two-bloc example uses score ties. The following construction shows that ties are not necessary.
Use four candidates with tie-break $A$ before $B$ before $C$ before $D$. Let the four bloc masses be $a,b,c,d$, where
$$ a,b,c,d>0, \qquad a+b+c+d=1, $$
and assume
$$ a<b, \qquad b+c-a<d<b+c. $$
These inequalities imply
$$ d>c, \qquad a+c<b+c<a+d, \qquad d<b+c. $$
Choose truthful rankings
$$ r_1=\mathrm{ABDC}, \qquad r_2=\mathrm{BDAC}, \qquad r_3=\mathrm{BADC}, \qquad r_4=\mathrm{DCAB}. $$
Blocs $1$ and $3$ retain their truthful ballots throughout the proposed sequence.
Consider five states, where state $0$ is truthful:
| State | Bloc $2$ | Bloc $4$ | $(P_\mu(A,B),P_\mu(A,C),P_\mu(A,D))$ | Score of $A$ | Winner |
|---|---|---|---|---|---|
| $0$ | $\mathrm{BDAC}$ | $\mathrm{DCAB}$ | $(a+d,a+b+c,a+c)$ | $a+c$ | $B$ |
| $1$ | $\mathrm{BDAC}$ | $\mathrm{CABD}$ | $(a+d,a+b+c,a+c+d)$ | $a+d$ | $A$ |
| $2$ | $\mathrm{BCAD}$ | $\mathrm{CABD}$ | $(a+d,a+c,1)$ | $a+c$ | $B$ |
| $3$ | $\mathrm{BCAD}$ | $\mathrm{DABC}$ | $(a+d,a+c+d,a+b+c)$ | $a+d$ | $A$ |
| $4$ | $\mathrm{BDAC}$ | $\mathrm{DABC}$ | $(a+d,1,a+c)$ | $a+c$ | $B$ |
The supports in the table are obtained by summing precisely the masses whose displayed ballots put $A$ above its opponent. The stated minima use $d>c$ and $d<b+c$.
At every displayed state, blocs $1$ and $4$ put $A$ above $B$, while blocs $2$ and $3$ put $B$ above $A$. Hence
$$ P_\mu(B,A)=b+c. $$
Moreover, blocs $1,2,3$ all put $B$ above both $C$ and $D$, so
$$ P_\mu(B,C)\ge a+b+c, \qquad P_\mu(B,D)\ge a+b+c. $$
Therefore $B$ has score exactly $b+c$.
The same three blocs put $B$ above $C$ and $D$, giving
$$ \operatorname{score}(C)\le P_\mu(C,B)\le d, \qquad \operatorname{score}(D)\le P_\mu(D,B)\le d. $$
Since $d<b+c$, neither $C$ nor $D$ can match $B$’s score. The strict inequalities
$$ a+c<b+c<a+d $$
now prove every winner in the table. Every displayed winner is unique.
Follow the sequence
$$ 0\longrightarrow1\longrightarrow2\longrightarrow3\longrightarrow4 \longrightarrow1. $$
The last four states form a cycle.
When bloc $4$ moves, the other ballots are $\mathrm{ABDC}$, $\mathrm{BADC}$, and either $\mathrm{BDAC}$ or $\mathrm{BCAD}$. For every replacement ballot of bloc $4$,
$$ \operatorname{score}(B)\ge b+c, $$
because the unchanged blocs already supply $b+c$ against $A$ and $a+b+c$ against $C,D$. Meanwhile,
$$ \operatorname{score}(C)\le d<b+c, \qquad \operatorname{score}(D)\le d<b+c. $$
Thus bloc $4$ cannot elect either $C$ or $D$. Its truthful ranking is $D\succ C\succ A\succ B$, so whenever $A$ is attainable, it is the best attainable winner. The table shows that its moves $0\to1$, $2\to3$, and $4\to1$ attain $A$ and strictly improve upon $B$.
Bloc $2$ makes moves $1\to2$ and $3\to4$. Both elect its truthful first choice $B$ instead of $A$, and therefore are strictly improving best responses.
This proves a reachable cycle under all the required move conditions.
Take
$$ (a,b,c,d)=\frac1{84}(13,17,23,31). $$
The conditions hold because
$$ 13<17, \qquad 17+23-13=27<31<40=17+23. $$
The winner scores along states $0,1,2,3,4$ are respectively
$$ \frac{40}{84},\quad \frac{44}{84},\quad \frac{40}{84},\quad \frac{44}{84},\quad \frac{40}{84}. $$
All $16$ subset sums of the integer weights are distinct. In increasing order, they are
$$ 0,\ 13,\ 17,\ 23,\ 30,\ 31,\ 36,\ 40,\ 44,\ 48,\ 53,\ 54,\ 61,\ 67,\ 71,\ 84. $$
Thus distinct sets of blocs have different total masses. In particular, no coalition has mass $1/2$.
The inequalities defining the construction are strict, so the same cycle persists under sufficiently small perturbations preserving positivity and total mass $1$. Distinctness of the finitely many coalition masses also persists under sufficiently small perturbations.
Therefore there is an open region of mass vectors exhibiting this cycle, with unique winners throughout and no equality between distinct coalition masses. Any proposed unrestricted convergence argument based solely on excluding such equalities would fail.
This section establishes the local oracle without enumerating all $m!$ ballots.
Write each mass as $\mu_t=a_t/d_t$, and set
$$ D=\prod_{t=1}^{\tau}d_t, \qquad v_t=D\mu_t. $$
Every $v_t$ is a positive integer, and
$$ \sum_t v_t=D. $$
The bit lengths of $D$ and each $v_t$ are $\mathrm{O}(L)$. Elementary integer arithmetic computes them in $\mathrm{O}(\tau L^2)$ bit operations.
Multiplying supports by $D$ multiplies all Maximin scores by $D$, preserving comparisons, ties, winners, and legal moves. Hence we may use integer weights.
Fix a bloc of weight $v$ and let
$$ Q(x,y)=\sum_{s\ne t:\,x\succ_{b_s}y}v_s $$
be the support supplied by all other blocs.
If a ballot elects $p$, raise $p$ to the first position while preserving the order of the remaining candidates.
Every support entering $p$’s score weakly increases. For each rival, its support against $p$ weakly decreases, while its supports against other rivals remain unchanged. Thus $p$’s score cannot decrease and no rival’s score can increase. All comparisons required by the fixed tie-break remain valid.
Consequently, $p$ is attainable if and only if it is attainable with $p$ first. This is an attainability argument; it does not restrict the ballots allowed in legal dynamics.
Let $R=C\setminus\{p\}$. When $p$ is first, its score is fixed at
$$ \sigma_p=\min_{y\in R}\bigl(Q(p,y)+v\bigr). $$
For $x\in R$, define the predicate
$$ G_p(x,z)= \begin{cases} z<\sigma_p,&\text{if }x\text{ is earlier than }p,\\ z\le \sigma_p,&\text{if }p\text{ is earlier than }x. \end{cases} $$
Candidate $p$ wins exactly when every rival $x$ has some opponent against whom its support satisfies this predicate.
Call $x$ a root if either
$$ G_p(x,Q(x,p)) $$
holds, or some $y\in R\setminus\{x\}$ satisfies
$$ G_p(x,Q(x,y)+v). $$
On vertex set $R$, insert an arc $y\to x$ whenever $x\ne y$ and
$$ G_p(x,Q(x,y)). $$
Lemma. Candidate $p$ is attainable if and only if every vertex is reachable from the root set.
Proof of sufficiency. Order the roots first, followed by the other vertices in nondecreasing shortest-path distance from the roots. Put this order after $p$.
For a root, its defining witness remains valid regardless of the remaining order: its support against $p$ is $Q(x,p)$, and its support against any rival $y$ is at most $Q(x,y)+v$. Both predicates are preserved when their numerical argument decreases.
For a nonroot $x$, choose a predecessor $y$ on a shortest path from the roots. Candidate $y$ is above $x$ in the ballot, so
$$ P(x,y)=Q(x,y). $$
The arc $y\to x$ supplies the required witness. Hence every rival loses to $p$ under the score comparison and tie-break. $\square$
Proof of necessity. Suppose a ballot with $p$ first elects $p$. If some vertices are unreachable from the roots, choose the highest such vertex $x$ in this ballot.
Because $p$ wins, there is an opponent $y$ satisfying $G_p(x,P(x,y))$.
If $y=p$, then $x$ is a root. If $x$ is above $y$, then
$$ P(x,y)=Q(x,y)+v, $$
which also makes $x$ a root. Both are contradictions.
Otherwise $y\in R$ is above $x$, and
$$ P(x,y)=Q(x,y). $$
There is therefore an arc $y\to x$. By the choice of $x$, the higher vertex $y$ is reachable, making $x$ reachable as well. This is the final contradiction. $\square$
For one proposed winner, constructing this graph and testing reachability takes $\mathrm{O}(m^2L)$ bit operations. Testing every candidate takes $\mathrm{O}(m^3L)$. The bloc’s best attainable winner is the truthfully highest candidate among those passing the test.
Including integer normalization and construction of the support matrix, one best-response computation takes
$$ \mathrm{O}\!\left( \tau L^2+(\tau m^2+m^3)L \right). $$
A proposed one-bloc replacement is legal exactly when its actual winner is strictly preferred to the current winner and equals the best attainable winner just computed. Thus legal-edge verification is polynomial-time computable.
Set
$$ q=m!, \qquad N=q^\tau. $$
There are exactly $N$ labelled ballot profiles. Each has at most $\tau(q-1)$ possible one-bloc replacements.
Enumerate all profiles and replacements, retain precisely the legal edges using the oracle above, and search the graph reachable from truthfulness for a directed cycle. The resulting running time is
$$ (m!)^{\tau+1}\operatorname{poly}(m,\tau,L). $$
This is an exact algorithm, but not a polynomial-time classification.
A profile has an encoding of length
$$ S=\tau m\lceil\log_2m\rceil, $$
and $\log_2N\le S$.
For profiles $u,v$, let $\operatorname{Reach}(u,v,k)$ mean that there is a directed walk of length at most $2^k$ from $u$ to $v$. At $k=0$, test equality or a legal edge. For $k>0$, enumerate all profiles $z$ and test
$$ \operatorname{Reach}(u,z,k-1) \quad\text{and}\quad \operatorname{Reach}(z,v,k-1). $$
This recurrence is correct: a walk of length at most $2^k$ can be split into two walks of length at most $2^{k-1}$, and conversely such walks concatenate. For a walk shorter than $2^{k-1}$, one part may be empty.
Every reachable vertex has a simple reaching path of length at most $N-1$, so $k=\lceil\log_2N\rceil$ suffices. The two recursive calls can be evaluated sequentially. Each level stores only a constant number of profiles and enumeration counters, and the depth is $\mathrm{O}(S)$. Thus the recursion uses $\mathrm{O}(S^2)$ space.
Enumerate legal edges $u\to v$ and accept if truthfulness reaches $u$ and $v$ reaches $u$. Acceptance gives a reachable nonempty closed walk, which contains a cycle. Conversely, a reachable directed cycle supplies such an edge.
Including the local oracle, this gives deterministic space
$$ \mathrm{O}\!\left( S^2+(\tau+m^2)L \right). $$
Hence the unrestricted problem belongs to $\mathrm{PSPACE}$.
Finally, infinite legal play and reachable-cycle existence are equivalent here. An infinite walk in a finite graph repeats a vertex. Conversely, a reachable cycle can be repeated indefinitely because legality depends only on the current profile and no fairness condition is imposed.
Let $k$ be the number of distinct masses, and again put $q=m!$.
Partition blocs into classes according to the pair consisting of their mass and truthful ranking. There are at most $kq$ classes. Let class $g$ contain $n_g$ blocs.
Represent a profile by counts $h_{g,b}$, recording the number of blocs in class $g$ submitting ballot $b$. They satisfy
$$ \sum_b h_{g,b}=n_g. $$
The number of count states is
$$ H=\prod_g\binom{n_g+q-1}{q-1} \le (\tau+1)^{kq(q-1)}. $$
The inequality follows because each class’s first $q-1$ counts determines its last count, and each of those counts has at most $\tau+1$ possible values.
A count move removes one bloc from a positive cell $(g,b)$ and places it in $(g,b')$. It changes one bloc of the original mass; it does not split that bloc.
Lemma. The count graph preserves existence of an infinite legal sequence from truthfulness.
Proof. Counts determine every pairwise support. For a bloc in cell $(g,b)$, subtracting its mass contribution under ballot $b$ determines the other blocs’ support matrix. Its truthful preferences are also determined by $g$. Therefore its best attainable winner and the legality of any replacement depend only on the count state and the source cell.
Every labelled legal move projects to a legal count move. Conversely, from any labelled representative of a count state, choose an actual bloc in the positive source cell of a legal count move. Changing its ballot realizes that count move, with exactly the same best-response test.
Thus every infinite labelled sequence projects to an infinite count sequence, and every infinite count sequence can be lifted step by step to an infinite labelled sequence. Finiteness gives the corresponding equivalence for reachable cycles. $\square$
Enumerating this graph and checking its edges takes
$$ (\tau+1)^{k(m!)(m!-1)} (m!)^{\mathrm{O}(1)} \operatorname{poly}(m,\tau,L) $$
time. This is polynomial in $\tau,L$ when both $m$ and $k$ are fixed.
The quotient preserves separate bloc controllers and all ballots attaining the best winner. It does not require a count cycle to return immediately to the same labelled profile.
The local move condition is polynomial-time decidable, but that alone does not bound the length or complexity of global reachability.
The two-bloc example shows that very small support does not guarantee convergence when all best-winner ballots are permitted. The four-bloc construction shows that unequal coalition masses and unique winners along a trajectory do not guarantee convergence either.
These results establish no unrestricted polynomial-time algorithm and no $\mathrm{NP}$-hardness reduction. In particular, the mass inequalities in the cycle construction are not a hardness reduction: they do not provide a legal preparation phase encoding arbitrary subset choices, nor do they exclude unintended reachable cycles in negative instances.
⟨structured verdict parsed — rendered above⟩
Result: partial. The structural results, best-response oracle, and upper bounds are correct as written. They do not resolve the requested unrestricted classification. The prover explicitly acknowledges this limitation, so there is no unsupported claim of having solved the main problem.
The only major issue is incomplete coverage of USER_TASK. I found no mathematical error or additional proof gap in the results actually claimed.
Section 1.1 is correct. The displayed inequalities establish that the first candidate in a bloc of mass greater than $1/2$ uniquely wins, independently of every other ballot.
The dynamical conclusions follow with the required best-response condition: only the dominant bloc can change the winner, and its best attainable winner is its truthful first choice. Thus truthfulness is terminal, and a sequence from an arbitrary profile has at most one legal move.
The specialization to two unequal positive masses is valid because their sum is $1$.
Lemma 1.2 correctly characterizes the attainable winners as exactly the candidates no later than the fixed ballot’s first candidate $q$.
Both directions are justified:
The conclusion about the best attainable winner uses the truthful ranking correctly and does not restrict which ballots attaining that winner are legal.
The three-candidate case analysis is exhaustive. The terminal cases cover a truthful first choice of $A$ and coincident truthful first choices. The remaining first choices are $B$ and $C$, and all four combinations of their truthful rankings are examined.
The ballot restrictions used in the nonterminal case are correct:
The resulting terminal-state argument is valid. An independent exhaustive check of all $36$ ordered truthful profiles with equal masses, allowing every ballot attaining the best winner, confirmed that the maximum legal-sequence length is $2$.
The two-candidate observation is also correct for any number of blocs: changing a truthful ballot can only reduce support for that bloc’s preferred candidate, so it cannot improve the winner.
All four score vectors in Section 1.4 are correct:
$$ (0,1/2,1/2,0),\qquad (1/2,1/2,0,1/2),\qquad (0,1/2,0,1/2),\qquad (1/2,1/2,1/2,0). $$
They give the stated winners $B,A,B,A$.
Every transition changes exactly one ballot. The moves by bloc $2$ attain its best available winner $A$ by Lemma 1.2; the moves by bloc $1$ attain its truthful first choice $B$. Each move strictly improves the moving bloc’s winner.
The cycle begins at truthfulness. The minimum-support and minimum-candidate conclusions follow from the preceding results. Appending candidates at the bottom preserves the displayed winners and best-response comparisons.
The stated implications of the mass conditions are correct:
$$ d>b+c-a>c, \qquad a+c<b+c<a+d, \qquad d<b+c. $$
All support triples for $A$ in Section 2.2 are correct, as are their stated minima.
At every displayed state, the unchanged contributions establish that $B$ has score exactly $b+c$. The bounds for $C$ and $D$ are valid because blocs $1,2,3$ all rank $B$ above both candidates. Consequently, the inequalities distinguish the claimed winner strictly at every state.
The argument for bloc $4$ holds for every replacement ballot, not just the displayed ones. With its other three ballots fixed, $B$ retains score at least $b+c$, while both $C$ and $D$ have score at most $d<b+c$. Thus bloc $4$ cannot elect either candidate it prefers to $A$.
Each displayed move by bloc $4$ therefore elects its best attainable winner $A$ and strictly improves upon $B$. Each move by bloc $2$ elects its truthful first choice $B$ and strictly improves upon $A$.
The sequence reaches state $1$ from truthfulness and then cycles through states $1,2,3,4$. The arbitrary scheduler permits the two other blocs to remain stationary; no fairness assumption is needed.
For the masses $(13,17,23,31)/84$, independently recomputed complete score vectors are:
| State | Scores in order $(A,B,C,D)$ |
|---|---|
| $0$ | $(36,40,0,31)/84$ |
| $1$ | $(44,40,31,0)/84$ |
| $2$ | $(36,40,31,0)/84$ |
| $3$ | $(44,40,0,31)/84$ |
| $4$ | $(36,40,0,31)/84$ |
These confirm the stated unique winners and winning scores. Exhaustive enumeration of replacement ballots also confirms every displayed best response.
The list of $16$ subset sums is correct and contains no repetitions. In particular, it excludes $42$, so no coalition has mass $1/2$.
The perturbation conclusion is justified by finitely many strict inequalities and nonzero differences between subset sums. The open region is understood relative to the simplex of positive masses summing to $1$, as the prover’s wording explicitly indicates. Rational instances in that region satisfy the input requirements.
The normalization is valid. The product $D$ has bit length $\mathrm{O}(L)$; each $v_t=D\mu_t$ is a positive integer with the same bit-length bound. Multiplication by the common positive factor preserves scores, ties, winners, and legality.
The stated normalization time is a valid upper bound using elementary integer arithmetic.
The monotonicity argument is correct. Raising $p$ weakly increases its score and weakly decreases every rival’s score. This preserves both strict comparisons against earlier candidates and weak comparisons against later candidates.
The prover correctly uses this only for attainability, while retaining all ballots attaining the best winner in the dynamics.
The predicate $G_p$ correctly distinguishes rivals earlier and later than $p$. Its strictness agrees with the fixed tie-break.
Both directions of the reachability lemma are valid:
The argument handles an empty root set and the case $m=2$ without an omitted exception.
The graph construction, reachability test, and candidate enumeration support the stated running time
$$ \mathrm{O}\!\left(\tau L^2+(\tau m^2+m^3)L\right). $$
The resulting test for a proposed legal edge correctly checks both strict improvement and best attainability.
The labelled state count $(m!)^\tau$ and replacement bound $\tau(m!-1)$ are correct. Explicit graph construction and cycle detection give the stated exponential-time upper bound.
The polynomial-space reachability recurrence is correct for walks of length at most $2^k$, including empty walks. A depth of $\lceil\log_2 N\rceil$ suffices for simple reaching paths. Sequential recursive evaluation requires only polynomial space.
The acceptance condition—an edge $u\to v$ with truthfulness reaching $u$ and $v$ reaching $u$—correctly characterizes a reachable nonempty closed walk and hence a reachable cycle. The stated total space bound
$$ \mathrm{O}\!\left(S^2+(\tau+m^2)L\right) $$
is consistent with the profile storage and local oracle.
Thus the $\mathrm{PSPACE}$ membership result is established. The equivalence between infinite legal play and reachable-cycle existence is also correctly justified.
The partition by mass and truthful ranking is valid despite distinct delegate identities: within a class, the written model gives identical preferences and voting weights.
The count-state formula and bound are correct:
$$ H=\prod_g\binom{n_g+q-1}{q-1} \le(\tau+1)^{kq(q-1)}. $$
The quotient lemma verifies both directions. Counts determine the support matrix and the legality of a move from any positive source cell. Every labelled move projects, and every count move can be realized from any labelled representative.
This establishes equivalence of infinite-sequence existence. The prover correctly avoids claiming that a count cycle must immediately restore the same labelled profile.
The graph-enumeration bound is polynomial in $\tau,L$ when both $m$ and $k$ are fixed. It does not extend to unrestricted inputs.
Major issue — the requested classification remains unresolved. None of the valid results establishes an unrestricted polynomial-time algorithm or an $\mathrm{NP}$-hardness result.
The polynomial local oracle does not itself classify global reachability. The fixed-parameter enumeration bound does not yield an unrestricted polynomial bound. The cycle constructions establish existence of cycles, but contain no reduction deciding an arbitrary hard input.
To complete the assignment, the prover must supply either an unrestricted polynomial-time decision algorithm with correctness and running-time proofs, or an appropriate polynomial-time hardness reduction with both directions verified under the exact legal-move definition. This requires additional mathematics; expositional clarification alone cannot settle the task.
⟨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.