Rank-maximal (RM) allocation is a rule for fair division of indivisible items.
In the special case in which each person should receive a single item (for example, when the "items" are tasks and each task has to be done by a single person), the problem is called rank-maximal matching or greedy matching.
The idea is similar to that of utilitarian cake-cutting, where the goal is to maximize the sum of utilities of all participants.
However, the utilitarian rule works with cardinal (numeric) utility functions, while the RM rule works with ordinal utilities (rankings).
For every allocation of items to the agents, we construct its rank-vector as follows.
Element #1 in the vector is the total number of items that are 1st-choice for their owners; Element #2 is the total number of items that are 2nd-choice for their owners; and so on.
A rank-maximal allocation is one in which the rank-vector is maximum, in lexicographic order.
The rank-vector is thus (2,0,1), which is lexicographically higher than (1,1,1) – it gives more people their 1st choice.
It is easy to check that no allocation produces a lexicographically higher rank-vector.
He presented an algorithm that finds an RM matching in time
, where m is the total length of all preference-lists (total number of edges in the graph), and C is the maximal rank of an item used in an RM matching (i.e., the maximal number of non-zero elements in an optimal rank vector).
A different solution, using maximum-weight matchings, attains a similar run-time:
In fair matching, the goal is to find a maximum-cardinality matching such that the minimum number of edges of rank r are used, given that - the minimum number of edges of rank r−1 are used, and so on.
In the capacitated RM matching problem, each agent has an upper capacity denoting an upper bound on the total number of items he should get.
It was first studied by Melhorn and Michail, who gave an algorithm with run-time