Robust algorithm to assign chaperones to students

Question

Here's the problem: Given 4 groups of students of sizes A, B, C and D, and a total of k chaperones, devise an algorithm for assigning chaperones to students in near-equal proportions.

You can't just give the groups k*A/N, k*B/N, k*C/N, k*D/N chaperones, because the number of chaperones has to be a positive integer. And you can't just round, because then you might not get the right number of chaperones. So my idea is that you throw out the fractional part, and give the integer part to each group, so do integer division. Then you might have some left over chaperones, but at most 3, so give them to the groups with the biggest remainders.

Then, the interviewer pointed out that there's a problem with this. If you add another chaperone, so increase k to k+1, then it can happen that one of the groups actually loses a chaperone this way. She gave me an example, but I don't remember it.

Can anyone come up with an algorithm that avoids this problem?

Answer 1

The problem you're trying to solve is generally known as an apportionment problem or vote allocation problem. This is the same problem as assigning the number of seats in the US House of Representatives to each state.

The problem of robustness that your approach (known as Hamilton's method or the method of largest remainder) fails to have is known as the Alabama Paradox. From the Wikipedia article, "The Alabama paradox was discovered in 1880, when it was found that increasing the total number of seats would decrease Alabama's share from 8 to 7."

Historically, at least four different methods have been used in US: Jefferson's method, Hamilton's method, Webster's method and the current Huntington-Hill's method used since 1941.

The idea behind these latter methods is the following. Let D = N/k, the total population divided by the number of seats/chaperones. Then let d = D, and modify d until the rounding k_i = round(G_i/d) adds up to the correct number of seats, i.e.

   round(G_1/d) + round(G_2/d) + ... + round(G_m/d) = k

The catch is in how the function round works. Webster's approach rounds in the usual sense: weakly above .5 go up and strictly below .5 go down, which is rather much like using an arithmetic mean. The Huntington-Hill method is based on the idea of using a geometric mean instead. There is a nice summary of these methods here. Note that all of these divisor algorithms are flawed in that they violate the Quota Rule: a state is not guaranteed to get at least floor(G_m/D) representatives.

If you want to play around with this more, there is an excellent article about this on Cut The Knot complete with history, equations, and fun applets.

Answer 2

Given 4 groups of students of sizes A, B, C and D, and a total of k chaperones, devise an algorithm for assigning chaperones to students in near-equal proportions.

Here is an algorithm that will solve the question very simply:

1. Begin with an apportionment of 0 chaperons per group. If any groups have no students in them, then throw out that group, as no chaperon will be assigned to such a group.

2. If the total number of assigned chaperons is equal to k, then we are done.

3. Assign one chaperon to one group. The group that is to receive the chaperon is the one with the lowest chaperons per student ratio. In the case of a tie, select the group with the most students among those with the lowest chaperons per student ratio. If there is still a tie, then from among those selected, choose the group that is alphabetically the first.

4. Go to step 2.

It makes unambiguous deterministic assignments. The proportions will be as nearly equal as the values allow. Increasing k will not decrease the assignments to any group, since it effectively just causes an additional iteration to occur and no iterations decrease any group's assignments.

It is possible for two groups of the same size to have a different number of chaperons, but this cannot be corrected without restating the problem to allow modifications to k. In no case will two groups of the same size differ in their assignments by more than 1.

All of the algorithms in the other answer for assigning representation to states are needlessly complicated, and are designed to minimize the number of computational steps performed (by doing numerical calculations rather than incremental assignments). The algorithm that I have given is very simple when run on a computer.