Constrained Approval Voting: A Voting System to Elect and Governing Board
Steven J. Brams
Unlike management scientists, political scientists and social choice theorists are rarely asked to use their expertise to solve practical problems in the private sector. I was surprised when a professional association asked me to advise them on the election of their governing board. I discovered that methods familiar to management scientists were well suited to the problem.
I shall not reveal the association's identity. However, I have altered no essential facts of the study.
The association was reviewing its election procedures in response to pressures for reform. In particular, some members thought that certain types of members were underrepresented on the board--and other types overrepresented--creating biases that affected the association's policies. A different voting system was considered a possible way to ameliorate this perceived misrepresenation.
After much discussion, which included a consideration of proportional-representation systems (for example, the Borda count and the Hare system of single transferable vote), I recommended constrained approval voting (CAV). Under CAV, the basic feature of approval voting [Brams and Fishburn l983]--that voters can vote for as many candidates as they like--is wedded to constraints placed on the numbers that can be elected in different categories.
This hybrid system radically modified the purpose for which approval voting was originally designed. It also raised a number of questions about the properties of constraints and their likely effects on the representation of different interests on the board.
In previous elections, the members voted for a slate of candidates prepared by a nominating committee. The committee prepared a slate of about twice as many candidates as there were seats to be filled; members could vote only for as many candidates as there were seats to be filled--no more and no less. Those candidates with the most votes were elected to fill the open seats over a multiyear cycle. If the cycle were two years, for example, board members would serve two years, with half the seats being filled in each annual election.
No change was contemplated in the size of the board or in the terms of office of its members. The issue was whether to elect board members by constituencies representing different interests of the association. What made the problem unusual was that a constituency was defined by both region and specialty.
The Representation Problem
Assume that there are two regional divisions of the association (A and B) and three specialty divisions (X, Y, and Z). The percentages of members that fall into each category can be shown in a 2 x 3 matrix, where the rows indicate the regional divisions and the columns the specialty divisions:
Region X Y Z Row Total
A 27 l6 l7 60
B 21 9 l0 40
Column Total 48 25 27 l00
These percentages may be interpreted as targets for the composition of the board.
The targets in any election will depend not only on the numbers of members that fall into each category but also on the numbers of board members continuing in each category. For example, if elections are held over a two-year cycle, and cell AY already contains 24 percent of the continuing board members, the l6 percent shown in the table should be reduced to eight percent as a target--and underrepresented cells increased accordingly--to ensure that members from AY do not continue to be overrepresented but instead are properly represented at the l6-percent level (the average of 24 and 8) on the next board.
The percentages shown in the table are an ideal: given that each board member has one vote, no allocation of board members (and therefore votes) to each category will mirror the percentages perfectly. Although a system of weighted voting could lead to a better fit, no consideration was given to endowing board members with different numbers of votes.
For the next step, assume that the percentages in the matrix are the targets, and six new members are to be elected to the board. (By coincidence this number exactly matches the number of cells.) Multiplying the target percentages by 6, we obtain the following target election figures, or TEFs:
Region X Y Z Row Total
A l.62 0.96 l.02 3.60
B l.26 0.54 0.60 2.40
Col. Total 2.88 l.50 l.62 6.00
The remainders of each of the TEFs preclude a perfect matching of (whole) representatives to the cells. But this does not prevent us from narrowing the possibilities to those that are, in some sense, best-fitting. To do so, consider the following set of constraints:
(l) Row and column minima: Rounded down, the TEF column sums are 2, l, and l; the row sums are 3 and 2. Assuming these as minima for the totals of regional and specialty representatives, respectively, there are 65 distinct cases that satisfy these constraints and whose cell entries sum to 6, as exhaustively enumerated in Table l.
Table l about here
There are systematic procedures but seem to be no efficient algorithms for generating all these cases. For a 2 x 3 matrix, a hand calculation is feasible; for larger matrices, the association used computer spreadsheets to find integer allocations, reflecting finer breakdowns of the association.
(2) Row and column maxima: Rounded up, the TEF column sums are 3, 2, and 2; the row sums are 4 and 3. Assuming these as maxima for the totals of regional and specialty representatives 30 of the 65 cases satisfying constraint l are excluded. Specifically, the row maxima exclude none of the 65 cases, but the first, second, and third column maxima exclude 8, ll, and ll cases, as shown in Table 2.
Table 2 about here
These column-maxima constraints are mutually exclusive: the cases excluded by each one are not excluded by either of the other two. Thirty-five cases remain admissible.
(3) Cell minima and maxima. Rounding down and up the TEFs of all the cells gives a minimum and a maximum for each cell. Satisfying these minimal and maximal cell constraints reduces the 35 admissible cases meeting constraints l and 2 to just l0 "controlled roundings," as shown in Table 3. Note that the sum of the first row in the first five cases is 4,
Table 3 about here
whereas this sum in the last five cases is 3.
The three constraints, applied progressively, have reduced the number of admissible cases from 65 (constraint l) to 35 (constraints l and 2) to l0 (constraints l, 2, and 3) whose cell entries, and column and row totals, sum to the grand total of 6. Satisfying these three constraints results in a controlled rounding, which can always be found for any matrix [Cox and Ernst l982]. For larger arrays (that is, three dimensions or more), however, a controlled rounding may not exist [Fagan, Greenberg, and Hemmig l988].
A controlled rounding can be defined more straightforwardly as one in which, for every column and row, the sum of its cell TEFs, rounded down or up, equals the column or row (total) TEF, rounded down or up, with the roundings summing to some grand total. Constraints l and 2 give all possible cases that are roundings of the column and row TEFs and sum to 6; constraint 3 limits these to those that are also roundings of the cell TEFs.
Further Narrowing: The Search May Be Futile
One could reduce the number of cases still further by using various criteria. For example, define an integer representation to be cell-consistent if the TEF of a cell that is assigned a larger integer is at least as great as one that is assigned a smaller integer. In controlled-rounding case #l above, the TEF of cell BY is 0.54 and that of BZ is 0.60; yet BY is assigned a l and BZ a 0, which makes this representation cell-inconsistent.
In fact, the only two cases that are cell-consistent are #2 and #9. Allocation #2 is cell-consistent because cell AX is the largest TEF (l.62) and receives the only 2 seats that are assigned to a cell; BY is the smallest TEF (0.54) and receives the only 0. Allocation #9 is cell-consistent because l's are assigned to all cells, so no smaller TEF receives a larger assignment than a larger TEF. When the integer assignments to the column and row sums are also consistent, the allocation is said to be consistent.
Another criterion for reducing the number of integer representations--in this case, to exactly one--is the Hamilton method of rounding [Balinski and Young l982], which has two steps:
(l) Allocate to each category--both the six cells and the column and
row sums--the integer portion of its TEF (that is, its number to the
left of the decimal point);
(2) Of those seats remaining (out of the six to be allocated in the
example), allocate them to the TEFs with the largest remainders--
starting with the TEF with the biggest remainder--until the six
seats are exhausted.
To illustrate the Hamilton method for the TEFs given earlier, the integer allocations according to step l are as follows (note that the column sums total 4 and the row sums total 5):
l 0 l 3
l 0 0 2
2 l l 4/5
The remaining seats are now allocated, according to step 2, on the basis of the TEFs having the largest remainders:
--three seats to cells in the 2 x 3 matrix (to which three seats have
already been allocated);
--two seats to the column sums (to which four seats have already
--one seat to the row sums (to which five seats have already been
These assignments give as a final allocation
2 1 1 4
l 0 l 2
3 1 2 6
This allocation is the same as (consistent) allocation #2 in Table 3. Allocation #9, on the other hand, is consistent but not Hamilton, which illustrates
Proposition l: Hamilton allocations are always consistent, but consistent allocations are not always Hamilton.
The second part of this proposition is proved by allocation #9. The first part follows from the fact that, by step l of the Hamilton method, TEFs with larger integer portions never receive fewer seats than TEFs with smaller integer portions; by step 2, TEFs with larger remainders never receive fewer seats than TEFs with smaller remainders. Hence, larger TEFs can never be assigned fewer seats than smaller TEFs.
Controlled roundings #3 and #5, in addition to the Hamilton allocation (#2), have column and row sums identical to that of the Hamilton allocation. However, these allocations are cell-inconsistent and hence inconsistent. By Proposition l, they cannot be Hamilton, because Hamilton allocations are a subset of consistent allocations. (Except for possible ties, in which a seat might be randomly assigned at step l or or step 2, Hamilton allocations are unique.)
So far, it would appear, a Hamilton allocation is the most sensible of the (consistent) controlled rounding allocations. But there is a rub: one may not exist.
For example, the following percentages and TEFs for the allocation of six seats differ very little from those used in the earlier example:
30 l0 l9 59
l8 12 ll 4l
48 22 30 l00
Target Election Figures
l.80 0.60 l.l4 3.54
l.08 0.72 0.66 2.46
2.88 l.32 l.80 6.00
Now applying the Hamilton method to the TEFs--both the cells and the column and row sums--one obtains the following allocations for each:
2 0 l 4
l l l 2
3 l 2 6
Although the column allocations sum to their Hamilton allocations, the first row sums to 3 (not 4), and the second row sums to 3 (not 2). This example proves that Hamilton allocations to the cells may not agree with Hamilton allocations to the column or row sums.
The fact that the Hamilton allocations in this example are unique, but not a controlled rounding, immediately implies
Proposition 2: A controlled rounding that is Hamilton may not exist.
A requirement of a controlled rounding is that the sums of the rounded cell TEFs for each column and row equal the corresponding rounded column and row TEFs.
Finally, to settle the question of the existence of a consistent controlled rounding, consider the following percentages for a 2 x 2 matrix and, given three seats are to be filled, the TEFs:
30 22 52
2l 27 48
51 49 l00
Target Election Figures
0.90 0.66 l.56
0.63 0.8l l.44
l.53 l.47 3.00
The only cell-consistent allocation is to assign one seat to all entries except the lowest (0.63). But the consistency of the column sums demands that the first column receive two seats, when in fact the sum of its cell-consistent entries (0 + l) is l. This example proves
Proposition 3. A controlled rounding that is consistent may not exist.
There is a final difficulty with cell-consistent controlled roundings, illustrated by the following percentages and TEFs:
14.6 9.4 l8.0 42.0
9.6 9.6 0.4 l9.6
l9.8 9.2 9.4 38.4
44.0 28.2 27.8 l00.0
Target Election Figures
0.73 0.47 0.90 2.l0
0.48 0.48 0.02 0.98
0.99 0.46 0.47 l.92
2.20 l.4l l.39 5.00
The cell-consistent allocation of seats shown below is not consistent because the first two columns and the second two rows do not sum to values consistent with their column and row TEFs:
l 0 l 2
l l 0 l
l 0 0 2
2 2 l 5
However, a new difficulty arises in this example: the second row is entitled to only 0.98 seats, but the cell-consistent assignments for this row sum to 2.
When the discrepancy between the cell-consistent sum of a column or row and its TEF is greater than l.0, it does not satisfy quota [Balinski and Young l982]. Put another way, the column or row TEF, rounded either up or down, is not equal to the cell-consistent sum. In the example, 0.98 rounded up is l, but the cell-consistent sum of the second row is 2, which proves
Proposition 4. A cell-consistent rounding may not satisfy quota.
An assignment of seats that violates quota, of course, is not a controlled rounding.
Because the narrowing-down criteria I have discussed--consistent allocations and Hamilton allocations--may be incompatible with all controlled roundings, they cannot reliably be used to distinguish either a very few or a single best allocation. In addition, a cell-consistent allocation not only may be inconsistent but also may fail to satisfy quota--and therefore not be a controlled rounding.
Other criteria have been proposed for filtering out the best-fitting controlled roundings, but they are not tied, in my view, to fundamental principles of fair representation. For example, Balinski and Demange [l986] and Gassner [l988] provide excellent analyses of technical criteria for finding better-fitting biproportional allocations (that is, those proportional to the TEFs in two dimensions, as here); they suggest their application in a political context, where biproportionality might be based on political parties and geographical constituencies rather than specialities and regions. Cox [l987] argues for unbiased controlled roundings and provides a computationally efficient procedure for finding them. Other approaches and algorithms have been proposed [Kelly, Golden, and Assad l989].
But for the purpose of choosing an elected board that is a reasonable approximation of the TEFs, the fact that no controlled rounding may satisfy a requirement as weak as consistency--not to mention give allocations compatible with a specific apportionment method like Hamilton--casts doubt on the recommendation of one allocation on purely theoretical grounds. Indeed, a case can be made that any of the controlled roundings is good enough: each cell receives representation within one seat of what it is entitled to, and so does each geographical region and functional category.
In the absence of compelling criteria for singling out a best controlled rounding in an election, I suggested to the association an empirical solution that had, underlying it, a theoretical rationale tied to the notion of voter sovereignty. This was to let the voters themselves choose the outcome they most favored.
Constrained Approval Voting (CAV)
I proposed, as a starting point, that the association use approval voting. Under approval voting, members would be able to vote for as many candidates as they approved of, or found acceptable, rather than--as under the extant system--be restricted to voting for exactly as many candidates as there were seats to be filled. But, as before, members could still vote for any candidates, irrespective of their regional or specialty designation, which now would be explicitly indicated on the ballot.
The advantages of approval voting have been discussed in detail elsewhere [Brams and Fishburn l983; Merrill l988; Nurmi l987]. However, these advantages pertain mainly to single-winner elections with more than two candidates, for which the proportional representation of different kinds of representatives on a board is not an issue.
Still, there seemed no good reason to force voters to vote for an arbitrary number of candidates. Rather, I argued, they should be permitted the more flexible option of voting for as many candidates as they liked,
The flexibility afforded by approval voting made sense to association members, who testified that many members did not have sufficient knowledge to make more than two or three intelligent choices. Thus, the requirement that they vote for, say, six candidates forced less knowledgeable members (usually newer) to make less-than-informed judgments, often influenced by casual advice from more senior members.
My second recommendation--to restrict the domain of possible outcomes--was designed to counteract a possible bias that approval voting might introduce. Specifically, if members of the largest categories, like AX with 27 percent of the members, tended to concentrate their votes on candidates in this category, they could unduly affect the election.
In fact, even under the extant system where voters were required to vote for an entire slate, the nominating committee "engineered" the slate to thwart voters from electing too many members of one type. For example, if AX members were overrepresented on the continuing board, the nominating committee might propose AX candidates who were not well known to diminish their chances of election.
This form of manipulation is well known to political scientists [Riker l986]. But it is an informal device that on occasion had not worked as planned, which is one reason why the association wanted to explore alternatives that offered more formal protection. Presumably, an election system that explicity ensured the fair representation of different interests would also gain the confidence of voters. Consequently, whatever outcome it produced would be considered more legitimate.
If the admissible outcomes are restricted to the set of controlled roundings and not a particular one, then voters would decide not only who is elected from each cell but also, within limits, how many. Of course, limiting voters to outcomes in the set of controlIed roundings is radically different from using approval voting to elect single winners in multicandidate elections, with no restrictions on who can be elected.
Indeed, one might argue that the l0 controlled roundings in the earlier example are too restrictive a set. The 35 (or even 65) cases available if criterion 3 (or 2 as well) was lifted would give the voters more control in the choice of a board and hence greater sovereignty.
Thereby, the board's composition would be more responsive to their voting. Whereas the controlled roundings guarantee that an integer representation is no more than one seat from the TEFs, the less restrictive set of, say, 35 cases would permit 25 additional outcomes--each of which leads to the election of at least one different candidate--and still guarantee column and row sums within one seat of their TEFs.
The acceptability of this set versus the l0 controlled roundings depends upon the importance one attaches to the principle that the number of cell seats--versus the regional and specialty totals--should all be within one seat of the TEFs. To put this matter somewhat differently, the designation of what outcomes are admissible will depend on whether it is thought that more popular (that is, approved) candidates should be permitted to win at the price of causing deviations from the cell TEFs greater than one seat.
Once the voters have chosen the set of outcomes they deem admissible, the outcome they select under CAV will be that with the greatest total number of approval votes. For example, if the admissible outcomes are the l0 controlled roundings in the earlier example, they have in common the certain election of exactly one candidate from the three cells AX, AZ, and BX:
l 0 l
l 0 0
This means that the biggest vote-getters in each of these cells will be guaranteed election, whichever of the l0 controlled roundings wins. The votes for these candidates can then be set aside.
The particular controlled rounding that wins will be the one in which the total approval vote for the three remaining "discretionary" choices is greatest. In case #l, for example, the runner-up in cell AX, the winner in cell AY, and the winner in cell BY would complete the six choices. The total of the votes for these three candidates would be compared with analogous totals in the nine other cases, given by the sums of the votes of the three best-performing candidates in the appropriate cells who were not certain winners.
If one admits the 35 cases that meet criteria l and 2, what they have in common is that no candidates are guaranteed election from any cell (see Figure 2). In this set of cases, all six choices are discretionary, although the constraints that these cases--as well as the l0 controlled roundings--must satisfy still impose restrictions on the possible outcomes (for example, four discretionary choices cannot all be chosen from one cell). At the least stringent level of criterion l alone, the election of four candidates from cell AX is permitted in one case (see Figure l), which is more than a two-seat (l22-percent) deviation from its TEF of l.80.
In my opinion, this deviation is too large, and I therefore recommended tighter restrictions. Both the l0 controlled roundings and the 35 cases that ensure the row and column totals will be within one seat of the TEFs seemed acceptable to me. The association could choose how much leeway it wanted to permit the voters.
Clearly, approval voting, by allowing voters to vote for as many candidates as they like, gives voters greater sovereignty than does restricting their votes to a fixed number. But where one draws the line to preclude the election of candidates who would not form a representative board is a value judgment. My analysis clarifies the trade-offs that that judgment entails.
Aftermath: Why CAV Was Rejected--and Why Approval Voting Has Been
A majority of the committee formed to consider election reform proposals and make recommendations to the board thought that breaking the association down into regional and specialty categories would violate its unitary philosophy; they wanted members to view it as a single entity by its members. Consequently, the association decided to continue to use slate engineering to ensure, insofar as possible, a representative board. And once it had rejected categorizing candidates, it saw approval voting as a secondary issue and did not deem it desirable without the constraints.
The failure of the professional association to adopt CAV was, in my opinion, a function of another factor. I worked closely on the design of the new voting system with a subcommittee of about five people, but the full committee that made the final decision on adoption had about l0 additional members. Although these people received extensive written reports summarizing my work with the subcommittee, they probably did not fully appreciate its advantages over slate engineering, which had worked fairly well in the past.
The options (including CAV) presented to the full committee when it convened were phrased neutrally, and I was given ample opportunity (two hours, with discussion) to make my arguments. However, despite rumblings of discontent about the make-up of the board, there was no crisis at the time. Moreover, because the committee had previously considered and rejected other voting systems, most members felt that they had given due consideration to possible alternatives. In short, there seemed no overriding reasons to make a change.
By comparison, professional societies that have adopted approval voting have generally done so because it appeared to be a manifestly better system for electing their officials in multicandidate races. These societies now include The Institute of Management Sciences (TIMS, with about 6,000 members), the Mathematical Association of America (MAA, with about 26,000 members), the American Statistical Association (ASA, with about 15,000 members), and the Institute of Electrical and Electronics Engineers (IEEE, with about 300,000 members).
Members of these societies who were familiar with approval voting were instrumental in its adoption in their societies. I and colleagues also played a role in most of the adoption decisions [Brams and Fishburn l990]. Our association has led to several empirical analyses of election returns of these societies [Brams l988; Brams and Fishburn l988; Brams and Nagel l990; Fishburn and Little l988]. In the case of the IEEE, a close three-way race for president that a petition candidate almost won gave impetus to election reform in that society. Brams and Nagel [l990] analyzed the use of approval voting by the IEEE and noted particularly its negative effect on candidates with strong but relatively narrow support.
CAV is a somewhat more complex system than approval voting, but it is meant to solve the more difficult problem of ensuring equitable representation of different constituencies, not just electing the most approved candidate. Its major advantages, in my opinion, are to obviate the need for slate engineering and to give members greater voice in determining the composition of a representative board.
Although CAV was not adopted despite my recommendation, my combined experience with CAV and approval voting illustrates how tools of management scientists can be applied to problems in political science and social choice that arise in the private sector. The analysis of CAV not only provided an understanding of its possible practical effects but also cast new light, in a specific context, on fundamental issues in the theory of representation.
I gratefully acknowledge the support of the National Science Foundation under grant SES-87l537 and the professional association with which I worked. For valuable discussions and and comments on earlier versions of this paper, I thank Lawrence H. Cox, Morton D. Davis, Peter C. Fishburn, Robert Hemmig, William R. Jones, D. Marc Kilgour, Jacek W. Mercik, Richard F. Potthoff, and two anonymous referees.
Balinski, M. L. and Demange, G. l986, "Generalizing Proportionality; or How to
to Simultaneously Apportion Seats to Regions and to Parties," (report)
Laboratoire d'Economtrie de l'Ecole Polytechnique, Paris.
Balinski, M. L. and Young, H. P. l982, Fair Representation: Meeting the Ideal
of One Man, One Vote, Yale University Press, New Haven, Connecticut.
Brams, S. J. l988, "MAA Elections Produce Decisive Winners," Focus: The
Newsletter of the Mathematical Association of America, Vol. 8, No. 3,
Brams, S. J. and Fishburn, P. C. l983, Approval Voting, Birkhuser Boston,
Brams, S. J. and Fishburn, P. C. l988, "Does Approval Voting Elect the Lowest
Common Denominator," PS: Political Science and Politics, Vol. 21, No.
2, pp. 277-284.
Brams, S. J. and Fishburn, P. C. l990, "Approval Voting in Scientific and
Engineering Societies," (report) Department of Politics, New York
Brams, S. J. and Nagel, J. H. l990, "Approval Voting in Practice," Public
Cox, L. H. l987, "A Constructive Procedure for Unbiased Controlled Rounding,"
Journal of the American Statistical Association, Vol. 82, No. 398, pp.
Cox, L. H. and Ernst, L. R. l982, "Controlled Rounding," INFOR, Vol. 20, No. 4,
Fagan, J. T., Greenberg, B. V. and Hemmig, B. l988. "Controlled Rounding of
Three Dimensional Tables," (report) Statistical Research Division
Report Series, Census/SRD/RR-88/02, Bureau of Census, U.S.
Department of Commerce.
Fishburn, P. C. and Little, J. D. C. l988, "An Experiment in Approval Voting,"
Management Science Vol. 34, No. 5, pp. 555-568.
Gassner, M. l988, "Two-Dimensional Rounding for a Quasi-Proportional
Representation" (report) Facult des Sciences Sociales, Politiques et
Economiques, Universit Libre de Bruxelles.
Kelly, J. P., Golden, B. L. and Assad, A. A. l989, "The Controlled Rounding
Problem: A Review," (report) Working Paper Series MS/S 89-0l6,
College of Business and Management, University of Maryland.
Merrill, S., III (l988). Making Multicandidate Elections More Democratic,
Princeton University Press, Princeton, New Jersey.
Nurmi, H. l987, Comparing Voting Systems. D. Reidel, Dordrecht, Holland.
Riker, W. H. l986, The Art of Political Manipulation. Yale University Press,
New Haven, Connecticut.
I designed a voting system for a professional association to ensure the equitable representation of different interests on its governing board. Approval voting, whereby voters can vote for as many candidates as they approve of, is combined with constraints on the numbers that can be elected from different categories of members to find the set of candidates most approved of by all voters, subject to the constraints.
Steven J. Brams is professor of politics at New York University. He is the author or coauthor of ten books that involve applications of game theory or social choice theory to subjects ranging from the Bible to superpower conflict.
Table l. There are 65 different allocations of six candidates that satisfy criterion l: the row and column sums are no less than the row and column
TEFs rounded down (minima).
Table 2. Of the 65 allocations of six candidates that satisfy criterion l, 30 cases are excluded and 35 cases included by criterion 2: the row and column sums are no more than the row and column TEFs rounded up (maxima).
30 Cases Excluded
35 Cases Included
Table 3: Of the 35 allocations of six candidates that satisfy criteria l and 2, there are l0 cases that satisfy criterion 3: the cell entries are no less than the cell TEFs rounded down (minima) and no more than the cell TEFs rounded up (maxima). These are the set of controlled roundings.
l 2 3 4 5 6 7 8 9 10
2 l l 2 l l l l 2 l l 2 2 0 2 2 0 l l l l l l l l l l l 0 2
l l 0 l 0 l 2 0 0 l l 0 1 l 0 l l l 2 l 0 2 0 l l l l 2 l 0