Hay un territorio D adyacente a n países. Cada país valora los diferentes subconjuntos de D de manera diferente. A los países les gustaría dividir D equitativamente entre ellos, donde "justo" significa una división proporcional . Además, la parte asignada a cada país debe estar conectada y adyacente a ese país . Esta restricción geográfica distingue este problema del clásico corte de torta justo .
Formalmente, cada país C i debe recibir una parte disjunta de D , marcada como D i , tal que una parte de la frontera entre C i y D esté contenida en el interior de C i ∪ D i .
En 1983, Hill demostró que, si cada punto en D tiene un valor de 0 para todos los países, y el límite de D tiene un valor de 0 para todos los países, entonces existe una división proporcional con la restricción de adyacencia. Su prueba fue solo existencial: no se describió ningún algoritmo. [1]
4 años después, Anatole Beck describió un protocolo para lograr tal división. [2] En esencia, el protocolo es una elaboración del protocolo del último disminuidor . Permite que los países pujen por partes de D , da la oferta más pequeña a su postor y divide el resto entre los n − 1 países restantes. Se necesitan algunas variaciones para garantizar que se satisfaga la restricción de adyacencia.
1. Encuentre un mapeo h de Riemann que mapee D al disco unitario , tal que para todos los países, el valor de cada círculo centrado en el origen sea 0 y el valor de cada radio desde el origen sea 0 (la existencia de tal h se prueba mediante un argumento de conteo).
2. Pida a cada país que dibuje, en el mapa del disco unitario h ( D ), un disco centrado en el origen con un valor de 1/ n . Esto es posible gracias a la condición de que el valor de todos los círculos centrados en el origen sea 0.