Rank-maximal allocation: Difference between revisions
Erel Segal (talk | contribs) No edit summary |
Erel Segal (talk | contribs) No edit summary |
||
| Line 41: | Line 41: | ||
Both maximum-cardinality RM matching and fair matching can be found by reduction to maximum-weight matching. <ref name=":0" /> |
Both maximum-cardinality RM matching and fair matching can be found by reduction to maximum-weight matching. <ref name=":0" /> |
||
3. 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. Each item has an upper quota denoting the an upper bound on the number of different agents it can be allocated to. It was first studied by Melhorn and Michail, who gave an algorithm with run-time <math>O(C n m \log(n^2/m)\log(n))</math>.<ref>{{Cite web|url=https://pure.mpg.de/rest/items/item_2344037/component/file_2344036/content|title=Network Problems with Non-Polynomial Weights and Applications|last=Kurt Mehlhorn and Dimitrios Michail|first=|date=2005|website=|archive-url=|archive-date=|dead-url=|access-date=}}</ref> There is an improved algorithm with run-time <math>O(m\cdot \min(B, C \sqrt{B}))</math>, where ''B'' is the minimum of the sum-of-quotas of the agents and the sum-of-quotas of the items.<ref>{{Cite journal|last=Paluch|first=Katarzyna|date=2013-05-22|title=Capacitated Rank-Maximal Matchings|url=https://link.springer.com/chapter/10.1007/978-3-642-38233-8_27|journal=Algorithms and Complexity|language=en|publisher=Springer, Berlin, Heidelberg|pages=324–335|doi=10.1007/978-3-642-38233-8_27}}</ref> It is based on an extension of the [[Gallai-Edmonds decomposition]] to multi-edge matchings. |
|||
3. In the '''capacitated RM matching''' problem, each agent has a lower and an upper capacity denoting a lower and upper bound on the total number of items he should get. Each item has a lower and upper quota denoting the a lower and upper bound on the number of different agents it can be allocated to. |
|||
== See also == |
== See also == |
||
| Line 47: | Line 47: | ||
*[[Fair item assignment]] |
*[[Fair item assignment]] |
||
*[[Stable matching]] |
*[[Stable matching]] |
||
*[[Envy-free matching]] |
|||
== References == |
== References == |
||
Revision as of 12:28, 23 January 2019
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 are 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 , where n is the number of agents and c is the largest length of a preference-list of an agent.[1]
Later, an improved algorithm was found, which runs 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). [2]
A different solution, using maximum-weight matchings, attains a similar run-time - .[3]
Variants
The problem has several variants.
1. In maximum-cardinality RM matching, the goal is to find, among all different RM matchings, the one with the maximum number of matchings.
2. 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.
Both maximum-cardinality RM matching and fair matching can be found by reduction to maximum-weight matching. [3]
3. 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. Each item has an upper quota denoting the an upper bound on the number of different agents it can be allocated to. It was first studied by Melhorn and Michail, who gave an algorithm with run-time .[4] There is an improved algorithm with run-time , where B is the minimum of the sum-of-quotas of the agents and the sum-of-quotas of the items.[5] It is based on an extension of the Gallai-Edmonds decomposition to multi-edge matchings.
See also
References
- ^ Irving, Robert W. (2003). Greedy matchings. University of Glasgow. pp. Tr-2003-136.
{{cite book}}: CS1 maint: location missing publisher (link) - ^ Irving, Robert W.; Kavitha, Telikepalli; Mehlhorn, Kurt; Michail, Dimitrios; Paluch, Katarzyna E. (2006-10-01). "Rank-maximal Matchings". ACM Trans. Algorithms. 2 (4): 602–610. doi:10.1145/1198513.1198520. ISSN 1549-6325.
- ^ a b Michail, Dimitrios (2007-12-10). "Reducing rank-maximal to maximum weight matching". Theoretical Computer Science. 389 (1): 125–132. doi:10.1016/j.tcs.2007.08.004. ISSN 0304-3975.
- ^ Kurt Mehlhorn and Dimitrios Michail (2005). "Network Problems with Non-Polynomial Weights and Applications".
{{cite web}}: Cite has empty unknown parameter:|dead-url=(help) - ^ Paluch, Katarzyna (2013-05-22). "Capacitated Rank-Maximal Matchings". Algorithms and Complexity. Springer, Berlin, Heidelberg: 324–335. doi:10.1007/978-3-642-38233-8_27.