1000/1000
Hot
Most Recent
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.:296–297 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. Therefore, the division procedures provide various kinds of relaxations.
Envy-freeness is attainable when, in addition to the indivisible items, there is also a divisible good ("money").
A special case of this setting is when dividing rooms in an apartment between tenants. It is characterized by two requirements: (a) the number of agents equals the number of objects, (b) the total amount of money paid by the agents must equal the total rent (which is fixed in advance). This is known as the Rental Harmony problem.
A second special case is when selling objects to buyers. In this case, the sum of payments is not fixed in advance, and the goal is to maximize either the seller's revenue, or the social welfare, subject to envy-freeness. Additionally, the number of objects may be different than the number of agents, and some objects may be discarded. This is known as the Envy-free Pricing problem.
A third case is when a benevolent third-party is willing to subsidize the allocation, but wants to minimize the amount of subsidy subject to envy-freeness. This problem is called the minimum-subsidy envy-free allocation, and it was studied in several settings.
Unit-demand agents are interested in at most a single item. In the economics literature, it is common to assume that each agent has a utility function on bundles (a bundle is a pair of an object and a certain amount of money). The utility function should be continuous and increasing in money. It does not have to be linear in money, but does have to be "Archimedean", i.e., there exists some value V such that, for every two objects j and k, the utility of object j plus V should be larger than the utility of object k (alternatively, the utility of getting object j for free is larger than the utility of getting object k and paying V). Quasilinear utility is a special case of Archimedean utility, in which V is the largest value-difference (for the same agent) between two objects.
Svensson[1] first proved that, when all agents are Archimedean, an envy-free allocation exists and is Pareto-optimal.
Demange, Gale and Sotomayor[2] showed a natural ascending auction that achieves an envy-free allocation using monetary payments for unit demand agents.
Maskin[3] proved the existence of a Pareto-optimal envy-free allocation when the total money endowment is more than (n-1)V. The proofs use competitive equilibrium.
Note that a subsidy of (n-1)V may be required: if all agents value a single object at V and the other objects at 0, then envy-freeness requires a subsidy of V for each agent who does not receive the object.
Tadenuma and Thomson[4] study several consistency properties of envy-free allocation rules.
Aragones[5] characterizes the minimum amount of subsidy required for envy-freeness. The allocation that attains this minimum subsidy is almost unique: there is only one way to combine objects with agents, and all agents are indifferent among all minimum-subsidy allocations. It coincides with the solution called the "money-Rawlsian solution" of Alkan, Demange and Gale.[6] It can be found in polynomial time, by finding a maximum-weight matching and then finding shortest paths in a certain induced graph.
Klijn[7] presents another polynomial-time algorithm for the same setting. His algorithm uses the polytope of side-payments that make a given allocaton envy-free: this polytope is nonempty iff the original allocation is Pareto-efficient. Connectivity of the undirected envy graph characterizes the extreme points of this polytope. This implies a method for finding extreme envy-free allocations.
Additive agents are more general, and may receive several items.
Alkan, Demange and Gale[6] showed that an envy-free allocation always exists when the amount of money is sufficiently large. This is true even when items may have negative valuations.
Meertens, Potters and Reijnierse[8] prove the existence of envy-free and Pareto-optimal allocations under very mild assumptions on the valuations (not necessarily quasilinear).
Cavallo[9] generalizes the traditional binary criteria of envy-freeness, proportionality, and efficiency (welfare) to measures of degree that range between 0 and 1. In the canonical fair division settings, under any allocatively-efficient mechanism the worst-case welfare rate is 0 and disproportionality rate is 1; in other words, the worst-case results are as bad as possible. He looks for a mechanism that achieves high welfare, low envy, and low disproportionality in expectation across a spectrum of fair division settings. The VCG mechanism is not a satisfactory candidate, but the redistribution mechanism of Bailey[10] and Cavallo[11] is.
Halpern and Shah[12] study subsidy in the general item-allocation setting. They consider two cases:
Brustle, Dippel, Narayan, Suzuki and Vetta[13] improve the upper bounds on the required subsidy:
Caragiannis and Ioannidis[14] study the computational problem of minimizing the subsidy:
Note that an envy-free allocation with subsidy remains envy-free if a fixed amount is taken from every agent. Therefore, similar methods can be used to find allocations that are not subsidized:
Often, some other objectives have to be attained besides fairness. For example, when assigning tasks to agents, it is required both to avoid envy, and to minimize the makespan (- the completion time of the last agent). Mu'alem presents a general framework for optimization problems with envy-freeness guarantee that naturally extends fair item allocations using monetary payments.[15]
Aziz[16] aims to attain, using monetary transfers, an allocation that is both envy-free and equitable. He studies not only additive positive utilities, but also for any superadditive utilities, whether positive or negative:
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' preference relations are strictly monotone, but does not need to assume that they are responsive preferences. In the worst case, the agents may have to rank all possible bundles, so the run-time might be exponential in the number of items.
It is usually easier for people to rank individual items than to rank bundles. Assuming all agents have responsive preferences, it is possible to lift the item-ranking to a partial bundle-ranking. For example, if the item-ranking is w>x>y>z, then responsiveness implies that {w,x}>{y,z} and {w,y}>{x,z}, but does not imply anything about the relation between {w,z} and {x,y}, between {x} and {y,z}, etc.
Given an item-ranking:
Bouveret and Endriss and Lang[17] study the algorithmic questions of finding a NEF/PEF allocation with an additional efficiency condition, particularly, completeness or NPE or PPE. In general, PEF is computationally easy while NEF is computationally hard.
The empty allocation is always EF. But if we want some efficiency in addition to EF, then the decision problem becomes computationally hard:[18]:300–310
The decision problem may become tractable when some parameters of the problem are considered fixed small constants:[23]
Many procedures find an allocation that is "almost" envy-free, i.e., the level of envy is bounded. There are various notions of "almost" envy-freeness:
An allocation is called EF1 if for every two agents A and B, if we remove at most one item from the bundle of B, then A does not envy B.[24] An EF1 allocation always exists and can be found efficiently by various procedures, particularly:
An allocation is called EFx if for every two agents A and B, if we remove any item from the bundle of B, then A does not envy B.[29] EFx is strictly stronger than EF1: EF1 lets us eliminate envy by removing the item most valuable (for A) from B's bundle; EFx requires that we eliminate envy by removing the item least valuable (for A). An EFx allocation is known to exist in some special cases:
Some approximations are known:
It is an open question whether an EFx allocation exists in general. The smallest open case is 4 agents with additive valuations.
In contrast to EF1, which requires a number of queries logarithmic in the number of items, computing an EFx allocation may requires a linear number of queries even when there are two agents with identical additive valuations.[26]
Another difference between EF1 and EFx is that the number of EFX allocations can be as few as 2 (for any number of items), while the number of EF1 allocations is always exponential in the number of items.[38]
Some division scenarios involve both divisible and indivisible items, such as divisible lands and indivisible houses. An allocation is called EFm if for every two agents A and B:[39]
An EFm allocation exists for any number of agents. However, finding it requires an oracle for exact division of a cake. Without this oracle, an EFm allocation can be computed in polynomial time in two special cases: two agents with general additive valuations, or any number of agents with piecewise-linear valuations.
In contrast to EF1, which is compatible with Pareto-optimality, EFm may be incompatible with it.
Rather than using a worst-case bound on the amount of envy, one can try to minimize the amount of envy in each particular instance. See envy minimization for details and references.
The AL procedure finds an EF allocation for two agents. It may discard some of the items, but, the final allocation is Pareto efficient in the following sense: no other EF allocation is better for one and weakly better for the other. The AL procedure only requires the agents to rank individual items. It assumes that the agents have responsive preferences and returns an allocation that is necessarily envy-free (NEF).
The Adjusted winner procedure returns a complete and efficient EF allocation for two agents, but it might have to cut a single item (alternatively, one item remains in shared ownership). It requires the agents to report a numeric value for each item, and assumes that they have additive utilities.
When each agent may get at most a single item, and the valuations are binary (each agent either likes or dislikes each item), there is a polynomial-time algorithm that finds an envy-free matching of maximum cardinality.[40]
If the agents have additive utility functions that are drawn from probability distributions satisfying some independence criteria, and the number of items is sufficiently large relative to the number of agents, then an EF allocation exists with high probability. Particularly:[41]
See Fair item allocation for details and references.
Below, the following shorthands are used:
Name | #partners | Input | Preferences | #queries | Fairness | Efficiency | Comments |
---|---|---|---|---|---|---|---|
Undercut | 2 | Bundle ranking | Strictly monotone | [math]\displaystyle{ 2^m }[/math] | EF | Complete | If-and-only-if a complete EF allocation exists |
AL | 2 | Item ranking | Weakly additive | [math]\displaystyle{ Poly(m) }[/math] | Necessarily-EF | Partial, but not Pareto-dominated by another NEF | |
Adjusted winner | 2 | Item valuations | Additive | [math]\displaystyle{ Poly(m) }[/math] | EF and equitable | PE | Might divide one item. |
Round-robin | [math]\displaystyle{ n }[/math] | Item ranking | Weakly additive | [math]\displaystyle{ m }[/math] | Necessarily-EF1 | Complete | |
Envy-graph | [math]\displaystyle{ n }[/math] | Bundle ranking | Monotone | [math]\displaystyle{ O(m n^3) }[/math] | EF1 | Complete | |
A-CEEI | [math]\displaystyle{ n }[/math] | Bundle ranking | Any | ? | EF1, and [math]\displaystyle{ (n+1) }[/math]-maximin-share | Partial, but PE w.r.t. allocated items | Also approximately strategyproof when there are many agents. |
Maximum-Nash-Welfare[29] | [math]\displaystyle{ n }[/math] | Item valuations | Additive | NP-hard (but there are approximations in special cases) | EF1, and approximately-[math]\displaystyle{ n }[/math]-maximin-share | PE |
With submodular utilities, allocation is PE and MEF1. |