The algorithm takes as input a matrix whose lines are the users and whose columns are the slots.
The matrix is filled in with non-negative integers describing the wishes of the users, which we can call "grades". A small number means that the user would be very satisfied if put in this slot, and a high number means that the user would be disappointed if put in this slot. For a given arrangement of the users in the slots, one can determine a "penalty": it is the sum of the squares of the "grades" that each user has considering in which slot he/she is placed.
A maximum and minimum number of users is associated to each slot. We use the Hungarian algorithm to minimize the penalty under these constraints.
To ensure that everyone has a fair chance of having his/her favorite slot, some rules must be imposed on the choices of the users. Indeed, one could manipulate the results by setting all slots to "hated" but one. A simple solution to this problem is to impose that the user strictly orders all the slots. However, this can be uncomfortable from the user’s point of view, and besides no default value can replace a user who chooses not to set his/her wishes.
Therefore, another solution was found. Assume there are n slots. Then, the gradation from wanted to hated is 0, 1, 2,...n-1. Then the rule goes as follows:
Therefore, the default setting of the wishes is to have grade 0 for each slots. This corresponds to somebody having no preferences.
When the users are setting their wishes, the sliders automatically prevent unfair wishes.
Initially this algorithm was intended to put people in slots for an oral exam. It could happen that some people simply mustn't be put in some slots because they have another exam at this time. In such a case, it’s nice to be able to avoid the problem by putting a very high grade to the slots that the person mustn't be put in. Therefore, the administrator has access to the choices of all the users and can modify them upon request (see Administration page).
To ensure that the users don’t change their wishes to trick the system, it’s good if they don’t know what the preferences of the other users are. Therefore, a unique key is randomly generated for each user. An url is then created using this key, which gives to the user a private access to his/her wish page.
The aim of the algorithm is to arrange people in various slots. It’s not the aim to put all people in the same slot.
It’s not that easy to modify the algorithm to put each person in two slots.
If you are not sure how to use some features on the pages of the wish website, try keeping the mouse on this feature. In most cases, a "tip" can appear informing you about how the feature works.
Before setting your wishes, you might want to take a look at the Rules to ensure fair choices above.
Online/offline When it is not possible to contact the participants by email, the website can still be used in its "offline" shape. The offline page is very similar to the administration page, except the pseudocode is not automatically written down (though there is an example to help). Please have a look at the help about the admin page for more info.
Number of slots If you give too many slots, it will become a bit inconvenient for the users to set their wishes. If you are organizing an oral exam with a lot of students, a good solution is to gather three passage times in one slot and fit three people in the slot.
Mailing list The mailing list should contain the e-mail of each of the participants to the event. If the administrator intends to be put in a slot to, his/her mail should be on the list too.
This list will be used to send the following mails:
Once an event has been created, the administrator receives an e-mail containing a link to the admin page. Once the administrator accesses this page, it is possible to send the invitation mail to all the participants, who will receive a private url to a page allowing them to set their choices.
The administration pages in the online and offline versions are very similar. The main item is a "problem settings" area, allowing to input all the parameters of the problem. There are as well two buttons, one to save the settings and the other ("compute assignation") to perform the computations and assign the participants in various slots. The "Assignation" area presents the results. In the online case, additional features allow to send news to the participants or to send them a reminder if they haven't participated yet.
Problem settings This area contains both the informations about the slots and the participants. Indeed, the list of the slots names is given along with the minimal and maximal number of participants allowed in each one. The list of the participants names/emails along with their preferences is given as well. In the online case, this area is automatically filled in with the parameters defined when creating the page and automatically updated when the users change their wishes. This area can always be modified by the administrator, who can add and remove slots or participants, change the quotas in the slots and change the wishes of the participants if needed (for instance, when a person has two exams on the same day, the administrator can but a high grade to the slots which are inconvenient for the student, so that he/she cannot fall into these). In the offline case, the administrator must enter the complete settings, including the wishes of the participants.
Save When the admin modifies the problem settings, it might affect some participants. This button allows to save the settings. In the online case, after saving the new data to the server, it will propose you to send mails to participents that has been added or to inform all the participants that a slot have been modified.
Send reminder In the online case, the admin can send a reminder to users who didn't yet set their wishes.
Compute assignation In both the online and offline cases, this button allows to compute the results and display them in the "assignation" area.
Assignation area This area is split in two parts: the "statistics" and the actual "results". The results give for each participant the title of the slot where he/she has been placed as well as the place it hold in his/her "wish list" (0 is best). The statistics describe for each slot as well as in total
Send results This button allows to send a personal email to each participant to give them their result. It will as well send a mail to the admin of the event with all the assignations.
Contact us on GitHub: github.com/agepoly/wish