Resource monotonicity

Allocating divisible resources

Single homogeneous resource, general utilities

Suppose society has ${\displaystyle m}$ units of some homogeneous divisible resource, such as water or flour. The resource should be divided among ${\displaystyle n}$ agents with different utilities. The utility of agent ${\displaystyle i}$ is represented by a function ${\displaystyle u_i}$; when agent ${\displaystyle i}$ receives ${\displaystyle y_i}$ units of resource, he derives from it a utility of ${\displaystyle u_i(y_i)}$. Society has to decide how to divide the resource among the agents, i.e, to find a vector ${\displaystyle y_1,\dots ,y_n}$ such that: ${\displaystyle y_1+\cdots +y_n=m}$.

Two classic allocation rules are the egalitarian rule - aiming to equalize the utilities of all agents (equivalently: maximize the minimum utility), and the utilitarian rule - aiming to maximize the sum of utilities.

The egalitarian rule is always RM: when there is more resource to share, the minimum utility that can be guaranteed to all agents increases, and all agents equally share the increase. In contrast, the utilitarian rule might be not RM.

For example, suppose there are two agents, Alice and Bob, with the following utilities:

• ${\displaystyle u_A(y_A)=y_A^2}$
• ${\displaystyle u_B(y_B)=y_B}$

The egalitarian allocation is found by solving the equation: ${\displaystyle y_A^2=(m-y_A)}$, which is equivalent to ${\displaystyle m=y_A^2+y_A}$, so ${\displaystyle y_A}$ is monotonically increasing with ${\displaystyle m}$. An equivalent equation is: ${\displaystyle y_B=(m-y_B{)}^2}$, which is equivalent to ${\displaystyle m=\sqrt{y_B}+y_B}$, so ${\displaystyle y_B}$ too is monotonically increasing with ${\displaystyle m}$. So in this example (as always) the egalitarian rule is RM.

In contrast, the utilitarian rule is not RM. This is because Alice has increasing returns: her marginal utility is small when she has few resources, but it increases fast when she has many resources. Hence, when the total amount of resource is small (specifically, ${\displaystyle m<1}$), the utilitarian sum is maximized when all resources are given to Bob; but when there are many resources (${\displaystyle m>1}$), the maximum is attained when all resources are given to Alice. Mathematically, if ${\displaystyle y}$ is the amount given to Alice, then the utilitarian sum is ${\displaystyle y^2+(m-y)}$. This function has only an internal minimum point but not an internal maximum point; its maximum point in the range ${\displaystyle [0,m]}$ is attained in one of the endpoints. It is the left endpoint when ${\displaystyle m<1}$ and the right endpoint when ${\displaystyle m>1}$. In general, the utilitarian allocation rule is RM when all agents have diminishing returns, but it may be not RM when some agents have increasing returns (as in the example).

Thus, if society uses the utilitarian rule to allocate resources, then Bob loses value when the amount of resources increases. This is bad because it gives Bob an incentive against economic growth: Bob will try to keep the total amount small in order to keep his own share large.

Two complementary resources, Leontief utilities

Consider a cloud server with some units of RAM and CPU. There are two users with different types of tasks:

• The tasks of Alice need 1 unit of RAM and 2 units of CPU;
• The tasks of Bob need 2 units of RAM and 1 unit of CPU.

Thus, the utility functions (=number of tasks), denoting RAM by r and CPU by c, are Leontief utilities:

• ${\displaystyle u_A(r,c)=min(r,c/2)}$
• ${\displaystyle u_B(r,c)=min(r/2,c)}$

If the server has 12 RAM and 12 CPU, then both the utilitarian and the egalitarian allocations (and also the Nash-optimal, max-product allocation) are:

• ${\displaystyle r_A=4,c_A=8⟹u_A=4}$
• ${\displaystyle r_B=8,c_B=4⟹u_B=4}$

Now, suppose 12 more units of CPU become available. The egalitarian allocation does not change, but the utilitarian allocation now gives all resources to Alice:

• ${\displaystyle r_A=12,c_A=24⟹u_A=12}$
• ${\displaystyle r_B=0,c_B=0⟹u_B=0}$

so Bob loses value from the increase in resources.

The Nash-optimal (max-product) allocation becomes:

• ${\displaystyle r_A=6,c_A=12⟹u_A=6}$
• ${\displaystyle r_B=6,c_B=3⟹u_B=3}$

so Bob loses value here too, but the loss is less severe.

Cake cutting, additive utilities

In the fair cake-cutting problem, classic allocation rules such as divide and choose are not RM. Several rules are known to be RM:

• When the pieces may be disconnected, any allocation rule maximizing a concave welfare function of the absolute (not normalized) utilities is RM. In particular, the Nash-optimal rule, absolute-leximin rule and absolute-utilitarian rule are all RM. However, if the maximization uses the relative utilities (utilities divided by total cake value) then most of these rules are not RM; the only one that remains RM is the Nash-optimal rule.
• When the pieces must be connected, no Pareto-optimal proportional division rule is RM. The absolute-equitable rule is weakly Pareto-optimal and RM, but not proportional. The relative-equitable rule is weakly Pareto-optimal and proportional, but not RM. The so-called rightmost mark rule, which is an variant of divide-and-choose, is proportional, weakly Pareto-optimal and RM - but it works only for two agents. It is an open question whether there exist division procedures that are both proportional and RM for three or more agents.

Single-peaked preferences

Resource-monotonicity was studied in problems of fair division with single-peaked preferences.