Algorithms to deal with apportionment problems

Question

I need an algorithm, or technique, or any guidance to optimize the following problem:

I have two companies:

• Company A has 324 employees
• Company B has 190 employees

The total of employees (A+B) is 514. I need to randomly select 28% of these 514 employees.

Ok, so let's do it: 28% of 514 is 143.92; Oh... this is bad, we are dealing with people here, so we cannot have decimal places. Ok then, I'll try rounding that up or down.

If I round down: 143 is 27,82101167% which is not good, since I must have at least 28%, so I must round up to 144.

So now I know that 144 employees must be selected.

The main problem comes now... It's time to check how much percentage I must use for each company to get the total of 144. How do I do that in order to have the percentage as close as possible to 28% for each company?

I'll exemplify:

If I just apply 28% for each company I get:

• Company A has 324 employers: 0.28 * 324 = 90.72
• Company B has 190 employers: 0.28 * 190 = 53.2

Again, I end up with decimal places. So I must figure out which ones I should round up, and which ones should I round down to get 144 total.

Note: For this example I only used two companies, but in the real problem I have 30 companies.

Answer 1

The problem can be framed as that of finding the closest integer approximation to a set of ratios. For instance, if you want to assign respectively A, B, C ≥ 0 members from 3 groups to match the ratios a, b, c ≥ 0 (with a + b + c = N > 0), where N = A + B + C > 0 is the total allocation desired, then you're approximating (a, b, c) by (A, B, C) with A, B and C restricted to integers.

One way to solve this may be to set it up as a least squares problem - that of minimizing |a - A|² + |b - B|² + |c - C|²; subject to the constraints A + B + C = N and A, B, C ≥ 0.

A necessary condition for the optimum is that it be a local optimum with respect discrete unit changes. For instance, (A,B,C) → (A+1,B-1,C), if B > 0 ... which entails the condition (A - B ≥ a - b - 1 or B = 0).

For the situation at hand, the optimization problem is:

|A - a|² + |B - b|²
a = 144×324/(324+190) ≅ 90.770, b = 144×190/(324+190) ≅ 53.230

which leads to the conditions:

A - B ≥ a - b - 1 ≅ +36.541 or B = 0
B - A ≥ b - a - 1 ≅ -38.541 or A = 0
A + B = 144

Since they are integers the inequalities can be strengthened:

A - B ≥ +37 or B = 0
B - A ≥ -38 or A = 0
A + B = 144

The boundary cases A = 0 and B = 0 are ruled out, since they don't satisfy all three conditions. So, you're left with 37 ≤ A - B ≤ 38 or, since A + B = 144: 181 ≤ 2A ≤ 182 or A = 91 ... and B = 53.

It is quite possible that this way of framing the problem may be equivalent, in terms of its results, to one of the algorithms cited in an earlier reply.

Answer 2

Since I originally posted this question I came across a description of this exact problem in Martin Fowler's book "Patterns of Enterprise Application Architecture" (page 489 and 490).

Martin talks about a "Matt Foemmel’s simple conundrum" of dividing 5 cents between two accounts, but must obey the distribution of 70% and 30%. This describes my problem in a much simpler way.

Here are the solutions he presents in his book to that problem:

• Perhaps the most common is to ignore it—after all, it’s only a penny here and there. However this tends to make accountants understandably nervous.
• When allocating you always do the last allocation by subtracting from what you’ve allocated so far. This avoids losing pennies, but you can get a cumulative amount of pennies on the last allocation.
• Allow users of a Money class to declare the rounding scheme when they call the method. This permits a programmer to say that the 70% case rounds up and the 30% rounds down. Things can get complicated when you allocate across ten accounts instead of two. You also have to remember to round. To encourage people to remember I’ve seen some Money classes force a rounding parameter into the multiply operation. Not only does this force the programmer to think about what rounding she needs, it also might remind her of the tests to write. However, it gets messy if you have a lot of tax calculations that all round the same way.
• My favorite solution: have an allocator function on the money. The parameter to the allocator is a list of numbers, representing the ratio to be allocated (it would look something like aMoney.allocate([7,3])). The allocator returns a list of monies, guaranteeing that no pennies get dropped by scattering them across the allocated monies in a way that looks pseudo-random from the outside. The allocator has faults: You have to remember to use it and any precise rules about where the pennies go are difficult to enforce.

Answer 3

There are many methods to perform apportionment, and no objective best method.

The following is in terms of states and seats rather than companies and people. Credit probably goes to Dr. Larry Bowen who is cited on the base site for the first link.

Hamilton’s Method
Also known as the Method of Largest Remainders and sometimes as Vinton's Method.

Procedure:

1. Calculate the Standard Divisor.
2. Calculate each state’s Standard Quota.
3. Initially assign each state its Lower Quota.
4. If there are surplus seats, give them, one at a time, to states in descending order of the fractional parts of their Standard Quota.

Here, the Standard Divisor can be found by dividing the total population (the sum of the population of each company) by the number of people you want to sample (144 in this case). The Standard Quota is the company's population divided by the Standard Divisor. The Lower Quota is this value rounded down. However, this method has some flaws.

Problems:

• The Alabama Paradox
  An increase in the total number of seats to be apportioned causes a state to lose a seat.
• The Population Paradox
  An increase in a state’s population can cause it to lose a seat.
• The New States Paradox
  Adding a new state with its fair share of seats can affect the number of seats due other states.

This is probably the most simple method to implement. Below are some other methods with their accompanying implementations and drawbacks.

Jefferson’s Method
Also known as the Method of Greatest Divisors and in Europe as the Method of d'Hondt or the Hagenbach-Bischoff Method.

Procedure:

1. Calculate the Standard Divisor.
2. Calculate each state’s Standard Quota.
3. Initially assign each state its Lower Quota.
4. Check to see if the sum of the Lower Quotas is equal to the correct number of seats to be apportioned.
   • If the sum of the Lower Quotas is equal to the correct number of seats to be apportioned, then apportion to each state the number of seats equal to its Lower Quota.
   • If the sum of the Lower Quotas is NOT equal to the correct number of seats to be apportioned, then, by trial and error, find a number, MD, called the Modified Divisor to use in place of the Standard Divisor so that when the Modified Quota, MQ, for each state (computed by dividing each State's Population by MD instead of SD) is rounded DOWN, the sum of all the rounded (down) Modified Quotas is the exact number of seats to be apportioned. (Note: The MD will always be smaller than the Standard Divisor.) These rounded (down) Modified Quotas are sometimes called Modified Lower Quotas. Apportion each state its Modified Lower Quota.

Problem:

• Violates the Quota Rule. (However, it can only violate Upper Quota—never Lower Quota.)

Webster’s Method
Also known as the Webster-Willcox Method as well as the Method of Major Fractions.

Procedure:

1. Calculate the Standard Divisor.
2. Calculate each state’s Standard Quota.
3. Initially assign a state its Lower Quota if the fractional part of its Standard Quota is less than 0.5.
   Initially assign a state its Upper Quota if the fractional part of its Standard Quota is greater than or equal to 0.5.
   [In other words, round down or up based on the arithmetic mean (average).]
4. Check to see if the sum of the Quotas (Lower and/or Upper from Step 3) is equal to the correct number of seats to be apportioned.
   • If the sum of the Quotas (Lower and/or Upper from Step 3) is equal to the correct number of seats to be apportioned, then apportion to each state the number of seats equal to its Quota (Lower or Upper from Step 3).
   • If the sum of the Quotas (Lower and/or Upper from Step 3) is NOT equal to the correct number of seats to be apportioned, then, by trial and error, find a number, MD, called the Modified Divisor to use in place of the Standard Divisor so that when the Modified Quota, MQ, for each state (computed by dividing each State's Population by MD instead of SD) is rounded based on the arithmetic mean (average) , the sum of all the rounded Modified Quotas is the exact number of seats to be apportioned. Apportion each state its Modified Rounded Quota.

Problem:

• Violates the Quota Rule. (However, violations are rare and are usually associated with contrived situations.)

Huntington-Hill Method
Also known as the Method of Equal Proportions.

• Current method used to apportion U.S. House
• Developed around 1911 by Joseph A. Hill, Chief Statistician of the Bureau of the Census and Edward V. Huntington, Professor of Mechanics & Mathematics, Harvard
• Preliminary terminology: The Geometric Mean

Procedure:

1. Calculate the Standard Divisor.
2. Calculate each state’s Standard Quota.
3. Initially assign a state its Lower Quota if the fractional part of its Standard Quota is less than the Geometric Mean of the two whole numbers that the Standard Quota is immediately between (for example, 16.47 is immediately between 16 and 17).
   Initially assign a state its Upper Quota if the fractional part of its Standard Quota is greater than or equal to the Geometric Mean of the two whole numbers that the Standard Quota is immediately between (for example, 16.47 is immediately between 16 and 17).
   [In other words, round down or up based on the geometric mean.]
4. Check to see if the sum of the Quotas (Lower and/or Upper from Step 3) is equal to the correct number of seats to be apportioned.
   • If the sum of the Quotas (Lower and/or Upper from Step 3) is equal to the correct number of seats to be apportioned, then apportion to each state the number of seats equal to its Quota (Lower or Upper from Step 3).
   • If the sum of the Quotas (Lower and/or Upper from Step 3) is NOT equal to the correct number of seats to be apportioned, then, by trial and error, find a number, MD, called the Modified Divisor to use in place of the Standard Divisor so that when the Modified Quota, MQ, for each state (computed by dividing each State's Population by MD instead of SD) is rounded based on the geometric mean, the sum of all the rounded Modified Quotas is the exact number of seats to be apportioned. Apportion each state its Modified Rounded Quota.

Problem:

• Violates the Quota Rule.

For reference, the Quota Rule :

Quota Rule

An apportionment method that always allocates only lower and/or upper bounds follows the quota rule.

Answer 4

My suggestion is to just take 28% of each company and round up to the nearest person.

In your case, you would go with 91 and 54. Admittedly, this does result in having a bit over 28%.

The most accurate method is as follows:

• Calculate the exact number that you want.
• Take 28% for each company and round down.
• Sort the companies in descending order by the remainder.
• Go through the list and choose the top n elements until you get exactly the number you want.