Single Transferable Vote (COMSOC)

Definition

Single Transferable Vote ( COMSOC)

In COMSOC, the single-winner version of STV is a voting rule that repeatedly eliminates an alternative with the lowest current plurality score. For a profile $R$ over a non-empty set of alternatives $C$, start with

$$S_0=C$$

and repeat while $|S_t|>1$:

$$\begin{array}{rl}{s}_t(x)& :=|\{i:x\text{ is highest in voter }i\text{’s ranking among }{S}_t\}|,\\ & \\ e_t& \in \arg \underset{x\in S_t}{\min }{s}_t(x),\\ & \\ S_{t+1}& :=S_t\setminus \{e_t\}.\end{array}$$

The last remaining alternative wins. Each voter supports their highest-ranked remaining alternative; their ranking does not change. Specify a tie-breaking rule when several alternatives share the lowest score. This single-winner procedure is also called instant-runoff voting or the Hare system.

Intuition

Plurality counts first choices; STV also uses the fallback choices already recorded on each ranked ballot. Let $n$ be the number of voters, each submitting one ballot. With complete, strict rankings, let $h_i(S_t)$ be voter $i$‘s highest-ranked remaining alternative. Then

$$\begin{array}{rl}{s}_t(x)& =|\{i\in \{1,\dots ,n\}:h_i(S_t)=x\}|,\\ \sum _{x\in S_t}{s}_t(x)& =\underset{\text{every ballot counts exactly once}}{\underbrace{n}}.\end{array}$$

The rule chooses to eliminate the least-supported alternative $e_t$; the invariant determines what happens to its ballots:

$$h_i(S_{t+1})=\{\begin{array}{ll}{h}_i(S_t),& h_i(S_t)\ne e_t,\\ \text{next remaining alternative in }{\succ }_i,& h_i(S_t)=e_t.\end{array}$$

Only $e_t$‘s ballots move; rankings stay fixed. For example, removing $B$ transfers its 18 votes to $D$, without losing or creating votes:

$$\underset{\text{before removing }B}{\underbrace{\text{overbracket}{30}^A+\text{overbracket}{18}^B+\text{overbracket}{28}^C+\text{overbracket}{24}^D}}=\underset{\text{after removing }B}{\underbrace{\text{overbracket}{30}^A+\text{overbracket}{28}^C+\text{overbracket}{(24+18)}^{D^{\prime }=B+D}}}=100.$$

Recount after each transfer. Across rounds,

$$\underset{\text{one fewer alternative}}{\underbrace{|S_{t+1}|=|S_t|-1}},\underset{\text{same number of votes}}{\underbrace{\sum _{x\in S_{t+1}}{s}_{t+1}(x)=n}}.$$

After $m-1$ eliminations, one alternative remains. Preserving each ballot’s best remaining choice does not guarantee that raising a candidate helps them; see non-monotonicity below.

Transfers Without Changing Votes

When a voter’s current choice is eliminated, their vote counts for the next alternative still present in their original ranking. Unlike strategic voting, this requires no false report: the rule itself transfers the vote after elimination.

Committee Elections and Use

Multi-winner STV also elects committees, but uses election quotas and transfers of surplus votes as well as eliminations; it is not simply the procedure above stopped with several candidates left. STV is used in Irish public elections, some Canadian municipal elections and Australian Senate elections. Australian House of Representatives elections use the single-winner preferential system.

Winner Determination

Winner determination asks: given the submitted ballots, how much work does it take to compute who wins? The ballots are fixed; we are not searching for strategic votes.

Let $n$ be the number of voters and $m$ the number of alternatives. Store which alternatives remain active. In each round:

1. Scan each ballot from the top until finding an active alternative; give that alternative one point.
2. Find the smallest score and eliminate one alternative with that score.

A simple implementation may inspect all $m$ positions on each of the $n$ ballots. It needs at most $m-1$ rounds because each round removes one alternative:

$$\underset{\text{ballots}}{\underbrace{n}}\cdot \underset{\text{positions per ballot}}{\underbrace{m}}\cdot \underset{\text{elimination rounds}}{\underbrace{(m-1)}}=O(n{m}^2).$$

Resetting the scores and finding their minimum adds only $O(m)$ work per round. Thus this implementation runs in polynomial time on explicitly listed rankings; the bound is an upper bound, not a claim that every position must always be read.

Fix a tie-breaking order in advance, such as alphabetical order among tied candidates. This makes each elimination unambiguous and cheap to compute. Asking who could win under any possible tie-breaking choices is a different task: one simulation follows only one sequence of eliminations.

Issues

Condorcet-inconsistency

In the 100-voter example below, $C$ is the Condorcet winner:

$$\begin{array}{rl}{N}_R(C,A)& =18+28+24=70,\\ N_R(C,B)& =28+24=52,\\ N_R(C,D)& =30+28=58.\end{array}$$

All three counts exceed $n/2=100/2=50$.

Nevertheless, STV first eliminates $B$ and transfers its 18 votes to $D$. The active scores become

$$(A,C,D)=(30,28,42).$$

It now eliminates $C$ for having the lowest current score, even though $C$ would defeat either remaining opponent head-to-head. Its 28 votes transfer to $A$, which wins $58:42$ against $D$.

STV’s elimination criterion counts current first choices, not pairwise victories. It can therefore remove the Condorcet winner and is not Condorcet consistent. No tie-breaking is involved here.

Non-monotonicity

Raising a winner in some voters’ rankings, without changing the relative order of other alternatives, can make that winner lose. The increased first-place support can change the elimination order and subsequent transfers. The following 17-voter profile shows this failure; no elimination tie-breaking is needed.

Example

The same 100-voter profile

Each row groups voters with the same complete ranking. The plurality diagram shows the initial scores; its result is not yet the STV computation.

Eliminate $B$: its 18 voters have $B\succ D\succ C\succ A$. Their next remaining choice is $D$:

$$(A,C,D)=(30,28,\underset{42}{\underbrace{24+18}}).$$

Eliminate $C$: its 28 voters have $C\succ B\succ A\succ D$. Since $B$ is already gone, skip it and transfer to $A$:

$$(A,D)=(\underset{58}{\underbrace{30+28}},42).$$

Eliminate $D$: $42<58$, so only $A$ remains and wins. No tie-breaking is needed in this profile.