Répartition équitable du gâteau bidimensionnel

Je m'intéresse aux procédures de partage équitable des terres (c.-à-d. Partage sans envie, ou au moins partage proportionnel).

Contrairement au problème bien étudié de division des gâteaux, la division des terres est bidimensionnelle, c'est-à-dire que les préférences des utilisateurs peuvent varier à la fois horizontalement et verticalement. Par conséquent, il n'est pas pratique de limiter l'algorithme aux coupes parallèles.

La seule référence que j'ai trouvée jusqu'à présent est Karthik Iyer et Michael Huhns, 2007 . Ils disent que "nous n'avons trouvé jusqu'à présent aucune solution constructive (algorithmique) au problème générique de division des terres. Tous les articles ont proposé des solutions existentielles à des versions qualifiées du problème."

Ils prouvent eux-mêmes un algorithme O (n ^ 2) pour la division proportionnelle des terres, avec certaines limitations (par exemple, chacun des n agents doit marquer n régions rectangulaires avec l'utilité 1 / n, et si les rectangles ne se chevauchent pas trop, l'algorithme garantit que chaque agent obtient un de ses rectangles).

Connaissez-vous de nouvelles références sur ce problème? Je m'intéresse spécifiquement aux algorithmes pratiques, et ils peuvent être approximatifs.

Les auteurs que vous citez ont un autre article sur le sujet .

Seriez-vous satisfait d'un modèle qui suppose que les propriétés des surfaces à allouer peuvent être résumées par un ensemble arbitrairement grand mais fini de paramètres unidimensionnels (par exemple longueur, profondeur, point le plus au nord, point le plus à l'est, ... vraiment comme autant que vous voulez mais fini)?

Si cela vous satisfait et que vous êtes d'accord avec l'hypothèse que les gens ont des préférences sur les surfaces telles que décrites par les valeurs de ces paramètres, vous pourriez trouver des informations utiles dans la théorie de la répartition équitable des faisceaux de biens multiples. Une excellente introduction (et gratuite) est «Fair Allocation Rules» de William Thomson .

Bien sûr, lorsque les dimensions représentent des paramètres décrivant les formes à allouer, vous avez probablement des préférences inhabituelles difficiles à travailler et qui ne correspondent pas bien aux résultats existants. Cela vaut peut-être la peine d'essayer ...

Je suppose que vous pourriez résoudre le problème en réduisant la dimensionnalité du problème. Par exemple, vous pouvez diviser le terrain en zones distinctes (manuellement ou en utilisant un algorithme approprié). Ensuite, vous pouvez utiliser n'importe quel algorithme unidimensionnel discret comme la méthode d'enchère scellée décrite dans http://www.colorado.edu/education/DMP/fair_division.html .

Je n'ai pas trouvé de réponse appropriée, j'ai donc dû en écrire une moi-même . C'était la première partie de mon doctorat. thèse. Il y a encore beaucoup de questions ouvertes dans ce domaine.