|
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. I ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Envy-free Pricing
Envy-free pricing is a kind of fair item allocation. There is a single seller that owns some items, and a set of buyers who are interested in these items. The buyers have different valuations to the items, and they have a quasilinear utility function; this means that the utility an agent gains from a bundle of items equals the agent's value for the bundle minus the total price of items in the bundle. The seller should determine a price for each item, and sell the items to some of the buyers, such that there is Envy-freeness, ''no envy''. Two kinds of envy are considered: * ''Agent envy'' means that some agent assigns a higher utility (a higher difference value-price) to a bundle allocated to another agent. * ''Market envy'' means that some agent assigns a higher utility (a higher difference value-price) to any bundle. The no-envy conditions guarantee that the market is stable and that the buyers do not resent the seller. By definition, every market envy-free allocation is also agent ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Envy-free Cake-cutting
An envy-free cake-cutting is a kind of fair cake-cutting. It is a division of a heterogeneous resource ("cake") that satisfies the envy-free criterion, namely, that every partner feels that their allocated share is at least as good as any other share, according to their own subjective valuation. When there are only two partners, the problem is easy and was solved in antiquity by the divide and choose protocol. When there are three or more partners, the problem becomes much more challenging. Two major variants of the problem have been studied: * Connected pieces, e.g. if the cake is a 1-dimensional interval then each partner must receive a single sub-interval. If there are n partners, only n-1 cuts are needed. * General pieces, e.g. if the cake is a 1-dimensional interval then each partner can receive a union of disjoint sub-intervals. Short history Modern research into the fair cake-cutting problem started in the 1940s. The first fairness criterion studied was proportional divi ... [...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] |
Rental Harmony
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. In the typical setting, there are n partners who rent together an n-room house for cost fixed by the homeowner. Each housemate may have different preferences — one may prefer a large room, another may prefer a room with a view to the main road, etc. The following two problems should be solved simultaneously: * (a) Assign a room to each partner, * (b) Determine the amount each partner should pay, such that the sum of payments equals the fixed cost. There are several properties that we would like the assignment to satisfy. * Non-negativity (NN): all prices must be 0 or more: no partner should be paid to get a room. * Envy-freeness (EF): Given a pricing scheme (an assignment of rent to rooms), we say that a partner ''prefers'' a given room if he ... [...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] |
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] |
Chore Division
Chore division is a fair division problem in which the divided resource is undesirable, so that each participant wants to get as little as possible. It is the mirror-image of the fair cake-cutting problem, in which the divided resource is desirable so that each participant wants to get as much as possible. Both problems have heterogeneous resources, meaning that the resources are nonuniform. In cake division, cakes can have edge, corner, and middle pieces along with different amounts of frosting. Whereas in chore division, there are different chore types and different amounts of time needed to finish each chore. Similarly, both problems assume that the resources are divisible. Chores can be infinitely divisible, because the finite set of chores can be partitioned by chore or by time. For example, a load of laundry could be partitioned by the number of articles of clothing and/or by the amount of time spent loading the machine. The problems differ, however, in the desirability of the ... [...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] |
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 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] |
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] |
Super Envy-freeness
A super-envy-free division is a kind of a fair division. It is a division of resources among ''n'' partners, in which each partner values his/her share at strictly ''more'' than his/her due share of 1/''n'' of the total value, and simultaneously, values the share of every other partner at strictly less than 1/''n''. Formally, in a super-envy-free division of a resource ''C'' among ''n'' partners, each partner ''i'', with value measure ''Vi'', receives a share ''Xi'' such that:V_i(X_i) > V_i(C)/n ~~ \text ~~ \forall j\neq i:V_i(X_j) < V_i(C)/n .This is a strong fairness requirement: it is stronger than both and super-proportionality. Existence Super envy-freeness was introduced by Julius Barbanel in 199 ...[...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
