Joe Otten is the author of an STV program for Windows which is being extended to handle constraints
In this paper we consider the situation with two independent sets of constraints, such as nationality and gender. A group of candidates are those sharing the same constraining characteristics. While I agree that Hill's method works, and that simpler methods do not, there is a problem when the numbers of candidates and groups of candidates become large. For instance, suppose there are 20 candidates to be elected from 30 groups, with 2 candidates in each group, there would be astronomic number of cases (»330), of which maybe only half can be ruled out by the constraints. Such a list of possibilities would take far too long to calculate on a fast computer with efficient code, and occupy an excessive amount of storage. This is clearly not feasible. It might appear that such complexity of constraints should not arise in practice - unfortunately it has arisen which has prompted the approach given here.
EM EW SM SW WM WW
0 7 6 0 1 0
1 6 5 1 1 0
1 6 6 0 0 1
2 5 4 2 1 0
2 5 5 1 0 1
3 4 3 3 1 0
3 4 4 2 0 1
4 3 3 3 0 1
Each time an election or exclusion causes one or more of these results to
become impossible, we cross it out. We can then see when it is necessary to
guard or doom candidates.
This problem requires a solution that does not involve listing every combination since the size of the list rises exponentially with the number of groups. I believe this is possible if we deduce and keep track of every constraint as it applies to every group. In Hill's example this is possible. At the crucial point he argues that '...only 2 Scottish women remain, we have to elect 6 Scottish altogether and have elected none as yet. Therefore we must elect at least 4 Scottish men. But we are restricted to 7 men in total and we have already elected 3. It follows that we must elect exactly 4 Scottish men, and that means that the remaining 2 Scottish women must be guarded, and that the 2 English men must be excluded as soon as possible,...'
This argument is sound, and does not itself rely on an exhaustive listing of all the possible combinations. I propose a procedure which implements this sort of logic in a way that can be automated and performed at the start of the count and after every election and exclusion.
The way I propose to represent this is as in the following grid.
A row (of 4 lines) corresponds to each gender constraint and a column to each nationality constraint. A cell, with 4 entries, Elected, Min, Max, Cands, corresponds to a candidate group or to a row or column total or to the grand total. The grid has been initialized with the numbers of candidates in each group, and the various totals required by the constraints (as from Hill's example). Of course, we have none elected in this initial table, the constraints are as given before, and the new information is that concerning the candidates.
The basic method is to repeatedly apply five rules to a table until a stable condition is produced which essentially provides a bounding box which must enclose any conformant solution. We need to apply these rules initially (to confirm that a solution is possible) and at each election and elimination. Each rule is triggered by a condition which should be satisfied by a conformant solution.
Once the grid is in a settled state, and if in any cell Elected = Max then continuing candidates in that cell are doomed. If in any cell Min = Cands then all continuing candidates in that cell are guarded.
I hope it is clear that each of these rules is a logical necessity, as is its Rule when it applies. What is not so clear is that following these rules is sufficient to ensure that candidates are always doomed or guarded as necessary.
To see what is going on, let us apply the above now before we start counting the votes, as we need to in order to ensure that there is a conformant result and to identify any candidates which may be initially guarded or doomed.
The next events are - the election of 2 English Men and 2 English Women, and the exclusion of a Scottish Woman. We would in practice update the grid after each of these 5 events, but for the purpose of this example, we will do it in one go.
All I have demonstrated here is that this method achieves the same result in this case as Hill's method. However, I hope that it is clear how it works and why it should therefore work for all 2-dimensional constraints problems.
Rules 4 and 5 were not needed as none of the Row total or Column total Min and Max could be altered. This was because the constraints were of the rigid 'must equal 7' variety rather than the more flexible 'must be between 5 and 9' variety.
The logic above, using guarded and doomed, depends upon electing and excluding candidates one at a time. None of the three sets satisfy this, and in consequence, the integration of these STV rules with the constraint logic is non-trivial. The addition is naturally simplest with the Church rules, since they have been written with that intent. However, the rules themselves are without constraints and a separate section gives a series of amendments to the rules which are to be applied in the case of constraints. The wording of the special section is reasonably straightforward since elections and exclusions take place one at a time.
Consider the following situations:
With Meek, the published algorithm only allows single exclusions, but the version implemented by I D Hill allows for a single exclusion and multiple elections at one stage. Both the elections and the exclusion need to be serialized to apply the constraints logic.
With all the rules, if two candidates achieve the quota at the same stage, then the election of one could cause the other to be doomed. Hence, if this is a tie, the tie-breaking logic would need to be applied to produce a result, even though this was not necessary without constraints.
Our illustration here was with an example having two independent types of constraint and therefore requiring two-dimensional tables. However, the same logic can be applied with higher dimensions if required.
With larger problems, the size and number of dimensions, and hence the computational requirements, will increase in proportion, not suffering the combinatorial explosion that the listing of all possible combinations does.
Software has been written to implement this procedure and successfully tested on a 4×16×9×3 hypercube.