# Fair division of two-dimensional cake

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.

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