10
$\begingroup$

I am interested in procedures for fair division of land (i.e. envy-free division, or at least proportional division).

In contrast to the well-studied cake-division problem, land-division is two-dimensional, i.e., the preferences of the users may vary both horizontally and vertically. Therefore, it is not practical to limit the algorithm to parallel cuts.

The only reference I found so far is Karthik Iyer and Michael Huhns, 2007. They say that "We have not come across any constructive (algorithmic) solutions so far to the generic land division problem. All the papers have offered existential solutions to qualified versions of the problem."

They themselves prove an O(n^2) algorithm for proportional land division, with certain limitations (e.g. each of the n agents must mark n rectangular regions with utility 1/n, and if the rectangles don't overlap too much, the algorithm guarantees that each agent gets one of its rectangles).

Do you know of any newer references on this problem? I am interested specifically in practical algorithms, and they may be approximate.

$\endgroup$
  • $\begingroup$ Did you read the Wikipedia article on fair division? $\endgroup$ – Pål GD Mar 28 '13 at 19:17
  • 2
    $\begingroup$ Yes, all references there deal with 1-dimensional preferences. $\endgroup$ – Erel Segal-Halevi Mar 28 '13 at 19:40
3
$\begingroup$

The authors you cite have another paper on the topic.

Would you be satisfied with a model which assumes that the properties of the surfaces to be allocated can be summarized by an arbitrarily large but finite set of one-dimensional parameters (say length, depth, northmost point, eastmost point,... really as many as you want but finite) ?

If this is satisfying to you, and you are ok with assuming that people have preferences over surfaces as described by the values of these parameters, you might find useful insights in the theory of fair allocation of bundles of multiple goods. A great (and free) introduction is "Fair Allocation Rules" by William Thomson.

Of course when the dimensions represent parameters describing the shapes to be allocated, you are likely to have unusual preferences which are hard to work with and do not fit nicely with the existing results. Might be worth giving it a try though...

$\endgroup$
2
$\begingroup$

I suppose you could address the issue by reducing the dimensionality of the problem. For example, you could divide the land into discrete areas (either manually or using a suitable algorithm). Then you could use any discrete one dimensional algorithm like the Sealed bid method described in http://www.colorado.edu/education/DMP/fair_division.html .

$\endgroup$
2
$\begingroup$

I did not find a suitable answer, so I had to write one myself. It was the first part of my Ph.D. thesis. There are still a lot of open questions in this field.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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