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.
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 , 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] 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-cardniality matching using only edges of ranks 1 and 2; then, extend this matching to a maximum-cardniality 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 [2] 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.
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 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. It is based on an extension of the Gallai–Edmonds decomposition to multi-edge matchings.[5]
The assignment problem is a fundamental combinatorial optimization problem. In its most general form, the problem is as follows:
In optimization theory, maximum flow problems involve finding a feasible flow through a flow network that obtains the maximum possible flow rate.
In the mathematical discipline of graph theory, a matching or independent edge set in an undirected graph is a set of edges without common vertices. In other words, a subset of the edges is a matching if each vertex appears in at most one edge of that matching. Finding a matching in a bipartite graph can be treated as a network flow problem.
In mathematics, in the areas of order theory and combinatorics, Dilworth's theorem characterizes the width of any finite partially ordered set in terms of a partition of the order into a minimum number of chains. It is named for the mathematician Robert P. Dilworth (1950).
The Hungarian method is a combinatorial optimization algorithm that solves the assignment problem in polynomial time and which anticipated later primal–dual methods. It was developed and published in 1955 by Harold Kuhn, who gave the name "Hungarian method" because the algorithm was largely based on the earlier works of two Hungarian mathematicians: Dénes Kőnig and Jenő Egerváry.
In graph theory, the Dulmage–Mendelsohn decomposition is a partition of the vertices of a bipartite graph into subsets, with the property that two adjacent vertices belong to the same subset if and only if they are paired with each other in a perfect matching of the graph. It is named after A. L. Dulmage and Nathan Mendelsohn, who published it in 1958. A generalization to any graph is the Edmonds–Gallai decomposition, using the Blossom algorithm.
Competitive equilibrium is a concept of economic equilibrium, introduced by Kenneth Arrow and Gérard Debreu in 1951, appropriate for the analysis of commodity markets with flexible prices and many traders, and serving as the benchmark of efficiency in economic analysis. It relies crucially on the assumption of a competitive environment where each trader decides upon a quantity that is so small compared to the total quantity traded in the market that their individual transactions have no influence on the prices. Competitive markets are an ideal standard by which other market structures are evaluated.
In the mathematical theory of matroids, the rank of a matroid is the maximum size of an independent set in the matroid. The rank of a subset S of elements of the matroid is, similarly, the maximum size of an independent subset of S, and the rank function of the matroid maps sets of elements to their ranks.
Rental harmony is a kind of a fair division problem in which indivisible items and a fixed monetary cost have to be divided simultaneously. The housemates problem and room-assignment-rent-division are alternative names to the same problem.
Resource monotonicity is a principle of fair division. It says that, if there are more resources to share, then all agents should be weakly better off; no agent should lose from the increase in resources. The RM principle has been studied in various division problems.
Envy-free (EF) item allocation is a fair item allocation problem, in which the fairness criterion is envy-freeness - each agent should receive a bundle that they believe to be at least as good as the bundle of any other agent.
The envy-graph procedure is a procedure for fair item allocation. It can be used by several people who want to divide among them several discrete items, such as heirlooms, sweets, or seats in a class.
Fair random assignment is a kind of a fair division problem.
A simultaneous eating algorithm(SE) is an algorithm for allocating divisible objects among agents with ordinal preferences. "Ordinal preferences" means that each agent can rank the items from best to worst, but cannot (or does not want to) specify a numeric value for each item. The SE allocation satisfies SD-efficiency - a weak ordinal variant of Pareto-efficiency (it means that the allocation is Pareto-efficient for at least one vector of additive utility functions consistent with the agents' item rankings).
In economics and social choice theory, an envy-free matching (EFM) is a matching between people to "things", which is envy-free in the sense that no person would like to switch his "thing" with that of another person. This term has been used in several different contexts.
In graph theory, a maximally matchable edge in a graph is an edge that is included in at least one maximum-cardinality matching in the graph. An alternative term is allowed edge.
Maximin share (MMS) is a criterion of fair item allocation. Given a set of items with different values, the 1-out-of-n maximin-share is the maximum value that can be gained by partitioning the items into parts and taking the part with the minimum value. An allocation of items among agents with different valuations is called MMS-fair if each agent gets a bundle that is at least as good as his/her 1-out-of-n maximin-share. MMS fairness is a relaxation of the criterion of proportionality - each agent gets a bundle that is at least as good as the equal split ( of every resource). Proportionality can be guaranteed when the items are divisible, but not when they are indivisible, even if all agents have identical valuations. In contrast, MMS fairness can always be guaranteed to identical agents, so it is a natural alternative to proportionality even when the agents are different.
Round robin is a procedure for fair item allocation. It can be used to allocate several indivisible items among several people, such that the allocation is "almost" envy-free: each agent believes that the bundle he received is at least as good as the bundle of any other agent, when at most one item is removed from the other bundle. In sports, the round-robin procedure is called a draft.
Birkhoff's algorithm is an algorithm for decomposing a bistochastic matrix into a convex combination of permutation matrices. It was published by Garrett Birkhoff in 1946. It has many applications. One such application is for the problem of fair random assignment: given a randomized allocation of items, Birkhoff's algorithm can decompose it into a lottery on deterministic allocations.
In economics and computer science, Fractional Pareto efficiency or Fractional Pareto optimality (fPO) is a variant of Pareto efficiency used in the setting of fair allocation of discrete objects. An allocation of objects is called discrete if each item is wholly allocated to a single agent; it is called fractional if some objects are split among two or more agents. A discrete allocation is called Pareto-efficient (PO) if it is not Pareto-dominated by any discrete allocation; it is called fractionally Pareto-efficient (fPO) if it is not Pareto-dominated by any discrete or fractional allocation. So fPO is a stronger requirement than PO: every fPO allocation is PO, but not every PO allocation is fPO.
References
↑ Irving, Robert W. (2003). Greedy matchings. University of Glasgow. pp.Tr–2003–136. CiteSeerX10.1.1.119.1747.{{cite book}}: CS1 maint: location missing publisher (link)
↑ Paluch, Katarzyna (22 May 2013). "Capacitated Rank-Maximal Matchings". Algorithms and Complexity. Lecture Notes in Computer Science. Vol.7878. Springer, Berlin, Heidelberg. pp.324–335. doi:10.1007/978-3-642-38233-8_27. ISBN978-3-642-38232-1.
This page is based on this Wikipedia article Text is available under the CC BY-SA 4.0 license; additional terms may apply. Images, videos and audio are available under their respective licenses.
