Failures of Instant Runoff Voting

I have always thought that Australia has had a perfect electoral system, at least for the House of Representatives. Compulsory ranked voting with instant run-off? What’s not to like?! The electorate is forced to show up once every four years and have their say, and no-one’s vote is wasted, or so I thought. I was recently made aware of two theorems in social decision theory, Arrow’s Theorem, and the Gibbard-Satterthwaite Theorem, that have made me more uneasy about our voting system, and voting systems in general.

Arrow’s Theorem

Arrow’s Theorem, or Arrow’s Impossibility Theorem, is stated as follows (Taken from here):

Let A be a set of outcomes, along with a process which aggregates individual’s preferences into a single preference order on A.

Whenever A has more than two outcomes, then at least one of the following must not hold:

  • (Weak Pareto Efficiency) If alternative a is ranked higher than alternative b for all individuals, then a is aggregately ranked strictly higher than b.
  • (Non-dictatorial) There is no individual such that that individual’s strict preferences always prevails.
  • (Independence of irrelevant alternatives) The social preference between x and y should only depend on the pairwise individual ordering of x and y. For example, adding a third candidate to the election should not affect the winner unless the third candidate wins.

Clearly having a non-dictatorial system is extremely important, though one could critique the power our media institutions have in choosing the winner of an election, and Weak Pareto Efficiency is also important. However, this usually means that an electoral system will fulfil these two properties, which means that the third property is usually unfulfilled. This means that in Instant Runoff Voting, we have situations where it may be advantageous to us to not enter our true preferences on the ballot. What type of situations could this occur in?

An Example

Well, let’s consider a scenario where we have the following first preference polling numbers:

Greens: 33% (33% Labor)

Labor: 30% (14% Liberal, 16% Greens)

Liberal: 37%

Suppose your favoured party is The Greens, followed by Labor, and then Liberal. Suppose also that you know that the preference distributions is as above. In the run-off, Labor will be eliminated, and the preferences allocated as follows:

Greens: 49%

Liberal: 51% (Winner)

and we have ended up with our least favoured outcome.

However, if instead 3% of Greens voters put Labor as their first preference instead, we get:

Greens: 30% (30% Labor)

Labor: 33% (14% Liberal, 19% Greens)

Liberal: 37%

and now The Greens will be eliminated, and the final results will be:

Labor: 63% (Winner)

Liberal: 37%

and we have ended up with our second choice by a landslide.

So in what situation will this come about? Well, as we can see above, it will happen when we have an extremely close election between three or more parties, and the preferences of the centre party are not sufficient to elect the minor party. It may be tactical then for the Greens voter to instead put Labor as their first preference.

You can see, however, that this requires detailed knowledge of both the first preference votes and the preference run-offs for each party, which is rarely the case. In the absence of such information, I would conjecture that it is a dominant strategy to put in one’s truthful preferences.

Alternative Voting Mechanisms

The previous section had me thinking, is there a way to bypass Arrow’s Theorem? It only holds for ranked choice ballots, right? Well, there are a plethora of other ways to vote! See Cardinal Voting among others, which does not use a ranked system, and therefore sidesteps Arrow’s Theorem. However, there exists a much more general theorem, the Gibbard-Satterthwaite Theorem, which says that for any voting mechanism, one of the following must hold:

  • There are only two alternatives,
  • (Non-dictatorial) There is no individual such that that individual can choose the winner,
  • (Existence of Tactical Voting) There is no action which best defends the individual’s desired outcome in every situation.

So it can be seen that there is no voting system which will satisfy all three of these simultaneously, and to me, that is a little bit troubling.

Voting photo taken from here.

 

 

Advertisements

Magic Squares (Part 1)

I was watching an episode of Penn and Teller Fool Us with my parents, if you haven’t watched this show, you really should. It’s extremely entertaining, though my girlfriend gets very upset that the show doesn’t tell you exactly how the trick is done.

In this episode, a magician by the name of Amazing Allison does a trick involving a magic square – you can see it here. When I saw it, I immediately wanted to know how it was done using mathematics.

A brief set-up: someone is asked for a number between 25 and 99, and then the performer creates a magic square, such that the rows and columns add up to the target number, and in addition a whole lot of other things add up to the target number, including the diagonals, each square of 4, etc. In my mind, there must be a formula for this, so I set out to find it.

Let us briefly consider a trivial solution: Suppose my target number is y, then a trivial solution for an n \times n magic square is for all entries to equal \frac{y}{n}. Of course, this is not a very interesting magic square, and quite easy to make! So let us improve this slightly by introducing a free variable – so now we have a target number y, and we fill in one box with our free variable x. The question is now, how will we find the remainder of our entries? Mathematically, this requires us to find n^{2} - 1 linearly independent conditions upon the entries of the square, then we chuck it into a matrix and find the reduced row echelon form, and whaboom we’re done. Easy, right? I tried this using a 4\times 4 magic square and it was surprisingly hard to find 15 linearly independent conditions! Here were all the conditions I added:

  1. All rows and columns must add to y
  2. Each diagonal must add to y
  3. The corners must add to y
  4. Each square of 4 blocks must add to y
  5. Each combination of non-corner exterior squares must add to y
  6. Diagonal alternating patterns through the square from top-down must add to y

and I was finally able to hit rank 15! The square yielded was as follows:

ScreenClip

Now, this is a good start, but looking at it, it still isn’t very interesting!

Going forward there are a couple of conditions that we should impose on this, firstly that each entry should be positive and integer. This will admit a trivial solution only in the case where y is divisible by 4. It may be better suited to a linear programming style problem, however, due to the integrality constraints. This will be further explored in part 2.

 

Partial Scoring for Multiple Choice Tests

I read some time ago an article by Terence Tao on how to assign partial credit scores for multiple choice tests – the article can be found here.

Terence’s solution focused on True/False questions, but could be easily generalized to multiple choice questions, but involved as part of the solution giving negative marks to students, including negative infinity marks. Clearly this is an infeasible solution for the classroom, and one wonders if there is a function f:[0,1] \to [0,1] such that f(0)=0 and f(1)=1 which satisfy similar conditions as those outlined in the article. The main condition that needs to be satisfied is that the students expected score should be maximised at their subjective probability of the particular answer being correct.

We can use some of Terence’s work here, to cheat slightly. Let us institute a rule that a person cannot bid 1 or 0 for a particular answer, and secondly that they can only bid a value q\in\{0.01,0.02,...,0.99\}. Now, we can use the form f(p)=Alog(p)+B with the constraints that f(0.99)=1 and f(0.01)=0. This yields the equation f(p) = 0.2176log(p) + 1.0022.

Let us check the required conditions:

f(0.01)=0: f(0.01)=0.2176\times log(0.01) + 1.0022 = 0

f(0.99)=1: f(0.99)=0.2176\times log(0.99) + 1.0022=1

E[mark] = p(0.2176log(q)+1.0022)+(1-p)(0.2176log(1-q)+1.0022)

\frac{\partial E[mark]}{\partial q}=0.2176\frac{p}{q}-0.2176\frac{1-p}{1-q}=0 so that the expected mark is maximised when p=q.

So we have found a function which practically maps to [0,1], with the minor caveat that a student can never pick either 0 nor 1 for their answer.

There is, however, a large flaw with this function, which is a student can lock in a score of 87% simply by choosing 0.5 for both options. Clearly further work is required here!