|
Rank-maximal Matching
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 ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Fair Division
Fair division is the problem in game theory of dividing a set of resources among several people who have an entitlement to them so that each person receives their due share. That problem arises in various real-world settings such as division of inheritance, partnership dissolutions, divorce settlements, electronic frequency allocation, airport traffic management, and exploitation of Earth observation satellites. It is an active research area in mathematics, economics (especially social choice theory), dispute resolution, etc. The central tenet of fair division is that such a division should be performed by the players themselves, maybe using a mediator but certainly not an arbiter as only the players really know how they value the goods. The archetypal fair division algorithm is divide and choose. It demonstrates that two agents with different tastes can divide a cake such that each of them believes that he got the best piece. The research in fair division can be seen as an exten ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Utilitarian Cake-cutting
Utilitarian cake-cutting (also called maxsum cake-cutting) is a rule for dividing a heterogeneous resource, such as a cake or a land-estate, among several partners with different cardinal utility functions, such that the ''sum'' of the utilities of the partners is as large as possible. It is a special case of the utilitarian social choice rule. Utilitarian cake-cutting is often not "fair"; hence, utilitarianism is often in conflict with fair cake-cutting. Example Consider a cake with two parts: chocolate and vanilla, and two partners: Alice and George, with the following valuations: The utilitarian rule gives each part to the partner with the highest utility. In this case, the utilitarian rule gives the entire chocolate to Alice and the entire Vanilla to George. The maxsum is 13. The utilitarian division is not fair: it is not proportional since George receives less than half the total cake value, and it is not envy-free since George envies Alice. Notation The cake is calle ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Cardinal Utility
In economics, a cardinal utility function or scale is a utility index that preserves preference orderings uniquely up to positive affine transformations. Two utility indices are related by an affine transformation if for the value u(x_i) of one index ''u'', occurring at any quantity x_i of the goods bundle being evaluated, the corresponding value v(x_i) of the other index ''v'' satisfies a relationship of the form :v(x_i) = au(x_i) + b\!, for fixed constants ''a'' and ''b''. Thus the utility functions themselves are related by :v(x) = au(x) + b. The two indices differ only with respect to scale and origin. Thus if one is concave, so is the other, in which case there is often said to be diminishing marginal utility. Thus the use of cardinal utility imposes the assumption that levels of absolute satisfaction exist, so that the magnitudes of increments to satisfaction can be compared across different situations. In consumer choice theory, ordinal utility with its weaker assumption ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Ordinal Utility
In economics, an ordinal utility function is a function representing the preferences of an agent on an ordinal scale. Ordinal utility theory claims that it is only meaningful to ask which option is better than the other, but it is meaningless to ask ''how much'' better it is or how good it is. All of the theory of consumer decision-making under conditions of certainty can be, and typically is, expressed in terms of ordinal utility. For example, suppose George tells us that "I prefer A to B and B to C". George's preferences can be represented by a function ''u'' such that: :u(A)=9, u(B)=8, u(C)=1 But critics of cardinal utility claim the only meaningful message of this function is the order u(A)>u(B)>u(C); the actual numbers are meaningless. Hence, George's preferences can also be represented by the following function ''v'': :v(A)=9, v(B)=2, v(C)=1 The functions ''u'' and ''v'' are ordinally equivalent – they represent George's preferences equally well. Ordinal utility contrasts ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Total Order
In mathematics, a total or linear order is a partial order in which any two elements are comparable. That is, a total order is a binary relation \leq on some set X, which satisfies the following for all a, b and c in X: # a \leq a ( reflexive). # If a \leq b and b \leq c then a \leq c ( transitive). # If a \leq b and b \leq a then a = b ( antisymmetric). # a \leq b or b \leq a (strongly connected, formerly called total). Total orders are sometimes also called simple, connex, or full orders. A set equipped with a total order is a totally ordered set; the terms simply ordered set, linearly ordered set, and loset are also used. The term ''chain'' is sometimes defined as a synonym of ''totally ordered set'', but refers generally to some sort of totally ordered subsets of a given partially ordered set. An extension of a given partial order to a total order is called a linear extension of that partial order. Strict and non-strict total orders A on a set X is a strict partial ord ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Maximum Cardinality Matching
Maximum cardinality matching is a fundamental problem in graph theory. We are given a graph , and the goal is to find a matching containing as many edges as possible; that is, a maximum cardinality subset of the edges such that each vertex is adjacent to at most one edge of the subset. As each edge will cover exactly two vertices, this problem is equivalent to the task of finding a matching that covers as many vertices as possible. An important special case of the maximum cardinality matching problem is when is a bipartite graph, whose vertices are partitioned between left vertices in and right vertices in , and edges in always connect a left vertex to a right vertex. In this case, the problem can be efficiently solved with simpler algorithms than in the general case. Algorithms for bipartite graphs Flow-based algorithm The simplest way to compute a maximum cardinality matching is to follow the Ford–Fulkerson algorithm. This algorithm solves the more general problem ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Dulmage–Mendelsohn Decomposition
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. Construction The Dulmage-Mendelshon decomposition can be constructed as follows. (it is attributed to who in turn attribute it to ). Let ''G'' be a bipartite graph, ''M'' a maximum-cardinality matching in ''G'', and ''V''0 the set of vertices of ''G'' unmatched by ''M'' (the "free vertices"). Then ''G'' can be partitioned into three parts: * ''E'' - the ''even'' vertices - the vertices reachable from ''V''0 by an ''M''-alternating path of even length. * ''O'' - the ''odd'' vertices - the vertices reachable from ''V''0 by an '' ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Maximum-weight Matching
In computer science and graph theory, the maximum weight matching problem is the problem of finding, in a weighted graph, a matching in which the sum of weights is maximized. A special case of it is the assignment problem, in which the input is restricted to be a bipartite graph, and the matching constrained to be have cardinality that of the smaller of the two partitions. Another special case is the problem of finding a maximum cardinality matching on an unweighted graph: this corresponds to the case where all edge weights are the same. Algorithms There is a O(V^E) time algorithm to find a maximum matching or a maximum weight matching in a graph that is not bipartite; it is due to Jack Edmonds, is called the ''paths, trees, and flowers'' method or simply Edmonds' algorithm, and uses bidirected edges. A generalization of the same technique can also be used to find maximum independent sets in claw-free graphs. More elaborate algorithms exist and are reviewed by Duan and Pettie ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Gallai–Edmonds Decomposition
In graph theory, the Gallai–Edmonds decomposition is a partition of the vertices of a graph into three subsets which provides information on the structure of maximum matchings in the graph. Tibor Gallai and Jack Edmonds independently discovered it and proved its key properties. The Gallai–Edmonds decomposition of a graph can be found using the blossom algorithm. Properties Given a graph G, its Gallai–Edmonds decomposition consists of three disjoint sets of vertices, A(G), C(G), and D(G), whose union is V(G): the set of all vertices of G. First, the vertices of G are divided into ''essential vertices'' (vertices which are covered by every maximum matching in G) and ''inessential vertices'' (vertices which are left uncovered by at least one maximum matching in G). The set D(G) is defined to contain all the inessential vertices. Essential vertices are split into A(G) and C(G): the set A(G) is defined to contain all essential vertices adjacent to at least one vertex of D(G) ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Fair Item Assignment
Fair item allocation is a kind of a fair division problem in which the items to divide are ''discrete'' rather than continuous. The items have to be divided among several partners who value them differently, and each item has to be given as a whole to a single person. This situation arises in various real-life scenarios: * Several heirs want to divide the inherited property, which contains e.g. a house, a car, a piano and several paintings. * Several lecturers want to divide the courses given in their faculty. Each lecturer can teach one or more whole courses. *White elephant gift exchange parties The indivisibility of the items implies that a fair division may not be possible. As an extreme example, if there is only a single item (e.g. a house), it must be given to a single partner, but this is not fair to the other partners. This is in contrast to the fair cake-cutting problem, where the dividend is divisible and a fair division always exists. In some cases, the indivisibility pr ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Stable Matching
In mathematics, economics, and computer science, the stable marriage problem (also stable matching problem or SMP) is the problem of finding a stable matching between two equally sized sets of elements given an ordering of preferences for each element. A matching is a bijection from the elements of one set to the elements of the other set. A matching is ''not'' stable if: In other words, a matching is stable when there does not exist any pair (''A'', ''B'') which both prefer each other to their current partner under the matching. The stable marriage problem has been stated as follows: The existence of two classes that need to be paired with each other (heterosexual men and women in this example) distinguishes this problem from the stable roommates problem. Applications Algorithms for finding solutions to the stable marriage problem have applications in a variety of real-world situations, perhaps the best known of these being in the assignment of graduating medical student ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Envy-free Matching
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 unweighted bipartite graphs In an unweighted bipartite graph G = (''X''+''Y'', ''E''), an envy-free matching is a matching in which no unmatched vertex in ''X'' is adjacent to a matched vertex in ''Y''. Suppose the vertices of ''X'' represent people, the vertices of ''Y'' represent houses, and an edge between a person ''x'' and a house ''y'' represents the fact that ''x'' is willing to live in ''y''. Then, an EFM is a partial allocation of houses to people such that each house-less person does not envy any person with a house, since he/she does not like any allocated house anyway. Every matching that saturates ''X'' is envy-free, and every empty matching is envy-free. Moreover, if , ''NG''(''X''), ≥ , X ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
