|
Envy Free
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. General definitions Suppose a certain resource is divided among several agents, such that every agent i receives a share X_i. Every agent i has a personal preference relation \succeq_i over different possible shares. The division is called envy-free (EF) if for all i and j: :::X_i \succeq_i X_j Another term for envy-freeness is no-envy (NE). If the preference of the agents are represented by a value functions V_i, then this definition is equivalent to: :::V_i(X_i) \geq V_i(X_j) Put another way: we say that agent i ''envies'' agent j if i prefers the piece of j over his own piece, i.e.: :::X_i \prec_i X_j :::V_i(X_i) 2 the problem is much harder. See envy-free cake-cutting. ... [...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] |
Envy-free Item Allocation
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. Since the items are indivisible, an EF assignment may not exist. The simplest case is when there is a single item and at least two agents: if the item is assigned to one agent, the other will envy. One way to attain fairness is to use monetary transfers; see Fair allocation of items and money. When monetary transfers are not allowed or not desired, there are allocation algorithms providing various kinds of relaxations. Finding an envy-free allocation whenever it exists Preference-orderings on bundles: envy-freeness The undercut procedure finds a complete EF allocation for two agents, if-and-only-if such allocation exists. It requires the agents to rank bundles of items, but it does not require cardinal utility information. It works whenever the agents' ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Fair Division Experiments
Various experiments have been made to evaluate various procedures for fair division, the problem of dividing resources among several people. These include case studies, computerized simulations, and lab experiments. Case studies Allocating indivisible heirlooms 1. Flood describes a division of a gift containing 5 parcels: whiskey, prunes, eggs, suitcase, etc. The division was done using the Knaster auction. The resulting division was fair, but in retrospect it was found that coalitions could gain from manipulation. 2. When Mary Anna Lee Paine Winsor died at the age of 93, her estate included two trunks of silver, that had to be divided among her 8 grandchildren. It was divided using a decentralized, fair and efficient allocation procedure, which combined market equilibrium and a Vickrey auction. Although most participants did not fully understand the algorithm or the preference information desired, it handled the major considerations well and was regarded as equitable. Allo ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Inequity Aversion
Inequity aversion (IA) is the preference for fairness and resistance to incidental inequalities. The social sciences that study inequity aversion include sociology, economics, psychology, anthropology, and ethology. Human studies Inequity aversion research on humans mostly occurs in the discipline of economics though it is also studied in sociology. Research on inequity aversion began in 1978 when studies suggested that humans are sensitive to inequities in favor of as well as those against them, and that some people attempt overcompensation when they feel "guilty" or unhappy to have received an undeserved reward. A more recent definition of inequity aversion (resistance to inequitable outcomes) was developed in 1999 by Fehr and Schmidt. They postulated that people make decisions so as to minimize inequity in outcomes. Specifically, consider a setting with individuals who receive pecuniary outcomes ''xi''. Then the utility to person ''i'' would be given by :U_i(\) = x_i - \frac ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Envy Minimization
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. Ideally, from a fairness perspective, one would like to find an envy-free item allocation - an allocation in which no agent envies another agent. That is: no agent prefers the bundle allocated to another agent. However, with indivisible items this might be impossible. One approach for coping with this impossibility is to turn the problem to an optimization problem, in which the loss function is a function describing the amount of envy. In general, this optimization problem is NP-hard, since even deciding whether an envy-free allocation exists is equivalent to the partition problem. However, there are optimization algorithms that can yield good results in practice. Defining the amount of envy There are several ways to define the objective function (the amoun ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Symmetric Fair Cake-cutting
Symmetric fair cake-cutting is a variant of the fair cake-cutting problem, in which fairness is applied not only to the final outcome, but also to the assignment of roles in the division procedure. As an example, consider a birthday cake that has to be divided between two children with different tastes, such that each child feels that his/her share is "fair", i.e., worth at least 1/2 of the entire cake. They can use the classic divide and choose procedure: Alice cuts the cake into two pieces worth exactly 1/2 in her eyes, and George chooses the piece that he considers more valuable. The outcome is always fair. However, the procedure is not symmetric: while Alice always gets a value of exactly 1/2 of her value, George may get much more than 1/2 of his value. Thus, while Alice does not envy George's share, she does envy George's role in the procedure. In contrast, consider the alternative procedure in which Alice and George both make half-marks on the cake, i.e., each of them marks t ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Complete Graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices is connected by a pair of unique edges (one in each direction). Graph theory itself is typically dated as beginning with Leonhard Euler's 1736 work on the Seven Bridges of Königsberg. However, drawings of complete graphs, with their vertices placed on the points of a regular polygon, had already appeared in the 13th century, in the work of Ramon Llull. Such a drawing is sometimes referred to as a mystic rose. Properties The complete graph on vertices is denoted by . Some sources claim that the letter in this notation stands for the German word , but the German name for a complete graph, , does not contain the letter , and other sources state that the notation honors the contributions of Kazimierz Kuratowski to graph theory. has edges (a ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Social Network
A social network is a social structure made up of a set of social actors (such as individuals or organizations), sets of dyadic ties, and other social interactions between actors. The social network perspective provides a set of methods for analyzing the structure of whole social entities as well as a variety of theories explaining the patterns observed in these structures. The study of these structures uses social network analysis to identify local and global patterns, locate influential entities, and examine network dynamics. Social networks and the analysis of them is an inherently interdisciplinary academic field which emerged from social psychology, sociology, statistics, and graph theory. Georg Simmel authored early structural theories in sociology emphasizing the dynamics of triads and "web of group affiliations". Jacob Moreno is credited with developing the first sociograms in the 1930s to study interpersonal relationships. These approaches were mathematically formalize ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
No Justified Envy
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 ''d''1, employed in some hospital ''h''1, prefers some other hospital ''h''2, which employs some other doctor ''d''2 (we say that ''d1 envies d2''). The envy is ''justified'' if, at the same time, ''h''2 prefers ''d''1 over ''d''2. Note that, ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Round-robin Item Allocation
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. Setting There are ''m'' objects to allocate, and ''n'' people ("agents") with equal rights to these objects. Each person has different preferences over the objects. The preferences of an agent are given by a vector of values - a value for each object. It is assumed that the value of a bundle for an agent is the sum of the values of the objects in the bundle (in other words, the agents' valuations are an additive set function on the set of objects). Description The protocol proceeds as follows: # Number the people arbitrarily from 1 to n; # While there are unassigned objects: #* Let each per ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Responsive Set Extension
In utility theory, the responsive set (RS) extension is an extension of a preference-relation on individual items, to a partial preference-relation of item-bundles. Example Suppose there are four items: w,x,y,z. A person states that he ranks the items according to the following total order: :w \prec x \prec y \prec z (i.e., z is his best item, then y, then x, then w). Assuming the items are independent goods, one can deduce that: :\ \prec \ – the person prefers his two best items to his two worst items; :\ \prec \ – the person prefers his best and third-best items to his second-best and fourth-best items. But, one cannot deduce anything about the bundles \, \; we do not know which of them the person prefers. The RS extension of the ranking w \prec x \prec y \prec z is a partial order on the bundles of items, that includes all relations that can be deduced from the item-ranking and the independence assumption. Definitions Let O be a set of objects and \preceq a total order ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Group Envy-freeness
Group envy-freeness (also called: coalition fairness) is a criterion for fair division. A group-envy-free division is a division of a resource among several partners such that every group of partners feel that their allocated share is at least as good as the share of any other group with the same size. The term is used particularly in problems such as fair resource allocation, fair cake-cutting and fair item allocation. Group-envy-freeness is a very strong fairness requirement: a group-envy-free allocation is both envy-free and Pareto efficient, but the opposite is not true. Definitions Consider a set of ''n'' agents. Each agent ''i'' receives a certain allocation ''Xi'' (e.g. a piece of cake or a bundle of resources). Each agent ''i'' has a certain subjective preference relation <''i'' over pieces/bundles (i.e. means that agent ''i'' prefers piece ''X'' to piece ''Y''). Consider a group ''G'' of the agents, with its current allocation |
