Equitable division of a contiguous resource - MathOverflow

Equitable division of a contiguous resource

2012-06-25T22:22:49Z

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.

Answer by Steven Landsburg for Equitable division of a contiguous resource

2012-06-26T00:33:54Z

This paper by Berliant, Dunz and Thomson is surely relevant.

Answer by Juan Camilo Gamboa for Equitable division of a contiguous resource

2012-07-04T00:59:01Z

I think your first problem is similar to the fair-division/cake-cutting problem as mentioned in the other answer and comments: find an allocation of parts of a continuous good among n players, with various optimality criteria (max sum, max min, leximin). Two papers very related to your work are one by Dubins and Spanier and another by Marco Dall'Aglio, based on the Dubins-Spanier paper.

In the work by Dall'Aglio, they state relationships between the max min and the max sum problem. In one of the more recent papers, they provide an algorithm for finding max min allocation: the solution is a max sum allocation weighted by the dual parameters of the max min problem. They search for the dual parameters using a subgradient method. I think this wor is related to your post, you can solve the max min problem by getting an equitable solution to the max sum problem. I guess that by replacing the utility with a concave utility, you are driving the optimal solutions towards the equitable solutions.