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’?

adamoIt depends on the definition of “fair”. So fair for who? The armed forces use a similar algorithm for placing military academy graduates to certain divisions, for they want a fair distribution of good and bad graduates. Their aim is to avoid having all the good graduates choose Communications (Διαβιβάσεις) leaving infantry (Πεζικό) with the worst ones.

keramidaPost authoradamo: Of course, “fair” is a veyr broad term in this case. I should have been more clear.

By allowing a final moment choice between optional classes, the students pick a placement in the [1..150] range in an effort to “game” the final result. How far can their gaming get them though? My intuition said there’s a fair chance this may be possible.

[Yes, a very similar algorithm is used in the military academy :)]

myleAs I was skimming your blog, I didn’t stumble on your solution. Given that the problem was sounding interesting, I tried to find it out on my own.

It reminds of a game theory problem, but what is asked is some statistics and not the best strategy.

Well, I am not sure if I have well understood the problem, but below is the hasty solution I came up with, to demonstrate my feeling that indeed, this algorithm is not fair as far as each position of the final rankings is concerned.

team = []

number_of_teams = 5

number_of_students = 150

for i in range(number_of_teams):

team.append([])

# for each ballot, find the favourable places

for ballot in range(15, 21):

n = 1

while (n <= number_of_students):

# how many students remain in this team

# that could belong to the first five

remaining_students = min(number_of_students – n + 1, number_of_teams);

for j in range(remaining_students):

# first student of the team

team[j].append(n+j)

# proceed to the next team

n += ballot

#for i in range(number_of_teams):

# team[i].sort()

print(team)

# initialize a double vector with zeros

# there has to be a better way

histogram = []

for i in range(number_of_teams):

histogram.append([])

for j in range(number_of_students):

histogram[i].append(0)

for i in range(number_of_teams):

for x in team[i]:

# start indexing from 1 (human readable)

# we already know that no student can achieve to be 0th in his year

histogram[i][x-1] += 1

print(histogram)