patternMinor
Fair division of two-dimensional cake
Viewed 0 times
fairdivisiontwodimensionalcake
Problem
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.
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.
Solution
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...
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...
Context
StackExchange Computer Science Q#10877, answer score: 3
Revisions (0)
No revisions yet.