Equitable division of a contiguous resource - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T15:59:32Z http://mathoverflow.net/feeds/question/100638 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/100638/equitable-division-of-a-contiguous-resource Equitable division of a contiguous resource John Gunnar Carlsson 2012-06-25T22:22:49Z 2012-07-18T19:22:00Z <p>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.</p> <p>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:</p> <p>$\text{maximize}_{R_1,\dots,R_n}\lbrace\min_i \iint_{R_i} f(x)u_i(x) dx\rbrace$ subject to</p> <p>$\bigcup_i R_i = R$ and $R_i \cap R_j = \emptyset \text{ for all }i\neq j$</p> <p>It is easy to verify that, at the optimal solution $R_1^*,\dots,R_n^*$, all of the agents' utilities are equal.</p> <p>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 <i>total</i> utilities of the agents, but under a logarithmic utility function, and imposing constraints on the populations in each piece:</p> <p>$\text{maximize}_{R_1,\dots,R_n}\lbrace\sum_i \iint_{R_i} f(x)\log(u_i(x)) dx\rbrace$ subject to</p> <p>$\iint_{R_i} f(x) dx = q_i^*$</p> <p>$\bigcup_i R_i = R$ and $R_i \cap R_j = \emptyset \text{ for all }i\neq j$</p> <p>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</p> <p><a href="http://menet.umn.edu/~jgc/mathoverflow.m" rel="nofollow">http://menet.umn.edu/~jgc/mathoverflow.m</a></p> <p>if anyone is interested.</p> http://mathoverflow.net/questions/100638/equitable-division-of-a-contiguous-resource/100646#100646 Answer by Steven Landsburg for Equitable division of a contiguous resource Steven Landsburg 2012-06-26T00:33:54Z 2012-06-26T00:33:54Z <p><a href="http://www.landsburg.org/bdt.pdf" rel="nofollow">This paper</a> by Berliant, Dunz and Thomson is surely relevant. </p> http://mathoverflow.net/questions/100638/equitable-division-of-a-contiguous-resource/101275#101275 Answer by Juan Camilo Gamboa for Equitable division of a contiguous resource Juan Camilo Gamboa 2012-07-04T00:59:01Z 2012-07-04T18:33:41Z <p>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 <a href="http://www.jstor.org/stable/10.2307/2311357" rel="nofollow">Dubins and Spanier</a> and another by <a href="http://adsabs.harvard.edu/abs/2001JCoAM.130...17D" rel="nofollow">Marco Dall'Aglio</a>, based on the Dubins-Spanier paper. </p> <p>In the work by Dall'Aglio, they state relationships between the max min and the max sum problem. In one of the more <a href="http://arxiv.org/pdf/1110.4241.pdf" rel="nofollow">recent papers</a>, 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.</p>