Fair division of a single homogeneous resource
Fair division of a single homogeneous resource
- Fair division of a single homogeneous resource** is one of the simplest settings in [[fair-division]] problems. There is a single resource that should be divided between several people. The challenge is that each person derives a different utility from each amount of the resource. Hence, there are several conflicting principles for deciding how the resource should be divided. A primary conflict is between efficiency and equality. Efficiency is represented by the *utilitarian* rule, which maximizes the sum of utilities; equality is represented by the *egalitarian* rule, which maximizes the minimum utility.
Setting In a certain society, there are: * <math>t</math> units of some divisible resource. * <math>n</math> agents with different "utilities". * The utility of agent <math>i</math> is represented by a function <math>u_i</math>; when agent <math>i</math> receives <math>y_i</math> units of resource, he derives from it a utility of <math>u_i(y_i)</math>.
This setting can have various interpretations. For example: The resource is wood, the agents are builders, and the utility functions represent their productive power - <math>u_i(y_i)</math> is the number of buildings that agent <math>i</math> can build using <math>y_i</math> units of wood. The resource is a medication, the agents are patients, and the utility functions represent their chance of recovery - <math>u_i(y_i)</math> is the probability of agent <math>i</math> to recover by getting <math>y_i</math> doses of the medication.
In any case, the society has to decide how to divide the resource among the agents: it has to find a vector <math>y_1,\dots,y_n</math> such that: <math>y_1+\cdots+y_n = t</math>
Allocation rules ### Envy-free The [[envy-freeness]] rule says that the resource should be allocated such that no agent envies another agent. In the case of a single homogeneous resource, it always selects the allocation that gives each agent the same amount of the resource, regardless of their utility function: ::<math>\forall i: y_i = t/n</math>
Utilitarian The utilitarian rule says that the sum of utilities should be maximized. Therefore, the utilitarian allocation is: ::<math>y = \arg\max_y \sum_i u_i(y_i)</math>
Egalitarian The **egalitarian** rule says that the utilities of all agents should be equal. Therefore, we would like to select an allocation that satisfies: ::<math>\forall i,j: u_i(y_i) = u_j(y_j)</math> However, such allocation may not exist, since the ranges of the utility functions might not overlap (see example below). To ensure that a solution exists, we allow different utility levels, but require that agents with utility levels above the minimum receive no resources: ::<math>y_i>0 \implies u_i(y_i) = \min_j u_j(y_j)</math> Equivalently, the egalitarian allocation maximizes the minimum utility: ::<math>y = \arg\max_y \min_i u_i(y_i)</math>
The utilitarian and egalitarian rules may lead to the same allocation or to different allocations, depending on the utility functions. Some examples are illustrated below.
Examples ### Common utility and unequal endowments Suppose all agents have the same utility function, <math>u</math>, but each agent <math>i</math> has a different initial endowment, <math>x_i</math>. So the utility of each agent <math>i</math> is given by: ::<math>u_i(y_i) = u(x_i + y_i)</math>
If <math>u</math> is a concave function, representing diminishing returns, then the utilitarian and egalitarian allocations are the same - trying to equalize the endowments of the agents. For example, if there are 3 agents with initial endowments <math>x=2,4,9</math> and the total amount is <math>t=8</math>, then both rules recommend the allocation <math>y=5,3,0</math>, since it both pushes towards equal utilities (as much as possible) and maximizes the sum of utilities.
In contrast, if <math>u</math> is a convex function, representing increasing returns, then the egalitarian allocation still pushes towards equality, but the utilitarian allocation now gives all the endowment to the richest agent: <math>y=0,0,9</math>. This makes sense, for example, when the resource is a scarce medication: it may be socially best to give all medication to the patient with the highest chances of curing.
Constant utility ratios Suppose there is a common utility function <math>u</math>, but each agent has a different coefficient <math>a_i</math> representing this agent's productivity. So the utility of each agent <math>i</math> is given by: ::<math>u_i(y_i) = a_i\cdot u(y_i)</math>
Here, the utilitarian and egalitarian approaches are diametrically opposed.
- The egalitarian allocation gives more resources to the less productive agents, in order to compensate them and let them reach a high utility level:
- ::<math>a_i>a_j \implies y_j>y_i</math>
- The utilitarian allocation gives more resources to the more productive agents, since they will use the resources better:
- ::<math>a_i>a_j \implies y_i>y_j</math>