Up: Issue 13 Next: Paper 4 Previous: Paper 2

# Voting matters - Issue 13, April 2001

## STV with multiple constraints

#### J Otten

Joe Otten is the author of an STV program for Windows which is being extended to handle constraints

### The problem

David Hill writes in Voting matters[1] that the handling of constraints should be undertaken by marking as doomed candidates who cannot be elected if a conformant result is to be obtained, and marking as guarded those candidates who must be elected for a conformant result. A doomed candidate is eliminated immediately so that the next preference can be taken into account, while guarded candidates await attaining a quota (if that is possible). However, where multiple constraints are to be applied, then Hill states we should list all the possible ways that the constraints might be met, so that we can tell when it is necessary to guard or doom continuing candidates. If you are unfamiliar with these details, I recommend reading Hill's article first.

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.

### A worked Example

We re-work Hill's example which is that of 14 to be elected, where must be 7 English, 6 Scottish and 1 Welsh, and additionally 7 Men and 7 Women. We refer to each of these by the initial letter with the nationality first. In this example, there are 8 possibilities listed:

```   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.

1. In each group we require: Elected £ Min £ Max £ Cands. Rule - increase Min or decrease Max. If as a result of applying the rules Min > Max then no conformant result is possible (there is no bounding box) and we do not regard this as a settled state.
2. In each group, the Min must be possible - i.e. it must be possible for this few to be elected, even if the current minimum is elected from the row/column, and the maxima elected from each other group in that row/ column. Rule - increase Min.
3. Like 2, for maxima - in each group, it must be possible for this many to be elected, even if the current maximum is elected from the row/column, and the minimum elected from each other group in the row/column. Rule - decrease Max.
4. The row/column minimum must be at least the sum of the minima of the items in the row/column. Rule - increase Min.
5. The row/column maximum must be no more than the sum of the maxima of the items in the row/column. Rule - decrease Max.
Hence if any of the conditions required is violated, we apply the associated rule until a settled state is reached.

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.

• By 1, Max English Men must be reduced from 7 to 4 because there are not enough candidates. Similarly, Max Scottish Women must be reduced from 6 to 3.
• By 2, Min Scottish Men = 2. There are at most 5 non-Scottish men, and we need 7 men altogether.
• Similarly by 2, Min English Women = 3. Since Min English + Max English Men = 7.
• By 2, Min Scottish Men = 3. Since Min Scottish Men + Max Scottish Women = 6.
This is a settled state, so we conclude that a conformant result is possible, and we can start counting the votes. The first event is the election of a Welsh man, which we mark as a 1 in the space referring to the number of Welsh men elected. This requires the following alterations:

• By 1, Min Welsh Men = 1.
• By 3, Max Welsh Women = 0.
• By 2, Min English Women = 4.
• By 3, Max English Men = 3.
This is a settled state. We now have 2 cells where Elected = Max, so the continuing candidates in those cells, a Welsh Man and the Welsh Woman are doomed. The doomed candidates are removed from the grid by reducing the Cands entry.

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.

• By 1, Min English Men = 2, due to the election.
• By 1, Max Scottish Women = 2.
This completes the actions directly as a result of the elections, but now we must continue to give a settled state
• By 2, Max Scottish Men = 4.
• By 2, Min English Women = 5.
• By 3, Max English Men = 2.
• By 2, Min Scottish Men = 4.
• By 2, Min Scottish Women = 2.
• By 3, Max English Women = 5.
At this point, the grid is in a settled state, and we know precisely how many are in each group, so the constraints problem has been solved. Elected = Max for English Men, so the 2 continuing English Men must be doomed, and Min = Cands for the Scottish Women, so these must both be guarded. The count will continue to determine which of the English Women and which of the Scottish Men are elected.

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.

### Constraints and the STV rules

Given the logic above for handling constraints, then this must be integrated into an STV system which would use a specific rule set in the unconstrained case. We consider this with three sets of rules: The Church of England rules[2](a hand-counting system which makes provision for constraints), the current ERS rules[3] (hand-counting with no provision for constraints) and Meek[4] (computer-counting with no provision for constraints).

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:

1. Suppose A is excluded, and this causes C and D to be doomed. The Church rules just exclude A at this stage, and then exclude C and D at the next stage. It seems possible to exclude all three together, but this surely makes no difference.
2. Suppose A and B are to be excluded (with A having fewer votes than B), and the exclusion of A causes B to be guarded, and C and D to be doomed. This then is essentially the same case as above.
3. Suppose A and B are to be excluded (with A having fewer votes than B), and the exclusion of A causes C and D to be doomed, but does not affect the status of B. It is clear that C and D should be excluded before B, since transfers from C and D could spare B from exclusion.
This last case shows the importance of exclusions being undertaken one at a time. This implies that the rules in ERS for multiple exclusions should be changed to handle constraints. Indeed, whatever method is used to handle constraints, the serialization of elections and exclusions is needed.

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.

### Conclusions

The logic for handling constraints which was first specified by David Hill can be implemented in a manner that does not involve the use of large lists. This can be combined with the conventional STV rules, provided changes are made to elect and exclude candidates one by one.

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.

### Reference

Up: Issue 13 Next: Paper 4 Previous: Paper 2