Background: I will below describe a generalization of the following voting systems (what is meant by “voting system” will be defined formally below) which are occasionally used in the real world:
“First-past-the-post” (FPTP, denoted $S_0$ below): the candidate with the most votes wins.
“Instant runoff” (IRV, denoted $S_1$ below): in the first round, the candidate with the least votes is removed, and all votes for that candidate are transferred to the next most favored candidate for each elector, and the procedure of elimination is repeated until only one candidate remains, who is then elected.
Note that we can also define “dual” systems (not used in the real world AFAICT, but imaginable and will help explain the general scheme described below):
Dual FPTP ($S'_0$ below): voters vote against a candidate, and the candidate with the fewest votes against them wins.
Dual IRV ($S'_1$ below): voters vote against a candidate, in the first round the candidate with the most votes against them is removed and all votes against that candidate are transferred to the next least favored candidate for each elector, and the procedure of elimination is repeated until only one candidate remains, who is then elected.
The idea is to generalize the procedure by which $S_1$ can be defined from $S'_0$ and $S'_1$ from $S_0$.
Notations/definitions: Let $N\geq 1$ be an integer; let $\mathcal{T}$ be the set of total orders on $\{1,\ldots,n\}$ and $\Delta_{\mathcal{T}}$ the set of probability distributions on $\mathcal{T}$ (which we can see as a simplex of dimension $N!-1$).
By a (ranked) voting system I mean a partially defined function $s$ on $\Delta_{\mathcal{T}}$ with values in $\{1,\ldots,N\}$; so $s$ takes the distribution of preferences of all electors and outputs the person elected. Of course we might demand a lot of additional conditions on $s$, but those considered below will be piecewise constant in the sense that there exist finitely many hyperplanes in $\Delta_{\mathcal{T}}$ such that $s$ is constant on each piece of the complement of these hyperplanes, and possibly undefined on the hyperplanes themselves (because they are defined by comparing votes for candidates $i$ and $j$ after various eliminations, and for simplicity we ignore or rule out the case where $i$ and $j$ have exactly the same number of votes).
Now the voting systems $(S_k)_{k\in\mathbb{N}}$ and $(S'_k)_{k\in\mathbb{N}}$ are defined (for all $N$ simultaneously) by induction on $k$ as follows:
$S_0$ and $S'_0$ are as described above; namely: $S_0(p)$ is the unique $i \in \{1,\ldots,N\}$ such that $p$ gives the greatest probability to the event “$i$ is the greatest element in the total order” (and undefined if there is no unique such $i$) and $S'_0(p)$ is the unique $i$ such that $p$ gives the smallest probability to the event “$i$ is the smallest element in the total order”.
If $S_k$ and $S'_k$ are defined, $S_{k+1}$ and $S'_{k+1}$ are defined as follows. To determine $S_{k+1}(p)$, first compute $i_1 := S'_k(\hat p)$ (the first candidate eliminated) where $\hat p$ is obtained from $p$ by reversing the total order (i.e., $\hat p(t) = p(\hat t)$ for $t\in\mathcal{T}$ where $\hat t$ is the total order on $\{1,\ldots,N\}$ which reverses that of $t$), then let $p_1$ be the probability distribution on total orders on $\{1,\ldots,N\}\setminus\{i_1\}$ obtained by deleting $i_1$ from the list of candidates (i.e., $p_1(t) = \sum_{u} p(u)$ where $u$ ranges over all total orders on $\{1,\ldots,N\}$ which restrict to the total order $t$ on $\{1,\ldots,N\}\setminus\{i_1\}$), then let $i_2 := S'_k(\widehat{p_1})$ with the obvious abuse of notation, and so on: then let $S_{k+1}(p) = i_N$ (the last candidate elimiated). Naturally, if any $i_j$ is undefined, the procedure stops and $S_{k+1}(p)$ is left undefined. And $S'_{k+1}$ is defined from $S_k$ in exactly the same way as $S_{k+1}$ is from $S'_k$.
In more informal terms, $S_{k+1}$ eliminates the least favored candidates one by one, where “least favored” is defined by applying $S'_k$ to the reverse order of preference, until only one is left, who is then elected; and symmetrically, $S'_{k+1}$ is defined by applying $S_k$ to the reverse order of preference.
Question: is it true that for all $p \in \Delta_{\mathcal{T}}$, outside of countably many hyperplanes, the sequence $(S_k(p))_{k\in \mathbb{N}}$ eventually stabilizes? If so, what is a bound (in function of $N$) on the smallest $k$ such that this happens. If not, is $(S_k(p))$ at least eventually periodic? If so, what are bounds on its preperiod and period?
