American Mathematical Monthly, The: Stochastic Apportionment

1. INTRODUCTION: THE PROBLEM OF APPORTIONMENT. Ten goals arc to be assigned to three brothers in numbers proportional to the ages (in years) of the recipients. Given the integral nature of a goat, it is not generally possible to meet exactly the condition of proportionality, and the resulting "apportionment problem" is a classic of operational research. The associated literature is extensive, including on the one hand discussions of criteria to be used in assessing different schemes, and on the other hand accounts of the properties of specific classes of scheme. A point of especial focus has been the apportionment of the seats in the House of Representatives to the states of the U.S.A. There are currently fifty states (excluding the District of Columbia) and 435 scats, which are to be divided among the states according to the U.S. Constitution [Article 1, section 2] of 1787 thus:

Representatives ... shall be apportioned among the several States ... according to their respective Numbers ....

No scheme is proposed in the Constitution, and Art. T therein permits a spectrum of interpretation of the phrase "according to their respective numbers." Politicians, lawyers, mathematicians, and others have been involved ever since in the cyclical debate of how to apportion the seats.

Although there is little in this article that is specific to the U.S. Congress, for case of exposition we shall use the terminology of the last problem. Our targets here arc to survey the general area and to propose a new method of apportionment that, in a certain way to be made more precise, meets all the usual criteria for such schemes. This new method is a lottery scheme whose implementation uses (pseudo-)random numbers. The scheme is fair in the sense of expectations so long as no minimal number of seats need be allocated to each state however small, in the Congressional example, the Constitution contains an additional condition that every state shall receive at least one seat. It is this violation of the principle of proportional representation that renders futile all attempts to obtain a truly fair system in which individuals are equally represented.

In section 3 we describe a new method that meets the so-called quota condition (see section 2) and gives proportional representation. In section 4 we present an adaptation of this method fur use in situations in which there are lower bounds on the allocations sought. We shall sec in section 4 that, in the presence of a lower bound, the quota condition (see section 2) provides another source of unfairness.

The established theory of deterministic apportionment is summarised in section 5. Those interested in learning more of the history and practice of apportionment should consult the book of Balinski and Young 111.

2. QUOTA. We suppose that there are .s states with respective populations [pi]^sub 1^, [pi]^sub 2^, ..., [pi]^sub s^ and that there are r seats in the House of Representatives. The total population size is [Pi] = [pi]^sub 1^ + [pi]^sub 2^ + ... + [pi]^sub s^, and thus the exact quota of seats for state i is the number q^sub i^ = r[pi]^sub i^/[Pi]. The problem is that the q^sub i^ are not generally integers, whereas representatives are (by axiom) indivisible. We call [pi] = ([pi]^sub 1^, [pi]^sub 2^,..., [pi]^sub s^) and q = (q^sub 1^, q^sub 2^,..., q^sub s^) the population vector and quota vector, respectively. We refer to the pair ([pi], r) as a problem.

It seems generally (if not universally) accepted that the property of satisfying quota is desirable. It is clear that, for all problems of the foregoing type, there exists necessarily at least one allocation that satisfies quota. This can cease to be the case when further conditions are added. In a variety of situations, including that of the U.S. Congress, there is a requirement that the [alpha] not be too small. Let l = (|^sub 1^, l^sub 2^,..., l^sub s^) be a given vector of nonnegative integers. We say that an allocation l [alpha] has lower bound l if [alpha]^sub i^ > or = l^sub i^ for all i. Of special interest is the case l = 1, the vector of ones, which is the lower bound specified in Art. I of the U.S. Constitution:

each State shall have at Least one Representative ....

Such a requirement is potentially disturbing since there exist problems ([pi], r) for which no allocation exists satisfying quota and having lower bound 1. For a simple (if extreme) example, consider the case when [pi] = (l, 1, 7) and r = 3.

A word for the novice-in common with other similar problems, one may be tempted to identify many desirable properties of schemes, only to find that no scheme has them all. A well-known example of this phenomenon is the result known as Arrow's Impossibility Theorem, which states that no preference ranking exists for a society that embraces a certain collection of five reasonable axioms (see [4, chap. 14]).

3. STOCHASTIC APPORTIONMENT WITHOUT LOWER BOUNDS. Although lottery schemes have been mentioned briefly in the literature (see, for example, [1]), the established theory is concentrated on deterministic schemes. Our purpose here is to propose a family of stochastic schemes, one in particular, that satisfy quota and that have the advantage of being truly fair and proportional in that each state receives a (possibly random) number of seats having mean value equal to the quota of the state. We shall see in section 4 that this cannot generally be achieved in the presence of lower bounds on allocations, and therefore we make the facilitating assumption for the duration of this section that no lower bound is required.

A random allocation is a vector A = (A^sub 1^, A^sub 2^,..., A^sub s^) of nonnegative-integer-valued random variables with sum r. A randomized scheme is a mapping that, to each problem ([pi], r), allocates a probability distribution on the space of appropriate allocations. Otherwise expressed, a randomized scheme results in a random allocation (we shall not spend any time on the choice of probability space, and such like).

There is a subtlety to the notion of a randomized scheme that we discuss briefly. We may seek to apply such a scheme to two given problems, perhaps by applying it twice to the same problem ([pi], r), or perhaps by applying it to ([pi], r) and to another problem ([pi]', r') obtained from ([pi], r) by changing some of the parameters. In so doing, we encounter the question of "coupling." That is, since randomized schemes make use of pseudo-random numbers, we shall need to specify whether, at the one extreme, we reuse for the second problem the pseudo-random numbers used already for the first, or, at the other extreme, we make use of "new" pseudo-random numbers. We discuss this no further at this stage (see, however, the two imal paragraphs of this section), since the discussion will concentrate for the moment on the use of randomized schemes for a single problem only.

Wc close this section with some remarks on the use of pseudo-random numbers. Some will argue that the degree of fairness of a stochastic scheme may not be evident to the population, and politicians also may be unwilling to accept such a scheme, since politicians are very sensitive to the marginal value to a party of a single seat. However, lotteries are already in wide use in areas having impact on individuals, not least in state-accredited systems for raising money for so-called good causes. Moreover, the allocation of individuals to the control group of a medical trial is usually done by lottery, and such a decision may be a matter of life or death. See [6] for an extended discussion of the drawing of lots.

When applying a randomized scheme to two or more problems, one needs to decide whether or not to resample the required pseudo-random numbers. The expectations under study remain the same, but the external perception of fairness is likely to be greater if the roulette wheel is spun afresh. A statistical virtue of resampling is the reduction of variances.

Let us suppose that (c) does not hold but that the outcome A satisfies quota. A slightly subtle point is that, conditional on this event, 4 is not fair. This is so because the conditioning changes the expectations. In summary, the scheme-work with the quota vector Q repeatedly until one obtains a random allocation that satisfies quota-is not a fair scheme.

A feasible line of enquiry that we have not pursued here is to postulate probabilistic models for problems, and to calculate the probability for such a model that the scheme we have devised results in an allocation that does not satisfy quota, in certain circumstances, the "law of anomalous numbers" (see |2], [3|) could be used as part of a basis for such a model.

This scheme, when iterated to reach a conclusion, identifies different levels of unfairness in its consecutive applications of the principle of equality of representation among the remaining states. Note that it terminates with a random allocation that satisfies quota if and only if there exists an allocation that both satisfies quota and obeys the lower bound.

Wc emphasize that, in the presence of a lower bound, the principle of satisfying quota is another potential source of unfairness. The upper quota presents no problem, but the lower quota can indeed be problematic.

Let us apply the above argument in the Congressional example, with l = 1. In the following table arc listed those states i that in the nine ten-yearly apportionments of 1920-2000 have Q^sub i^

A point of focus is the degree to which a scheme favours large over small states. There arc various ways of measuring such bias, both theoretical and empirical, and the case is made in [1] and [7] that Webster's "major fraction" method is the least biased hi this regard.

A scheme is said to be house monotone if no state's allocation diminishes when the size r of the house increases. A scheme that is not house monotone is said to suffer from the Alabama paradox. It is considered desirable that a scheme be house monotone. Other desirable features of schemes include the absence of what are known as the population paradox (in a growing population, state i can grow faster than state j, and yet lose a seat to j), and the new-state paradox (a new state may join the union, with an appropriate number of new seats, but the allocations to the original states change).

One may ask in what sense the stochastic apportionment scheme of section 3 meets these requirements. The latter scheme is population monotone in a stochastic sense: when state i loses people to state j, the number of scats allocated to i (respectively, j) is stochastically nonincrcasing (respectively, nondccreasing). (Sec [3, sec. 4.12] for a definition of stochastic ordering.) In a similar stochastic sense, the scheme is house monotone.

Finally, we consider the case of deterministic schemes in situations where there is a nontrivial lower bound on the allocation sought. As stated already, there may exist no allocation that satisfies both quota and the lower bound, and even if there exists such an allocation, there will generally exist no scheme that is fair across the board. The method used currently for apportioning the House of Representatives is to allocate one seat to each state however small (in 2000 there were just four states whose quotas were smaller than one) and then to apply the method of equal proportions to those states whose "residual" quotas are strictly positive. The outcomes of this scheme have, fortunately in recent decades, been allocations that have satisfied quota.

ACKNOWLEDGMENTS. The author thanks Gracmc Milton lor telling him of the apportionment problem, and Richard Wehcr for discussing it with him and lor help with related references. Friedrich Pukclshcim kindly pointed out his online hihliography or apportionment [5].

REFERENCES

1. M. L. Balinski and H. P. Young, Fair Representation, Meeting the Ideal of One Person, One Vole, 2nd ed., The Brookings Institution, Washington, D.C., 2001.

2. W. Feller, An Introduction to Probability Theory anil its Applications, vol. 2. 2nd ed., John Wiley & Sons, New York, 1971.

3. G. R. Grimmctt and D. R. Stirzaker, Probability and Random Processes. 3rd ed., Oxford University Press, Oxford, 2001.

4. R. D. Luce and II. Raiffa, Games and Decisions, Dover, New York, 1989.

5. F. Pukelshehn, Pukclshcini's proportional representation literature list, www.uni-angsburg.dc/ba/i/pprll. html.

6. W. A. Silverman and I. Chalmers, Casting and drawing lots, in Controlled Trials from History. 1. Chalmers, I. Milne, and U. Trohler, eels., 2001, www.jaiiieslindlibrary/essays/castirig_of_lots/casting.html.

7. H. P. Young, Dividing the House: Why Congress Should Reinstate an Old Apportionment Formula, Policy Brief no. 88, The Brookings Institution, Washington, D.C., 2001 ; available at www.brook.edti/dybdocroot/ comm/policybriet's/pb88.htm.

GEOFFREY GRIMMETTs preoccupation with things random was inspired by the teachings of John Hammers ley and Dominie Welsh in Oxford, where he was an undergraduate from 1968 to 1971. Alter spending sixteen years in Bristol, he moved to Cambridge University in 1992 as professor of mathematical statistics. His research concerns primarily the theory of disordered spatial processes, particularly those arising in models of statistical physics. He is the author of several books including the textbook Probability and Random Processes. written with David Stirzaker. In his diminishing spare time, he plays music and hikes up and down mountains and canyons. His papers arc available via www.statslah.cam.ac.ukrgrg/.

Statistical Laboratory, Centre for Mathematical Sciences, Wilberforce Road, Cambridge CB3 0WB, United Kingdom

g.r.grimmett@statslab.cam.ac.uk