Fair cake-cutting algorithms with real land-value data

摘要

Fair division of land is an important practical problem that is commonly handled either by hiring assessors or by selling and dividing the proceeds. A third way to divide land fairly is via algorithms for fair cake-cutting. Such un-intermediated methods are not only cheaper than an assessor but also theoretically fairer since they guarantee each agent a fair share according to his/her value function. However, the current theory of fair cake-cutting is not yet ready to optimally share a plot of land, and such algorithms are seldom used in practical land division. We attempt to narrow the gap between theory and practice by presenting several heuristic adaptations of famous algorithms for one-dimensional cake-cutting to two-dimensional land-division. The heuristics are evaluated using extensive simulations on real land-value data maps from three different data sets and a fourth (control) map of random values. The simulations compare the performance of cake-cutting algorithms to sale and assessor division in various performance metrics, such as utilitarian welfare, egalitarian welfare, Nash social welfare, envy, and geometric shape. The cake-cutting algorithms perform better in most metrics. However, their performance is greatly influenced by technical implementation details and heuristics that are often overlooked by theorists. We also propose a new protocol for practical cake-cutting using a dynamic programming approach and discuss its run-time complexity versus performance trade-off. Our new protocol performs better than the examined classic cake-cutting algorithms on most metrics. Experiments to assess the amount that a strategic agent can gain from reporting false preferences are also presented. The results show that the problem of strategic manipulation is much less severe than the worst-case predicted by theory.