Help
Overview
The profile matching web application allows you to assign applicants to posts, e.g. students to projects, where students have a preference over the projects they wish to undertake.Input
Below we highlight the format required for the "Preference lists" and "Post capacities" input data form elements.
- Preference lists
-
The preference lists consist of a whitespace (tabs or spaces) separated list of integers that represent an applicants preference over a particular
set of posts. For example:
1 2 5 9 4 5 6 7
represents the preference lists of two applicants. The first applicant ranks posts 1, 2, 5 and 9, and prefers post 1 to 2, 2 to 5, and 5 to 9. The second applicant ranks posts 4, 5, 6, and 7, and prefers post 4 to 5, 5 to 6 and 6 to 7. The number of lines here must match the number of applicants specified. - Post capacities
-
Each post capacity appears on a separate lines. For example
1 2 1
represents the capacities of post 1, 2 and 3, where post 1 has capacity 1, post 2 has capacity 2, and post 3 has capacity 1. Here the number of lines must corresponds to the number of posts specified.
Output
The software runs several different matching algorithms whose characteristics are detailed below:
- Greedy
- The greedy matching maximises the number of applicants matched and subject to this maximises the number of applicants that obtain their first choice, and subject to this, maximises the number of applicants that get their second choice, and so on.
- Generous
- The generous matching maximises the number of applicants matched and subject to this minimises the number of applicants that obtain their rth choice, and subject to this, minimises the number of applicants that obtain their (r-1)th choice, and so on, where r is the maximum length of an applicant's preference list.
- Greedy-Generous
- Suppose that the generous matching had a profile such that no applicant obtained worse than their rth choice Then the greedy-generous matching is a matching that first maximises the number of applicants matched but has no applicant assign to their rth choice or worse, then subject to this, the number of applicants that obtain their first choice is maximised, and subject to this, the number of applicants that obtain their second choice is maximised, and so on.
- Min Cost
- The cost of a matching M is the sum of the ranks of the assigned projects in the applicants' preference lists (e.g., if a matching gives three applicants their first choice, two applicants their second choice and one student their third choice, then its cost is 3*1+2*2+1*3=10). Then the minimum cost matching is one that first maximises the number of applicants matched and subject to this minimises the cost.
- Naive
- This matching strategy is based on a first come first served model. Using this approach does not guarantee that the optimal number of applicants will be matched. It is shown here only for illustration purposes.