# Equitable division of a contiguous resource

I have come across the following result regarding equitable division of a resource, which is a simple and immediate consequence of linear programming complementarity (in the infinite-dimensional case). I strongly suspect that it is a special case of some other well-known principle, perhaps in a related field such as economics or even geography, but as of yet I have not found any helpful leads. Can anyone suggest any results from which the statement below is a consequence? Any other leads will also be appreciated.

Let $R$ denote a contiguous resource (such as a piece of land) that is to be divided into $n$ pieces $R_1,\dots,R_n$ among $n$ agents (so agent $i$ gets piece $R_i$). Suppose that each agent has a continuous "utility density" function $u_i(x)>0$ defined on $R$ and that $R$ also has a continuous "population density" $f(x)>0$ defined on it. The total "utility" that agent $i$ receives is then $\iint_{R_i} f(x)u_i(x) dx$. One might consider the problem of choosing $R_1,\dots,R_n$ as "equitably" as possible, say by maximizing the minimum utility of the agents:

$\text{maximize}_{R_1,\dots,R_n}\lbrace\min_i \iint_{R_i} f(x)u_i(x) dx\rbrace$ subject to

$\bigcup_i R_i = R$ and $R_i \cap R_j = \emptyset \text{ for all }i\neq j$

It is easy to verify that, at the optimal solution $R_1^*,\dots,R_n^*$, all of the agents' utilities are equal.

Now, define $q_i^* := \iint_{R_i^*} f(x) dx$ (the population of the $i$th optimal piece), and consider the problem of choosing regions to maximize the total utilities of the agents, but under a logarithmic utility function, and imposing constraints on the populations in each piece:

$\text{maximize}_{R_1,\dots,R_n}\lbrace\sum_i \iint_{R_i} f(x)\log(u_i(x)) dx\rbrace$ subject to

$\iint_{R_i} f(x) dx = q_i^*$

$\bigcup_i R_i = R$ and $R_i \cap R_j = \emptyset \text{ for all }i\neq j$

It is not hard to show that the solution to this problem is the same as the solution to the original problem. I have uploaded a MATLAB script that demonstrates this principle using cvx at

http://menet.umn.edu/~jgc/mathoverflow.m

if anyone is interested.

-
From the "Out in Left Field" file comes the suggestion of equitable frosted cake cutting, where everyone gets the same amount of cake and frosting. Perhaps some searches using this idea will help, although you may end up with algorithms involving envy minimization and the like. Gerhard "Likes Whipped Cream With Liquer" Paseman, 2012.06.25 –  Gerhard Paseman Jun 25 '12 at 22:41
Perhaps there is some insight to be gained via generalized Voronoi diagrams, Power Diagrams? For example, as explored in "Equitable Partitioning Policies for Robotic Networks," which cites your work? –  Joseph O'Rourke Jun 26 '12 at 0:07
@Joseph O'Rourke: Hi Joseph! Yes, actually, one can prove that when $u_i(x) = \|x-p_i\|$ for a point $p_i$, the optimal solution to both is a multiplicatively weighted Voronoi diagram; I proved this (for the first of the two problems I gave in this post) in the paper "Dividing a territory among several facilities" on my website. –  John Gunnar Carlsson Jun 26 '12 at 0:28
Perhaps the fair-division tag is appropriate here? –  Joel Reyes Noche Jul 18 '12 at 23:39