An algorithm for mess allocation.

Applied algorithms for a very real world problem : 



Report on new Mess Allocation Algorithm:

The two objectives of the algorithm are

•  Efficiency
    To ensure that maximum number of people get their desired choices

•  Equality
    So that over time, the maximum regret of any individual is minimized

The Algorithm

The algorithm tries to make sure that maximum people get their first choices.
However in case of tie algorithm gives preference to those who register
first.Among those who are left out (from getting their first choice), we try
to allocate the second choices to the maximum number again. The step is
repeated for the third, and fourth choices too. If any (at all) are still
left, they are randomly allocated.

How It Works

The algorithm has six rounds.

In the first round, allocation is done for a student only if his first choice
is available. For each caterer, students who opted for that caterer as their
first choice is allocated to the respective mess, as long as the number
allocated to a mess does not exceed its capacity.

If the number of students who opted for a particular mess as their first
choice exceeds the capacity of the mess, the students with higher regrets are
given more priority. Among students having equal regrets, the time of
registration is given priority.

In the second round, the same procedure is repeated. Only this time, we
concider the second choices of those students who have not been allocated in
the first round. A student gets allocated to a mess only if his second choice
is available. Students are prioritized in the decreasing order or regrets, and
based on time of registration among students having equal regrets.

Similar, third choices of those who remain unallocated are concidered in the
third round, and fourth choices of those who remain unallocated are concidered
in the fourth round.

If any student who registered for mess did not get allocated in the first four
rounds, he is randomly allocated to a mess in the fifth round. Students who
did not regsiter for mess are allocated randomly in the sixth round.

System Of Regrets ( Subject to change for next month )

Each student has a value called regret stored against him/her in the database.
This value is a measure of how much disappointed he/she would be by the
allocation.
Initially (in the first month of allocation), the regrets of all students will
be zero.

If a student is allotted to the mess of his first choice, + 0 is added to his
regret
If a student is allotted to the mess of her second choice, + 1 is added to his
regret
If a student is allotted to the mess of his third choice, + 2 is added to his
regret
If a student is allotted to the mess of his first choice, + 3 is added to his
regret

For those dining in Himalaya, if a student does not get any mess of his choice
(if he gets randomly allotted to a mess even after registering as none of his
4 choices were available), +4 is added to his regret.

The regrets of each student keep on accumulating every month. Now, higher the
regret of a student, the more he is disappointed. To ensure equality, a
student with higher regret is given priority over a student with lower regret
during allocation.


Conclusion

The new algorithm is found to be much more efficient that the one presently
being used which is solely based on first come - first serve principle.

>  Maximum number of students gets their first choice. Among those remaining,
it attempts to maximize the number that gets second, third, and fourth choices
too (if any).

>  The regrets of students over time are balanced in an optimal way
Regards

{ New Mess Allocation Algorithm:
Developed by Hareesh R, Institute Web Operations Core 2009 – 2010 }