An interesting problem was described to me by a friend last night.
Let us assume that there is a semi-fictional school, where a number of students start studying every year. The number of new students ranges between 70 and 150 every year.
The students can pick more than the strictly required number of classes during their few final terms. They get rated in all their optional classes, and just before graduating the students have the option of keeping some of the optional classes and aborting others.
Each time they pick or drop one of the optional classes, there is a system in place that immediatelly replies with their placement in the graduation list, depending on their final score in the selected set of classes.
The school now uses a very peculiar algorithm for selecting a number of the graduating students to cover some of the prestiguous positions for teaching assistants. There are 5 types of positions: A, B, C, D and E. The academic prestige, future options and monetary gains from each type of position are very well-defined, and there is a clear order of preference: A > B > C > D > E.
The peculiar algorithm for picking graduating students for each type of these teaching assistant positions is:
- After all students have picked a set of class grades, and their graduation placement has been fixed, a ballot is drawn between the numbers 15, 16, 17, 18, 29 and 20.
- The number N drawn from the ballot is used to split the graduating students in teams of N members, starting from the one with the highest grades as student #1, the second as #2, … the N-th as the last member of the first team, the (N+1)-th as the first member of the second team, and so on.
- Then the first five students of each team are chosen for the five job position types: the first team member for an A position, the second for a B position, etc.
This is a very strange algorithm for selecting students for the five types teaching assistant positions. At first glance someone may be tempted to say that it is `fair’, because of the ballot. My intuition says this isn’t true, however. So the questions this discussion triggered were:
- How “fair” is this selection algorithm?
- Are there positions in the graduation order of all students that are favored a lot by this sort of selection process?
- If there are positions that do have an advantage, how many are they and what is their overall distribution in the range of [1..150] students of each year?
I spent a bit of time last night trying to work this out, and I think I have an answer now. Before I post how I tried to answer, what are your thoughts? How would you approach this ‘problem’?