In economics and social choice theory, a no-justified-envy matching is a matching in a two-sided market, in which no agent prefers the assignment of another agent and is simultaneously preferred by that assignment.
Consider, for example, the task of matching doctors for residency in hospitals. Each doctor has a preference relation on hospitals, ranking the hospitals from best to worst. Each hospital has a preference relation on doctors, ranking the doctors from best to worst. Each doctor can work in at most one hospital, and each hospital can employ at most a fixed number of doctors (called the capacity of the hospital). The goal is to match doctors to hospitals, without monetary transfers.
Envy is a situation in which some doctor d1, employed in some hospital h1, prefers some other hospital h2, which employs some other doctor d2 (we say that d1 envies d2). The envy is justified if, at the same time, h2 prefers d1 over d2. Note that, if d1 has justified envy w.r.t. h2, then h2 has justified envy w.r.t. d1 (h2 envies h1). In this case, we also say that d1 and h2 are a blocking pair. A matching with no blocking pairs is called a no-justified-envy (NJE) matching, or a matching that eliminates justified envy. [1] [2]
No-justified-envy matching is a relaxation of two different conditions:
In a many-to-one matching problem, stable matchings exist and can be found by the Gale–Shapley algorithm. Therefore, NJE matchings exist too. In general there can be many different NJE matchings. The set of all NJE matchings is a lattice. The set of stable matchings (which are a subset of the NJE matchings) is a fixed point of a Tarsky operator on that lattice. [3]
Often, the hospitals have not only upper quotas (capacities), but also lower quotas – each hospital must be assigned at least some minimum number of doctors. [4] In such problems, stable matchings may not exist (though it is easy to check whether a stable matching exists, since by the rural hospitals theorem, in all stable matchings, the number of doctors assigned to each hospital is identical). In such cases it is natural to check whether an NJE matching exists. A necessary condition is that the sum of all lower quotas is at most the number of doctors (otherwise, no feasible matching exist at all). In this case, if all doctor-hospital pairs are acceptable (every doctor prefers any hospital to unemployment, and any hospital prefers any doctor to a vacant position), then an NJE matching always exists. [4]
If not all pairs are acceptable, then an NJE matching might not exist. It is possible to decide the existence of an EFM in the following way. Create a new instance of the problem, in which the upper quotas are the lower quotas of the original problem, and the lower quotas are 0. In the new problem, a stable matching always exists and can be found efficiently. The original problem has an NJE matching if-and-only-if, in the stable matching of the new problem, every hospital is full. [5]
The algorithm can be improved to find a maximal NJE matching. [6]
By definition, in an NJE matching, there may be a doctor d and a hospital h such that d prefers h over his current employer, but h does not prefer d over any of its current employees. This may be called an "unjustified envy". A matching with no envy at all exists only in the rare case in which each doctor can be matched to his first choice. When such a "totally envy-free matching" does not exist, it is still reasonable to find matchings that minimize the "envy amount". There are several ways in which the envy amount may be measured, for example: the total amount of envy-instances over all doctors, or the maximum amount of envy-instances per doctor. [7]
In geometry, a dodecahedron or duodecahedron is any polyhedron with twelve flat faces. The most familiar dodecahedron is the regular dodecahedron with regular pentagons as faces, which is a Platonic solid. There are also three regular star dodecahedra, which are constructed as stellations of the convex form. All of these have icosahedral symmetry, order 120.
In mathematics, economics, and computer science, the stable marriage problem 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:
The National Resident Matching Program (NRMP), also called The Match, is a United States-based private non-profit non-governmental organization created in 1952 to place U.S. medical school students into residency training programs located in United States teaching hospitals. Its mission has since expanded to include the placement of U.S. citizen and non-U.S. citizen international medical school students and graduates into residency and fellowship training programs. In addition to the annual Main Residency Match that in 2021 encompassed more than 48,000 applicants and 38,000 positions, the NRMP conducts Fellowship Matches for more than 60 subspecialties through its Specialties Matching Service (SMS). The NRMP is sponsored by a board of directors that includes medical school deans, teaching hospital executives, graduate medical education program directors, medical students and residents, and one public member.
In mathematics, economics, and computer science, the Gale–Shapley algorithm is an algorithm for finding a solution to the stable matching problem. It is named for David Gale and Lloyd Shapley, who published it in 1962, although it had been used for the National Resident Matching Program since the early 1950s. Shapley and Alvin E. Roth won the 2012 Nobel Prize in Economics for work including this algorithm.
Tayfun Sönmez is a Turkish-American professor of economics at Boston College. He is a Fellow of the Econometric Society and the 2008 winner of the Social Choice and Welfare Prize, which honors scholars under the age of 40 for excellent accomplishment in the area of social choice theory and welfare economics. Sönmez has made significant contributions in the areas of microeconomic theory, mechanism/market design, and game theory. His work has been featured by the U.S. National Science Foundation for its practical relevance.
Envy-freeness, also known as no-envy, is a criterion for fair division. It says that, when resources are allocated among people with equal rights, each person should receive a share that is, in their eyes, at least as good as the share received by any other agent. In other words, no person should feel envy.
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.
Top trading cycle (TTC) is an algorithm for trading indivisible items without using money. It was developed by David Gale and published by Herbert Scarf and Lloyd Shapley.
Fair random assignment is a kind of a fair division problem.
Random priority (RP), also called Random serial dictatorship (RSD), is a procedure for fair random assignment - dividing indivisible items fairly among people.
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 their "thing" with that of another person. This term has been used in several different contexts.
The rural hospitals theorem (RHT) is a fundamental theorem in the theory of stable matching. It considers the problem of matching doctors to hospitals for residency, where each doctor is matched to a single hospital but each hospital has several positions for doctors. The total number of positions is larger than the total number of doctors, so some hospitals inevitably remain with unfilled positions. Usually, rural hospitals are less wanted than urban hospitals, so they often remain with many empty positions. This raised the question of whether the mechanism used to match doctors to hospitals can be changed in order to help these rural hospitals.
Stable marriage with indifference is a variant of the stable marriage problem. Like in the original problem, the goal is to match all men to all women such that no pair of man and woman who are unmarried to each other, would simultaneously like to leave their present partners and pair with each other instead.
In mathematics, economics, and computer science, the lattice of stable matchings is a distributive lattice whose elements are stable matchings. For a given instance of the stable matching problem, this lattice provides an algebraic description of the family of all solutions to the problem. It was originally described in the 1970s by John Horton Conway and Donald Knuth.
In mathematics, economics, and computer science, the stable matching polytope or stable marriage polytope is a convex polytope derived from the solutions to an instance of the stable matching problem.
In computer science and operations research, the envy minimization problem is the problem of allocating discrete items among agents with different valuations over the items, such that the amount of envy is as small as possible.
In economics and computer science, the house allocation problem is the problem of assigning objects to people with different preferences, such that each person receives exactly one object. The name "house allocation" comes from the main motivating application, which is assigning dormitory houses to students. Other commonly used terms are assignment problem and one-sided matching. When agents already own houses, the problem is often called a housing market. In house allocation problems, it is assumed that monetary transfers are not allowed; the variant in which monetary transfers are allowed is known as rental harmony.
A school-choice mechanism is an algorithm that aims to match pupils to schools in a way that respects both the pupils' preferences and the schools' priorities. It is used to automate the process of school choice. The most common school-choice mechanisms are variants of the deferred-acceptance algorithm and random serial dictatorship.
In mechanism design, a regret-free truth-telling mechanism is a mechanism in which each player who reveals his true private information does not feel regret after seeing the mechanism outcome. A regret-free mechanism incentivizes agents who want to avoid regret to report their preferences truthfully.
{{cite journal}}: Cite journal requires |journal= (help)