Fair cake-cutting algorithms with real land-value data

Itay Shtechman, Rica Gonen, Erel Segal-HaLevi

פרסום מחקרי: פרסום בכתב עתמאמרביקורת עמיתים


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.

שפה מקוריתאנגלית
מספר המאמר39
כתב עתAutonomous Agents and Multi-Agent Systems
מספר גיליון2
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - אוק׳ 2021

הערה ביבליוגרפית

Publisher Copyright:
© 2021, Springer Science+Business Media, LLC, part of Springer Nature.

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Fair cake-cutting algorithms with real land-value data'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי