Single Transferable Vote (COMSOC)

comsoc

Definition

Single Transferable Vote

In COMSOC, Single Transferable Vote is an elimination-based voting rule that repeatedly removes an alternative with the lowest current plurality score until only one alternative remains. It is also called the Hare system or instant runoff.

Let $C$ be a set of alternatives and let

$$R:=({\succ }_1,\dots ,{\succ }_n)$$

be a preference profile. Starting with the active set $A_0:=C$, each round computes plurality scores restricted to the active alternatives. An active alternative with minimum restricted plurality score is eliminated. The last remaining alternative is the STV winner.

If several active alternatives have the same minimum plurality score in an elimination round, a tie-breaking convention is needed unless the rule is treated as an irresolute rule.

Mechanism

Iterated elimination

STV uses the following procedure:

1. Count each voter’s highest-ranked active alternative.
2. Eliminate an alternative with the lowest plurality score.
3. Transfer the affected voters to their next highest-ranked active alternative.
4. Repeat until one alternative remains.

Example

Course profile

In the lecture profile, the initial plurality scores are

$$A:30,B:18,C:28,D:24.$$

The STV elimination proceeds as follows:

round	active alternatives	restricted plurality scores	eliminated alternative
$1$	$A,B,C,D$	$A:30,B:18,C:28,D:24$	$B$
$2$	$A,C,D$	$A:30,C:28,D:42$	$C$
$3$	$A,D$	$A:58,D:42$	$D$

After $D$ is eliminated, only $A$ remains. Thus $A$ is the unique STV winner.

Properties

Transfers votes after elimination

STV uses more of each ranking than ordinary Plurality. When a voter’s current favourite active alternative is eliminated, their vote transfers to the next active alternative in their ranking.

Committee variant

The lecture notes state that STV can also be used for electing a committee of multiple winners.

Non-monotonicity

STV is not monotone: ranking a winner higher can make that alternative lose.

Polynomial-time winner determination

To determine whether a given alternative $c^{\ast }\in C$ is an STV winner, simulate the elimination rounds and compare the result with $c^{\ast }$.

Thus STV winner determination is solvable in polynomial time.