6

Let the set of alternatives be $\left\{a,b,c,d\right\}$.

Let there be $n$ types of voter profiles, each type with a different strict ordering over the set of alternatives.

The number of voters belonging to the profile types need not be the same, let us denote these by $v_1,v_2,...,v_n$.

What is the minimal number of $n$, for which you can construct the voter profiles in such a way that the plurality rule (a.k.a. first-past-the-post), simple run-off (election with two rounds) rule, elimination rule and the Borda count all yield different outcomes? (Assume non-strategic voters. Outcomes should not be ties.)

EDIT:
Plurality rule has one round of voting and whoever has the most votes wins.
Example: United Kingdom parliamentary elections

The simple run-off rule has two rounds of voting. The two candidates with the most votes in round 1 advance to round 2. In round 2 voters vote for their favourite remaining candidate, and whoever has the most votes wins.
Example: French presidential election

The elimination rule is similar to the run-off rule but has three rounds (number of alternatives minus one). In each round the candidate with the least votes is eliminated (figuratively). Others proceed to the next round.
Example: Academy award (Oscar) vote

Minimalist guesses ("here are some profiles with $n = 4$") are fine, ideal solution would provide a proof that $n$ is minimal.

Giskard
  • 29,387
  • 11
  • 45
  • 76

2 Answers2

3

First, let me state that this is a beautiful problem!

Here is a proof that $n=4$. To prove that $n \leq 4$, consider the following example:

  • $m+4$ voters have preference $a \succ d \succ b \succ c$
  • $m+3$ voters have preference $b \succ d \succ c \succ a$
  • $m+2$ voters have preference $c \succ d \succ b \succ a$
  • $m$ voters have preference $d \succ c \succ a \succ b$

where $m \geq 2$. I leave it to you to check that $a$ is selected by the plurality rule, $b$ by the simple run-off, $c$ by the elimination rule and $d$ by the Borda procedure.

Now, let us prove that $n>3$. The cases $n=1$ and $n=2$ are trivial, so let us assume $n=3$ and write $v_1,v_2,v_3$ for the number of voters in the three voter profiles. Without loss of generality, let us assume that $v_1 \geq v_2 \geq v_3$, that $a$ is selected by the plurality rule, that $b$ is selected by the run-off election, that $c$ is selected by the elimination rule and that $d$ is selected by the Borda count.

The outcome of the plurality rule shows that $a$ is most preferred by voters of group 1 (since it wins with no ties). If $a$ were also preferred by voters of group 2, $a$ would win the run-off election, which is a contradiction. Thus $a$ is most preferred by voters of group 1, $b$ is most preferred by voters of group 2, and $v_1>v_2 \geq v_3$, the latter inequality being strict if $b$ is not most preferred by voters of group 3. But then it is clear that both $a$ and $b$ survive the first two rounds of the elimination rule, i.e. that $c$ and $d$ are eliminated, which is a contradiction.

Oliv
  • 3,232
  • 11
  • 25
2

This is not mathematically rigorous but I believe the reasoning is correct.

We assume that the allocation of votes between voter types is such that ties are not allowed, where it matters. Also, obviously, the minimal number of voter types cannot be one. So we need at least two voter types.

Given absence of ties, in the Plurality system, it must be the case that there exists a pair of first-second candidates, say $\{a,b\}$. Without loss of generality assume that in Plurality, $a$ wins.

Now, it is certain that $\{a,b\}$ will also be the candidate pair in the second round of Simple Run Off, if it is so for the Plurality regime. To obtain a different outcome here, we need a third voter type, that will support $b$ even though it was not its first-preference (and a suitable allocation of votes between types). So we conclude that $n_{min} \geq 3$.

Consider now the Elimination system. In the first round the fourth in votes candidate will be eliminated, say $d$. In the second round, we will have three candidates. And voting must be such that the final pair of candidates is not $\{a,b\}$ (because both have won in the other two systems). So we must eliminate either $b$ or $a$ and so get either $\{a,c\}$ or $\{b,c\}$, and in both cases, $c$ must win. Is this possible with three voter types?

No. Since voters vote strictly by preference ordering and not strategically, each of the three voter types will vote for its first-preference. Then, with only three voter types, we will necessarily get as a final pair $\{a,b\}$, which we do not want. So we conclude that we need at least a fourth voter type, so $n_{min} \geq 4$.

And indeed, we do not need more than that. Consider

$$v_1:\; \{a,d,c,b\}$$ $$v_2:\; \{b,d,c,a\}$$ $$v_3:\; \{c,d,b,a\}$$ $$v_4:\; \{d,c,b,a\}$$

with

$$v_1>v_2>v_3>v_4$$ $$v_2+v_3> v_1 $$ $$v_3+v_4> v_2 $$

The first inequality makes $a$ win Plurality, and gives final pair $\{a,b\}$ in Plurality and Simple Run off. The second inequality is enough to make $b$ win Simple-Run Off.

In the Elimination system, due to first inequality $d$ goes out first. Then the third inequality makes $b$ be eliminated second, and we are left with the final pair $\{a,c\}$. Then the second inequality again is enough to make $c$ the winner here ($v_4$ will also vote for $c$).

As for the Borda Count, consider $v_1=10, v_2=9, v_3=8, v_4=7$. $d$ will win with $109$ points.

Alecos Papadopoulos
  • 33,814
  • 1
  • 48
  • 116