Divisão justa de bolo bidimensional

Estou interessado em procedimentos para a divisão justa da terra (ou seja, divisão sem inveja, ou pelo menos divisão proporcional).

Em contraste com o bem estudado problema de divisão de bolos, a divisão de terras é bidimensional, ou seja, as preferências dos usuários podem variar horizontal e verticalmente. Portanto, não é prático limitar o algoritmo a cortes paralelos.

A única referência que encontrei até agora é Karthik Iyer e Michael Huhns, 2007 . Eles dizem que "até agora não encontramos soluções construtivas (algorítmicas) para o problema genérico da divisão de terras. Todos os trabalhos ofereceram soluções existenciais para versões qualificadas do problema".

Eles mesmos provam um algoritmo O (n ^ 2) para divisão proporcional da terra, com certas limitações (por exemplo, cada um dos n agentes deve marcar n regiões retangulares com utilidade 1 / n, e se os retângulos não se sobrepuserem muito, o algoritmo garante que cada agente obtenha um de seus retângulos).

Você conhece alguma referência mais recente sobre esse problema? Estou interessado especificamente em algoritmos práticos, e eles podem ser aproximados.

Os autores que você cita têm outro artigo sobre o assunto .

Você ficaria satisfeito com um modelo que assume que as propriedades das superfícies a serem alocadas podem ser resumidas por um conjunto arbitrariamente grande, mas finito, de parâmetros unidimensionais (por exemplo, comprimento, profundidade, ponto mais ao norte, ponto mais ao leste, ... realmente como quantos você quiser, mas finito)?

Se isso é satisfatório para você, e você concorda em assumir que as pessoas têm preferências sobre as superfícies, conforme descrito pelos valores desses parâmetros, poderá encontrar informações úteis na teoria da alocação justa de pacotes de vários produtos. Uma ótima introdução (e gratuita) é "Fair Allocation Rules", de William Thomson .

Obviamente, quando as dimensões representam parâmetros que descrevem as formas a serem alocadas, é provável que você tenha preferências incomuns, difíceis de trabalhar e que não se encaixam bem nos resultados existentes. Pode valer a pena experimentá-lo embora ...

Suponho que você possa resolver o problema reduzindo a dimensionalidade do problema. Por exemplo, você pode dividir o terreno em áreas discretas (manualmente ou usando um algoritmo adequado). Em seguida, você pode usar qualquer algoritmo unidimensional discreto como o método de lance selado descrito em http://www.colorado.edu/education/DMP/fair_division.html .

Como não encontrei uma resposta adequada, tive que escrever uma . Foi a primeira parte do meu doutorado. tese. Ainda existem muitas questões em aberto nesse campo.