You are the accommodations officer for a university and you have 400 applicants for 100 places in hall. Each room is shared by two students so there are 50 rooms.
There is a complicating factor: the Dean has given you a list of students who are ″incompatible pairs″ and you are instructed to make certain that none of these pairs is share a room.
This, everyone agrees is simple to achieve. Choose 100 students, allocate them to rooms then check the list of incompatible students and make sure that changes are made to move, or reject and replace, at least one from each incompatible pair.
What is not simple is to produce a formula that would make this possible from scratch.
It’s easy to make a process but a process is not a formula.
divide into pairs,
allocate each pair to a room,
check the incompatible list – if a pair is on the list (a positive match), [take an action from a pick list]; if a pair is not on the list, move onto the next pair.
When there are no more positive matches, the task is complete.
There are two central issues. The first is that there is a significant human input into the decision making processes. It is not a pure algorithm.
That human input starts with deciding to exclude a significant proportion of the 400. What basis is there for exclusion? Or do the humans behave differently: do they look for qualities for inclusion and then score those against some criteria that we don’t know.
The reason that it seems to be a massive problem is that the number of options available is huge: the Institute says ″Indeed, the total number of ways of choosing one hundred students from the four hundred applicants is greater than the number of atoms in the known universe!″
So, there are criteria.