Redividing the cake

Abstract

The paper considers fair allocation of resources that are already allocated in an unfair way. This setting requires a careful balance between the fairness considerations and the rights of the present owners. The paper presents re-division algorithms that attain various trade-off points between fairness and ownership rights, in various settings differing in the geometric constraints on the allotments: (a) no geometric constraints; (b) connectivity—the cake is a one-dimensional interval and each piece must be a contiguous interval; (c) rectangularity—the cake is a two-dimensional rectangle or rectilinear polygon and the pieces should be rectangles; (d) convexity—the cake is a two-dimensional convex polygon and the pieces should be convex. These re-division algorithms have implications on another problem: the price-of-fairness—the loss of social welfare caused by fairness requirements. Each algorithm implies an upper bound on the price-of-fairness with the respective geometric constraints.

Appendices

Appendix

Lower bounds on price of r-proportionality

This appendix presents several lower bounds on the price of r-proportionality with geometric constraints. As a warm-up, the following simple lower bound is proved (the bound for utilitarian price of proportionality was already proved by [11]):

Theorem 9

With $n=2$ agents, when the cake is an interval and the pieces must be intervals, the utilitarian price of proportionality is 3/2 and the Nash-price of proportionality is $\sqrt{2}$.

Proof

For the lower bound,⁹ consider an interval cake with four homogeneous regions, where the values of each of two agents for each of the four regions is given by the table below (where $\epsilon >0$ is an infinitesimally small positive constant):

George’s value:	$1-\epsilon$	$\epsilon$	$\epsilon$	$1-\epsilon$
Alice’s value:	$\epsilon$	$1-\epsilon$	$1-\epsilon$	$\epsilon$

Due to symmetry, the only connected proportional allocation divides the cake exactly in the middle and gives each agent exactly 1, so both the utilitarian welfare and the Nash welfare are 1. However, giving the leftmost region to George and the rightmost three regions to Alice gives Alice a value of almost 2 and George a value of almost 1, so the utilitarian welfare is almost 3/2 and Nash welfare is almost $\sqrt{2}$. When $\epsilon \rightarrow 0$, the utilitarian price of proportionality approaches 3/2 and the Nash price of proportionality approaches $\sqrt{2}$.

For the matching upper bound, note that, in any proportional allocation, the utilitarian welfare and the Nash welfare are at least 1 (it is attained when all agents get exactly their proportional share). On the other hand, in any non-proportional allocation, the utilitarian welfare is less than $n-1+\frac{1}{n}$, and the Nash welfare is less than $(n^{n-1})^{1/n}$ (since one agent gets a value of less than 1, and the other agents get a value of at most n). Therefore, the utilitarian price of proportionality is at most $n-1+\frac{1}{n}=3/2$ and the Nash price of proportionality is at most $n^{1-1/n}=\sqrt{2}$. $\square$

Below, this lower bound is extended in two ways: two agents with r-proportionality and 2-dimensional cakes, and n agents with 1-proportionality.

Theorem 10

With $n=2$ agents, interval cake and interval pieces, or rectangular cake and rectangular pieces, for any $r \in [0, 1]$, the utilitarian price of r-proportionality is $1+r/2$ and the Nash price of r-proportionality is $\mathrm{max}(1,\sqrt{2 r})$.

Proof

For the lower bound, consider an interval cake with six homogeneous interval regions, or a rectangular cake of dimensions $6\times 6$ with six homogeneous rectangular regions of dimensions $1\times 6$ each, where the values of each of two agents for each region are given below (where $\epsilon >0$ is an infinitesimally small positive constant):

George’s value:	$r-\epsilon$	$\epsilon$	$1-r$	$1-r$	$\epsilon$	$r-\epsilon$
Alice’s value:	$\epsilon$	$r-\epsilon$	$1-r$	$1-r$	$r-\epsilon$	$\epsilon$

Observation 4

In any r-proportional allocation, both the utilitarian and the Nash welfare are at most 1.

Proof

Suppose first that the cake is an interval. In any r-proportional allocation, each agent must get a value of at least r. Hence, one agent must get the two leftmost regions and the other agent must get the two rightmost regions. The two central regions can be divided arbitrarily; regardless of how they are divided, the utilitarian welfare is 1. To compute the maximum Nash welfare, suppose George receives the two leftmost regions and a fraction x of the two central regions; so his value is $r + 2x(1-r)$, while Alice’s value is $r + 2(1-x)(1-r)$. By taking the derivative, one can find out that the product is maximized when $x=1/2$, where the value of each agent is exactly 1. Hence, the maximum Nash welfare in an r-proportional allocation is 1 too.

If the cake is rectangular, then there are two ways to divide it into two rectangles: vertically or horizontally. If it is divided by a vertical cut, then the situation is exactly as in the case of an interval. If it is divided by a horizontal cut, then — regardless of the cut location — the sum of the agents’ values is 2, so the utilitarian welfare is 1 and the maximum Nash welfare is attained when both values are 1. In both cases, the maximum utilitarian and Nash welfare in an r-proportional allocation is 1. $\square$

Observation 5

There is an allocation in which, when $\epsilon \rightarrow 0$, the utilitarian welfare approaches $1+r/2$ and the Nash welfare approaches $\sqrt{2 r}$.

Proof

Cut the cake at the right of the leftmost region (if the cake is rectangular, use a vertical cut). Give George the leftmost region and Alice the other regions. George’s value is $r-\epsilon$ while Alice’s value is $2-\epsilon$, so when $\epsilon \rightarrow 0$, the utilitarian welfare approaches $1+r/2$ and the Nash welfare approaches $\sqrt{2 r}$. $\square$

The above two observations imply a lower bound of $1+r/2$ on the utilitarian price of r-proportionality and a lower bound of $\mathrm{max}(1,\sqrt{2 r})$ on the Nash price of r-proportionality.¹⁰

For the matching upper bound, note that in any proportional allocation (which is, in particular, r-proportional), both the utilitarian and the Nash welfare are at least 1, while in any non-r-proportional allocation, the utilitarian welfare is less than $1+r/2$ the Nash welfare is less than $\sqrt{2 r}$ (since one agent gets less than r and the other agent gets at most 2). $\square$

Theorem 11

When the cake is an interval and the pieces must be intervals, the Nash price of proportionality when there are n agents is at least $2^{1-1/n}$.

Proof

Consider a piecewise-homogeneous cake consisting of 2n regions. The agents are partitioned into two groups: odd-indexed agents and even-indexed agents. The agents in each group have the same valuation. The odd-indexed agents value the regions at $1-\epsilon , \epsilon , \epsilon , 1-\epsilon , \ldots$, while the even-indexed agents value the regions at $\epsilon , 1-\epsilon , 1-\epsilon , \epsilon , \ldots$, An example is shown in the table below for $n=5$, where $1^-$ is a shorthand for $1-\epsilon$:

Agents 1, 3, 5:	$1^{-}$	$\epsilon$	$\epsilon$	$1^{-}$	$1^{-}$	$\epsilon$	$\epsilon$	$1^{-}$	$1^{-}$	$\epsilon$
Agents 2, 4:	$\epsilon$	$1^{-}$	$1^{-}$	$\epsilon$	$\epsilon$	$1^{-}$	$1^{-}$	$\epsilon$	$\epsilon$	$1^{-}$

The total cake value for all agents is n, so in a proportional allocation, each agent should get a value of at least 1. The following two observations imply the theorem.

Observation 6

In a proportional allocation, the value of every agent is exactly 1; hence the Nash welfare is 1.

Proof

In a proportional allocation, the agent who receives the leftmost piece must receive at least two adjacent regions in order to have a value of at least 1.

The two leftmost agents must receive together at least four adjacent regions. This is because the value measure arrives at 2 only at the end of the fourth region, and the leftmost agent consumes at least two regions which are worth at least 1, so to ensure the second-leftmost agent a value of at least 1, their combined consumption must consist of at least the four leftmost regions.

Proceeding this way, it is possible to prove by induction that, for every integer $\ell \ge 1$, the $\ell$ leftmost agents consume together at least $2\ell$ regions. By a symmetric argument, the same is true for the $\ell$ rightmost agents. But this implies that, in a proportional allocation, each agent must consume exactly 2 regions. The value of every two consecutive regions when starting from the left (or from the right) is exactly 1. $\square$

Observation 7

There is an allocation in which the Nash welfare approaches $2^{1-1/n}$ as $\epsilon \rightarrow 0$.

Proof

Give the leftmost region to agent 1. Then, give each of agents $2,\ldots ,n-1$ two consecutive regions. Give agent 2 the last three consecutive regions.

The value of agent 1 is $1-\epsilon$; the value of each of $2,\ldots ,n-1$ is $2-2\epsilon$; and the value of n is $2-\epsilon$. When $\epsilon \rightarrow 0$, the Nash welfare approaches $(2^{n-1})^{1/n} = 2^{1-1/n}$. $\square$

The above two observations imply that the Nash price of proportionality approaches $2^{1-1/n}$ when $\epsilon \rightarrow 0$.¹¹$\square$

So far, I could not extend Theorem 11 to rectangular cakes: the main difficulty is that there are many possible ways to cut a rectangle into n rectangles, so it is hard to reason about what the possible r-proportional allocations can be. Similarly, I could not extend the theorem to r-proportionality: giving even a single agent a value of r apparently allows a lot of freedom in allocating to the other agents, so again, it is hard to reason about what an r-proportional allocations can be. Thus, the exact utilitarian and Nash price of r-proportionality for all $n\ge 3$ and $r\in (0,1)$ remains open.