Efficient envy-free division
Efficient envy-free division
Efficiency and fairness are two major goals of welfare economics. Given a set of resources and a set of agents, the goal is to divide the resources among the agents in a way that is both Pareto efficient (PE) and envy-free (EF). The goal was first defined by david-schmeidler and Menahem Yaari. Later, the existence of such allocations has been proved under various conditions.
Existence of PEEF allocations We assume that each agent has a preference-relation on the set of all bundles of commodities. The preferences are complete, transitive, and closed. Equivalently, each preference relation can be represented by a continuous utility function.
Weakly-convex preferences *Theorem 1 (Varian):
Topological conditions on the space of efficient allocations PEEF allocations exist even when agents' preferences are not convex. There are several sufficient conditions that are related to the shape of the set of allocations corresponding to a specific efficient utility profile. Given a utility-vector u, define A(u) = the set of all allocations for which the utility-profile is u. The following successively more general theorems were proved by different authors:
- Theorem 2** (Varian): If all agents' preferences are strongly monotone, and for every PE utility-profile u, the set A(u) is convex, then PEEF allocations exist.*
The proof uses the Kakutani fixed-point theorem.
- Note*: if all agents' preferences are convex (as in theorem 1), then A(u) is obviously convex too. Moreover, if A(u) is singleton (as in theorem 2) then it is obviously convex too. Hence, Svensson's theorem is more general than both Varian's theorems.
- Theorem 4** (Diamantaras): If all agents' preferences are strongly monotone, and for every PE utility-profile u, the set A(u) is a contractible space (can be continuously shrunk to a point within that space), then PEEF allocations exist.*
The proof uses a fixed-point theorem by Eilenberg and Montgomery.
- Note:* Every convex set is contractible, so Diamantaras' theorem is more general than the previous three.
Sigma-optimality Svensson proved another sufficient condition for the existence of PEEF allocations. Again all preferences are represented by continuous utility functions. Moreover, all utility functions are continuously differentiable in the interior of the consumption space.
The main concept is sigma-optimality. Suppose we create, for each agent, k copies with identical preferences. Let X be an allocation in the original economy. Let Xk be an allocation in the k-replicated economy where all copies of the same agent receive the same bundle as the original agent in X. The allocation X is called sigma-optimal if for every k, the allocation Xk is Pareto-optimal.
- Lemma: An allocation is sigma-optimal, if-and-only-if it is a competitive-equilibrium.*
- Theorem 5** (Svensson): Suppose all agents' preferences are strongly monotone, and represented by continuous utility functions. Then, Pareto-efficient EEF allocations exist.*
Non-existence of PEEF allocations ### Non-convex preferences PEEF allocations might fail to exist even without production, when the preferences are non-convex.
As an example, suppose the total endowment is (4,2), and Alice and Bob have identical concave utilities:
:<math>u_A(x,y)=u_B(x,y)=\max(x,y)</math>.
The equal allocation [(2,1);(2,1)] is EF with utility vector (2,2). Moreover, every EF allocation must give both agents equal utility (since they have the same utility function) and this utility can be at most 2. However, no such allocation is PE, since it is Pareto-dominated by the allocation [(4,0);(0,2)] whose utility vector is (4,2).
Non-existence remains even if we weaken envy-freeness to no domination -- no agent gets more of each good than another agent.
- Proposition 8** (Maniquet): There exist 2-good 3-agent division economies with strictly monotonic, continuous and even differentiable preferences, where there is domination at every Pareto efficient allocation.*
Finding a PEEF allocation For two agents, the adjusted-winner-procedure is a simple procedure that finds a PEEF allocation with two additional properties: the allocation is also equitable, and at most a single good is shared between the two agents.
For three or more agents with linear utilities, any Nash-optimal allocation is PEEF. A Nash-optimal allocation is an allocation that maximizes the product of the utilities of the agents, or equivalently, the sum of logarithms of utilities. Finding such an allocation is a convex optimization problem:
<math>\text{maximize} \sum_{i=1}^n \log(u_i(X_i)) ~~~\text{such that}~~~ (X_1,\ldots,X_n) ~~~\text{is a partition}~~~</math>.
and thus it can be found efficiently. The fact that any Nash-optimal allocation is PEEF is true even in the more general setting of fair-cake-cutting.
- Proof: Consider an infinitesimal piece of cake, Z. For each agent i, the infinitesimal contribution of Z* to <math>\log(u_i(X_i))</math> is
<math>u_i(Z)\cdot {d \log(u_i(X_i))\over d (u_i(X_i))} = {u_i(Z) \over u_i(X_i)}</math>.
Therefore, the Nash-optimal rule gives each such piece Z to an agent j for which this expression is largest:
<math>\forall j\in[n]: Z\subseteq X_j \iff \forall i\in[n]: {u_j(Z)\over u_j(X_j)} \geq {u_i(Z)\over u_i(X_i)}</math>
Summing over all infinitesimal subsets of *Xj'', we get:
<math>\forall i,j\in[n]: {u_j(X_j )\over u_j(X_j )} \geq {u_i(X_j)\over u_i(X_i)}</math>
This implies the definition of envy-free allocation:
<math>\forall i,j\in[n]: {u_i(X_i)} \geq {u_i(X_j)}</math>