Rank-maximal (RM) allocation is a rule for fair division of indivisible items. Suppose we have to allocate some items among people. Each person can rank the items from best to worst. The RM rule says that we have to give as many people as possible their best (#1) item. Subject to that, we have to give as many people as possible their next-best (#2) item, and so on. 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).
Definition There are several items and several agents. Each agent has a total order on the items. Agents can be indifferent between some items; for each agent, we can partition the items to equivalence classes that contain items of the same rank. For example, If Alice's preference-relation is x > y,z > w, it means that Alice's 1st choice is x, which is better for her than all other items; Alice's 2nd choice is y and z, which are equally good in her eyes but not as good as x; and Alice's 3rd choice is w, which she considers worse than all other items. 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.
Example Three items, x y and z, have to be divided among three agents whose rankings are:
Alice: x > y > z Bob: x > y > z Carl: y > x > z In the allocation (x, y, z), Alice gets her 1st choice (x), Bob gets his 2nd choice (y), and Carl gets his 3rd choice (z). The rank-vector is thus (1,1,1). In the allocation (x,z,y), both Alice and Carl get their 1st choice and Bob gets his 3rd choice. 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. Hence, the allocation (x,z,y) is rank-maximal. Similarly, the allocation (z,x,y) is rank-maximal – it produces the same rank-vector (2,0,1).
Algorithms RM matchings were first studied by Robert Irving, who called them greedy matchings. He presented an algorithm that finds an RM matching in time O ( n 2 c 3 ) {\displaystyle O(n^{2}c^{3})} , where n is the number of agents and c is the largest length of a preference-list of an agent. Later, an improved algorithm was found, which runs in time O ( m ⋅ min ( n , C n ) ) {\displaystyle O(m\cdot \min(n,C{\sqrt {n}}))} , 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). The algorithm reduces the problem to maximum-cardinality matching. Intuitively, we would like to first find a maximum-cardinality matching using only edges of rank 1; then, extend this matching to a maximum-cardinality matching using only edges of ranks 1 and 2; then, extend this matching to a maximum-cardinality matching using only edges of ranks 1 2 and 3; and so on. The problem is that, if we pick the "wrong" maximum-cardinality matching for rank 1, then we might miss the optimal matching for rank 2. The algorithm of solves this problem using the Dulmage–Mendelsohn decomposition, which is a decomposition that uses a maximum-cardinality matching, but does not depend on which matching is chosen (the decomposition is the same for every maximum-cardinality matching chosen). It works in the following way.
Let G1 be the sub-graph of G containing only edges of rank 1 (the highest rank). Find a maximum-cardinality matching in G1, and use it to find the decomposition of G1 into E1, O1 and U1. One property of the decomposition is that every maximum-cardinality matching in G1 saturates all vertices in O1 and U1. Therefore, in a rank-maximal matching, all vertices in O1 and U1 are adjacent to an edge of rank 1. So we can remove from the graph all edges with rank 2 or higher adjacent to any of these vertices. Another property of the decomposition is that any maximum-cardinality matching in G1 contains only E1-O1 and U1-U1 edges. Therefore, we can remove all other edges (O1-O1 and O1-U1 edges) from the graph. Add to G1 all the edges with the next-highest rank. If there are no such edges, stop. Else, go back to step 2. A different solution, using maximum-weight matchings, attains a similar run-time: O ( m ⋅ min ( n + C , C n ) ) {\displaystyle O(m\cdot \min(n+C,C{\sqrt {n}}))} .
… excerpt ends here. Continue reading the full article.
