After reading the post titled "How to become the next Government of Singapore?" at http://dontneedsex.blogspot.com/2013/05/how-to-become-next-government-of.html, I noticed some discrepancies (Holland-Bukit Timah is 4 seats instead of 5, Ang Mo Kio is 6 seats instead of 5) and some potential flaws with his approach. So I have decided to do the calculations by myself as well.
Flaws with Current Approach
The flaw with the current approach taken by Donaldson Tan is:
- Assumption that 44 seat will get the minimum votes - Depending on GRC make-up, there is a possibility that 45 or 46 seats might "cost" less votes than 44 seats.
Data
I pulled the electorate numbers from (http://en.wikipedia.org/wiki/Constituencies_of_Singapore), taking the Election column.
Method
I have used two methods to check for the minimum amount of votes needed:
- Brute Force (with Backtracking) - Brute force of whole solution space to find the global minimum
- Mathematical Approach - Voters needed per seat
Method 1 - Brute Force
I put in all the data of the voters and seats of each SMC/GRC and wrote a generate and test brute force algorithm to test ALL possible combinations (from only one constituency selected to all constituencies selected) and retrieve the global minimum. This is a very inefficient method (because it has to test the whole solution space) but as our input is small, and we are not looking to scale the solution, this will suffice.
The code I used is as follows:
public class Constituency {
public String name;
public int voters;
public int seats;
public Constituency(String name,int seats, int voters ){
this.name = name;
this.voters = voters;
this.seats = seats;
}
public int getMinVotesNeeded(){
return (int)Math.ceil((double)voters / 2.0);
}
@Override
public String toString(){
return name + " : " + seats + " seats : " + getMinVotesNeeded() + " votes.";
}
}
public class MinVotes {
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
ArrayList<Constituency> constituencies = new ArrayList<Constituency>();
constituencies.add(new Constituency("Aljunied Group Representation Constituency", 5, 143024));
constituencies.add(new Constituency("Ang Mo Kio Group Representation Constituency", 6, 178933));
constituencies.add(new Constituency("Bishan-Toa Payoh Group Representation Constituency", 5, 122416));
constituencies.add(new Constituency("Chua Chu Kang Group Representation Constituency", 5, 158552));
constituencies.add(new Constituency("East Coast Group Representation Constituency", 5, 120207));
constituencies.add(new Constituency("Holland-Bukit Timah Group Representation Constituency", 4, 91559));
constituencies.add(new Constituency("Jurong Group Representation Constituency", 5, 125214));
constituencies.add(new Constituency("Marine Parade Group Representation Constituency", 5, 154340));
constituencies.add(new Constituency("Moulmein-Kallang Group Representation Constituency", 4, 87498));
constituencies.add(new Constituency("Nee Soon Group Representation Constituency", 5, 148168));
constituencies.add(new Constituency("Pasir Ris-Punggol Group Representation Constituency", 6, 168834));
constituencies.add(new Constituency("Sembawang Group Representation Constituency", 5, 142351));
constituencies.add(new Constituency("Tampines Group Representation Constituency", 5, 137437));
constituencies.add(new Constituency("Tanjong Pagar Group Representation Constituency", 5, 139638));
constituencies.add(new Constituency("West Coast Group Representation Constituency", 5, 120956));
constituencies.add(new Constituency("Bukit Panjang Single Member Constituency", 1, 33035));
constituencies.add(new Constituency("Hong Kah North Single Member Constituency", 1, 27691));
constituencies.add(new Constituency("Hougang Single Member Constituency", 1, 24532));
constituencies.add(new Constituency("Joo Chiat Single Member Constituency", 1, 22027));
constituencies.add(new Constituency("Mountbatten Single Member Constituency", 1, 23712));
constituencies.add(new Constituency("Pioneer Single Member Constituency", 1, 25732));
constituencies.add(new Constituency("Potong Pasir Single Member Constituency", 1, 17306));
constituencies.add(new Constituency("Punggol East Single Member Constituency", 1, 33261));
constituencies.add(new Constituency("Radin Mas Single Member Constituency", 1, 31001));
constituencies.add(new Constituency("Sengkang West Single Member Constituency", 1, 26869));
constituencies.add(new Constituency("Whampoa Single Member Constituency", 1, 21615));
constituencies.add(new Constituency("Yuhua Single Member Constituency", 1, 23183));
int TOTAL_CONSTITUENCIES = 27;
int SEATS_MIN_NEEDED = 44;
int currBitArray = 1;
int endstate = (int)Math.pow(2,TOTAL_CONSTITUENCIES+1) ;
int currWinningPattern = 0;
int currWinningVotes = (int)Math.pow(2, TOTAL_CONSTITUENCIES+1);
while(currBitArray < endstate){
int totalVotes = 0;
int totalSeats = 0;
innerLoop : for(int i=0; i<TOTAL_CONSTITUENCIES; i++){
if(isBitSet(currBitArray, i)){
totalVotes += constituencies.get(i).getMinVotesNeeded();
totalSeats += constituencies.get(i).seats;
if(totalVotes > currWinningVotes) break innerLoop; //if we can't beat best so far, exit
}
}
if(totalSeats >= SEATS_MIN_NEEDED && currWinningVotes > totalVotes){
currWinningPattern = currBitArray;
currWinningVotes = totalVotes;
}
currBitArray ++;
}
System.out.println("Lowest votes needed : " + currWinningVotes);
System.out.println("Constituencies: ");
for(int i=0; i<TOTAL_CONSTITUENCIES; i++){
if(isBitSet(currWinningPattern, i)){
System.out.println(constituencies.get(i).toString());
}
}
}
public static boolean isBitSet(int decimal, int N){
if ((decimal & (1 << N)) != 0)
{
return true;
}
return false;
}
}
It has given me the following output:
Lowest votes needed : 538653
Constituencies:
Bishan-Toa Payoh Group Representation Constituency : 5 seats : 61208 votes.
East Coast Group Representation Constituency : 5 seats : 60104 votes.
Holland-Bukit Timah Group Representation Constituency : 4 seats : 45780 votes.
Jurong Group Representation Constituency : 5 seats : 62607 votes.
Moulmein-Kallang Group Representation Constituency : 4 seats : 43749 votes.
Tampines Group Representation Constituency : 5 seats : 68719 votes.
Tanjong Pagar Group Representation Constituency : 5 seats : 69819 votes.
West Coast Group Representation Constituency : 5 seats : 60478 votes.
Hougang Single Member Constituency : 1 seats : 12266 votes.
Joo Chiat Single Member Constituency : 1 seats : 11014 votes.
Mountbatten Single Member Constituency : 1 seats : 11856 votes.
Potong Pasir Single Member Constituency : 1 seats : 8653 votes.
Whampoa Single Member Constituency : 1 seats : 10808 votes.
Yuhua Single Member Constituency : 1 seats : 11592 votes.
538653 out of 2,349,091 is 22.9% of the voters.
Method 2 - Mathematical
We use the voters divided by the number of seats to get the "voters needed per seat" figure. Then we sort them by voters/seat.
From this, we can assume that by taking constituencies from the top going down, we will get the lowest amount of voters needed to get 44 seats.
Lets assume we take the set S = {2, 3, 4, ..., 18} where numbers represent the row number in the spreadsheet (row 1 is the heading). We get the following, 47 seats and 578800 votes needed. We can see that we only need 44 or more.
So let's try to trim it down, we can remove 3 seats but there are no 3 seat GRCs, so we can remove 3 X 1 seat SMCs. Let's take the ones from the bottom with the highest votes/seat of course. They are T = {14,15,17}. So now we have the set that we are considering A = S - T, basically the set of constituencies from 2 to 18 excluding 14, 15 and 17.
This gives us the following result: 538653 votes needed for 44 seats.
Although we have already arrived at the same result as method 1, we cannot stop here. We must investigate to see if we can lower our number even further.
We have 1, 4 and 5 seats constituencies in our final set (A). We have to see whether we can replace them in any way so that we can have a lower total votes needed amount (538653). On the side of the non-selected constituencies, we have 1, 5, 6 seats.
Possibilities of replacement are:
Lets assume we take the set S = {2, 3, 4, ..., 18} where numbers represent the row number in the spreadsheet (row 1 is the heading). We get the following, 47 seats and 578800 votes needed. We can see that we only need 44 or more.
So let's try to trim it down, we can remove 3 seats but there are no 3 seat GRCs, so we can remove 3 X 1 seat SMCs. Let's take the ones from the bottom with the highest votes/seat of course. They are T = {14,15,17}. So now we have the set that we are considering A = S - T, basically the set of constituencies from 2 to 18 excluding 14, 15 and 17.
This gives us the following result: 538653 votes needed for 44 seats.
Although we have already arrived at the same result as method 1, we cannot stop here. We must investigate to see if we can lower our number even further.
We have 1, 4 and 5 seats constituencies in our final set (A). We have to see whether we can replace them in any way so that we can have a lower total votes needed amount (538653). On the side of the non-selected constituencies, we have 1, 5, 6 seats.
Possibilities of replacement are:
- 1 for 1
- 4 for 1,1,1,1
- 5 for 5
- 5 for 1,1,1,1,1
- 1,4 for 5
- 1,1,1,1,1 for 5
- 1,1,4 for 6
- 1,5 for 6
- 1,1,1,1,1,1 for 6
Let's look at them case by case.
Case 1: If there was a 1 seat that was directly replaceable, it would have been higher up in the ranking and would have been included. Not possible.
Case 2: We take the 4-seat with the highest votes needed and compare it with the least votes needed of the first four 1-seats and see if it is possible. Row 6 is compared with Rows 14,15,17,25. Row 6 has 45780 votes needed while 14,15,17,25 has 55648 votes needed. So if the lowest votes needed cannot replace Row 6, Case 2 is not possible.
Case 3: Same as Case 1.
Case 4: Similar to Case 2 (18 Vs 14,15,17,25,27)
Case 5: Similar to Case 2 (6,12 Vs 20)
Case 6: Similar to Case 2 (3,5,7,8,12 Vs 20)
Case 7: Similar to Case 2 (6,8,12 Vs 19)
Case 8: Similar to Case 2 (12,18 Vs 19)
Case 9: Similar to Case 2 (2,3,5,7,8,12 Vs 19)
We can see that there are no possibilities of substituting any constituencies for another one. Therefore, we can conclude that 538653 votes needed for 44 seats is the optimal result.
Conclusion
What I've shown here is that 538653 votes are needed out of 2,349,091 and this is 22.9% of the votes. Not as low as 17% as mentioned by Donaldson on his blog.
I double checked the data when I entered it and I double checked my first method (method 1) with another method (method 2). However, I welcome any critique if any of my methods are unsound or have flaws in them =).
Disclaimer
I am not being partisan or trying to imply in any way that the election system in Singapore is flawed. The fact that 22.9% of the votes can get > 50% of the seats in parliament is what is to be expected of a first-past-the-post system.
I am more interested in the algorithmic and mathematical problems that arise from the question, "How many votes are needed to get > 50% of seats in the Singapore parliament?"
I am more interested in the algorithmic and mathematical problems that arise from the question, "How many votes are needed to get > 50% of seats in the Singapore parliament?"
Clarence
