2
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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 $\endgroup$ Jun 25, 2012 at 22:41
  • $\begingroup$ 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? $\endgroup$ Jun 26, 2012 at 0:07
  • $\begingroup$ @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. $\endgroup$ Jun 26, 2012 at 0:28
  • 1
    $\begingroup$ Perhaps the fair-division tag is appropriate here? $\endgroup$
    – JRN
    Jul 18, 2012 at 23:39

2 Answers 2

1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.