A full source code review of the Idox Count Engine implementation was performed in order to validate that it faithfully reproduces the Maltese PR-STV Algorithm. In addition to the corresponding functionality testing, the validation assessed whether the methodologies and algorithms implemented by Idox Group follow the guidelines and processes required by the Maltese Government. The implementation was reviewed for non-casual as well as casual elections.
Scope of Project:
- Receive and check in TDP/Software
- System Familiarization training to SLI Compliance by Idox Group
- Source Code Review
- Test Report
- Archive Test Materials
The basic algorithm implementation consisted of the following:
If this is a non-casual contest, the quota is calculated using the following formula:
If this is a casual contest, the quota is calculated using the following formula:
Both calculations accurately represent the calculation defined in the CT2298_2016 – Annex 5 – Schedule 13 of the General Elections Act.
The code base was reviewed to verify a number of key files and functions implemented in regard to the election process. Inputs and outputs were analyzed for each key file and function in order to verify the flow was logical and correct.
The source code was traced to follow the flow of the election process. The below narrative of the process begins with the first stage of the contest and continues through the process highlighting where certain stages differ.
The first step of the contest allows the user to determine what type of process is to be employed (‘Complete Contest’, ‘Next Stage’ or ‘Casual’). Note that initially only the ‘Next Stage’ option will be available. A non-casual contest will need to have reached its completion point before the other options listed become available
Selecting ‘Next Stage’ implements the “Maltese STV Engine” process. This also defines the type of the next stage (first preference, surplus, exclusion, or not yet determined). Note that ‘not yet determined’ is only used at the beginning of a stage where the type will be determined as ‘surplus’ or ‘exclusion’ later on. At this point parcels are determined in readiness for the next stage. Different parcels are added to the saved list of parcels depending on the type of parcels available for that stage.
The number of votes for each candidate is determined. These votes are checked against the calculated quota. If a candidate has votes greater than or equal to the quota, the candidate is deemed elected and the number of votes they received are saved in a variable which is then ordered from the greatest to least number of votes.
If 1 or more candidates has the same number of votes, the tie resolution function is called. Since the current stage is the first stage, the program will throw a request to the user to determine the winner of the tie. This is accurate to the Maltese algorithm since there were no previous counts to compare votes.
The ordering of candidate votes continues until all candidates have been ordered by the number of votes received, with tie outcomes determined. If, at this point, there are no candidates with a surplus and the number of continuing candidates equals one more than the number of seats to fill, all continuing candidates except for the bottom candidate are deemed elected. This essentially skips an unnecessary exclusion step where the bottom candidate would have been excluded and ballots would have been transferred to the remaining continuing candidates. However, the number of continuing candidates at that point would have equaled the number of seats to fill. Per the Maltese algorithm, if the number of continuing candidates is equal to the number of seats to fill, all remaining continuing candidates are to be elected. Therefore, this process is in line with the Maltese algorithm. If, at this point, the number of elected candidates equals the number of seats to fill, the contest ends.
Note that new stages only occur once the user selects ‘Next Stage’. The point that any stage differs from the 1st preferences stage is in the move to next stage function. If there are still candidates with a surplus, the next candidate with a surplus is obtained. Then, that candidate’s surplus ballots are transferred. All ballots allotted in the previous stage for the candidate in question are evaluated.
A variable is created to determine which candidates are not continuing.
The surplus amount is then accurately calculated by taking the count of ballots for the given candidate from all stages and subtracting the quota. The transferrable ballots are determined which returns the ballots from the previous stage sorted by the next preference candidates.
If the total number of transferrable ballots is less than or equal to the surplus, all transferrable votes are separated into parcels for each candidate in backwards order. A separate parcel is created for the non-transferrable ballots deducted from the candidate with the surplus so that the surplus is exhausted. These ballots are also transferred in backwards order.
If the total number of transferrable ballots is greater than the surplus, a transfer ratio is calculated to be the surplus divided by the total transferrable ballots. The count of actual transferrable ballots per candidate is then calculated to be the truncated outcome of the count of current transferrable ballots per candidate
multiplied by the transfer ratio. The decimal value truncated is saved for use. The remaining ballots to be transferred is then calculated to be the surplus minus the sum of all actual transferrable ballots calculated. If there are additional ballots to transfer (the surplus has not been exhausted), then the candidate with the highest decimal value remainder calculated above is awarded an additional ballot. This order continues until the surplus is met.
If two or more remainder values are equal and the number of tied remainders are not less than or equal to the number of ballots left to transfer, then the candidate with the highest number of transferrable ballots (initially – before ratio was considered) will get the additional ballot transfer. If there was also a tie with regards to the highest number of transferrable ballots, the tie resolution function is called. The functionality of this function is the same as called in the 1st Preference stage, however, the current stage will not equal the first stage. Therefore, this function will essentially be called in order of stages beginning with the first stage, until the number of votes for each tied candidate up to the given stage is unequal. The candidate at the first stage with a higher number of votes will win the tie. If the candidates have the same number of votes all the way up to the current stage, the program will throw a request to the user to determine the winner of the tie. This accurately follows the Maltese algorithm.
The actual transferrable ballots are separated into parcels for each candidate and are in backwards order of the transferrable ballots initially determined. This is in line with clarifications received by Idox Group.
The function to declare elected candidates is then called, and the same process is followed at this point as in the 1st preference stage. The only difference is when the tie resolution function is called the current stage will not equal the first stage, so the candidate at the first stage in which a higher number of votes was recorded will win the tie. If the candidates have the same number of votes all the way up to the current stage, the program will throw a request to the user to determine the winner of the tie. This accurately follows the Maltese algorithm.
If there are no candidates with a surplus to transfer, then a candidate must be excluded.
The candidate with the lowest number of votes is determined. If there is a tie, the tie resolution function is called. This functions the same as in the Transfer Surplus stage, only the candidate with the lowest number of votes at a given stage is returned (instead of the highest).
The votes of the candidate chosen to be excluded are then transferred, by next preference, to the other continuing candidates with the ordering of ballots preserved (instead of reversed as in the Transfer Surplus stage). A separate parcel is created for all non-transferrable ballots, which also preserves the order of ballots. The total number of accumulated votes for the candidate excluded are determined and then all votes to transfer are determined.
The function to declare elected candidates is then called, and the same process is followed at this point as in the Transfer Surplus stage.
A check is done to see if the contest is finished, if all seats are not filled, the Next Stage button is enabled and the calculations continue, otherwise the contest concludes.
When the ‘Casual’ button is clicked, if the current contest was a casual election, the user is given the option to delete the election. Otherwise, the user is given the option to create a casual election. A new engine is essentially created for the casual contest. The user is given options to select the vacating candidate and the nominated/continuing candidates for this casual election. The vacating candidate can only be chosen from the previously elected candidates. The nominated/continuing candidates can be chosen from the previously elected and excluded candidates. The background colors for these will differ based on whether the candidates were previously elected or excluded. If the vacating candidate was selected as a continuing candidate, an error message will be displayed to the user. Furthermore, at least one nominated/continuing candidate must be selected or an error message will be displayed.
There is no programmatic check on whether previously elected candidates have been selected as continuing candidates, so it is up to the Electoral Commission to ensure that all candidates selected as continuing candidates are validly nominated, as per item #20 in “Annex 5, Schedule 13” of the Maltese General Elections Act.
The initial parcels are then defined to be all of the parcels from the vacating candidate.
The functionality then starts all over from the first button click of ‘Next Stage’. The only differences in this election are the calculation of the quota, as noted above. Surplus transfers do not occur as the moment a candidate reaches the quota they are elected. This is all in line with the Maltese algorithm.
Also, at the end of a stage, when checking if the contest is finished, the contest will return that it is finished if there are no continuing candidates. This is a necessary check specifically for casual contests as there could be scenarios where no candidates received enough votes to reach or exceed the quota.
After conducting a full source code review of the Idox Count Engine implementation, SLI Compliance was able to confirm that the Idox Count Engine (v0.7.4) implementation reproduces the Maltese PR-STV Algorithm and that the methodologies and algorithms implemented by Idox Group follow the guidelines and processes required by the Maltese Commission.
What we did
- Source Code Review
- Functionality Testing