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
(»3^{30}), 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 1Each 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.

- 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. - 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*. - 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.* - The row/column minimum must be at least the sum of
the minima of the items in the row/column.
**Rule**- increase*Min*. - The row/column maximum must be no more than the
sum of the maxima of the items in the row/column.
**Rule**- decrease*Max*.

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.

- By 1,
*Min*Welsh Men = 1. - By 3,
*Max*Welsh Women = 0. - By 2,
*Min*English Women = 4. - By 3,
*Max*English Men = 3.

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.

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

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:

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

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.

- I D Hill. STV with constraints.
*Voting matters*, Issue 9, pp2-4. 1998. - GS1327: General Synod, Single Transferable Vote regulations 1990 and 1998. (Obtainable from Church House Bookshop, Great Smith Street, London SW1P 3BN.)
- R A Newland and F S Britton. How to conduct an election by Single Transferable Vote. ERS 3rd Edition, 1997.
- I D Hill, B A Wichmann and D R Woodall. Algorithm
123 - Single Transferable Vote by Meek's method.
*Computer Journal*. Vol 30, pp277, 1987.