La siguiente variante del problema del corte justo de la torta fue introducida por Ted Hill en 1983. [1]
Existe un territorio D adyacente a n países. Cada país valora los diferentes subconjuntos de D de manera diferente. Los países desearían dividir D de manera justa entre ellos, donde "justo" significa una división proporcional . Además, la porción 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 reparto justo de la porción .
Formalmente, cada país C i debe recibir una pieza disjunta de D , marcada D i , de modo que una porción de la frontera entre C i y D esté contenida en el interior de C i ∪ D i .
Hay casos en los que no se puede solucionar el problema:
En 1983, Hill demostró que, si cada punto de 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]
Cuatro años después, Anatole Beck describió un protocolo para lograr dicha división. [2] En esencia, el protocolo es una elaboración del protocolo del último reductor . Permite a los países ofertar por partes de D , le da la oferta más pequeña a su ofertante y divide el resto entre los n − 1 países restantes. Se necesitan algunas variaciones para garantizar que se cumpla la restricción de adyacencia.
Cuando D está simplemente conexo , se utiliza el siguiente algoritmo.
1. Encuentre una función de Riemann h que asigne D al disco unitario , de modo 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 dicha h se prueba mediante un argumento de conteo).
2. Pedir a cada país que dibuje, en el mapa de la unidad 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.
3. Encuentra el disco D 1 con el radio más pequeño, r 1 .
Hay dos casos.
4. Si D 1 fue extraído por un solo país, digamos C i , entonces entreguemos este disco a C i . Su valor para los demás países es estrictamente menor que 1/ n , por lo que podemos darle a C i una pequeña pieza adicional que lo conecte con su disco asignado.
Para ello, se traza un sector que conecta D 1 con la imagen del límite entre C i y D . Que cada país (excepto C i ) recorte este sector de forma que todos los países valoren la unión del disco y el sector como máximo 1/ n . Esto es posible gracias a la condición de que el valor de todos los radios a partir del origen sea 0. Se asigna a C i la unión de D 1 y el sector recortado.
El resto está simplemente conexo y tiene un valor de al menos ( n − 1)/ n para los n − 1 países restantes, por lo que la división puede proceder recursivamente en el paso 1.
Si D 1 fue dibujado por k > 1 países, entonces se requieren subastas más sofisticadas para encontrar un país al cual podamos darle un disco y un sector de conexión.
5. Elija un país ganador arbitrario y llámelo el declarante , C 1 . Deje que agregue un sector que conecte D 1 con su territorio actual y deje que los otros países recorten ese sector de manera que:
6. Supongamos que cada uno de los países ganadores ofrece un nuevo radio r (menor que su primera oferta), de modo que el valor del sector recortado más el disco de radio r sea exactamente 1/ n . Seleccione el disco más pequeño de esos, D 2 . Nuevamente, hay dos casos:
Si C 1 es uno de los países que ofertan D 2 , entonces simplemente le damos D 2 (que es ligeramente más pequeño que el D 1 original ) y el sector de conexión. C 1 acordó que el valor es 1/ n y los otros países acordaron que es como máximo 1/ n , por lo que podemos proceder recursivamente en el paso 1.
De lo contrario, C 1 acepta que el valor total de D 2 más el sector de conexión es menor que 1/ n . Todos los no ganadores también deben aceptar esto, ya que D 2 es menor que D 1 . Por lo tanto, C 1 y todos los demás países que aceptan esto son eliminados del conjunto de ganadores.
7. De entre los ganadores restantes, elija un nuevo declarante C 2 . Deje que agregue otro sector que conecte D 2 con su territorio actual y deje que los demás países recorten ese sector como en el paso 5.
Nótese que ahora D 2 está conectado a dos territorios diferentes – C 1 y C 2 . Esto es un problema porque hace que el territorio restante esté desconectado. Para resolver esto, se le permite a C 2 tomar otro sector, esta vez de longitud menor a 1 para que no dañe la conectividad. [2] Ese tercer sector es nuevamente recortado por todos los países como en el paso 5. A cambio, se le exige a C 2 que renuncie a una parte del sector que conecta D 2 con C 1 , cuyo valor es igual al valor del tercer sector que recibió.
La asignación de candidatos de C 2 ahora contiene las siguientes partes: D 2 , un único sector de longitud 1 que conecta D 2 con C 2 y dos sectores cortos que no llegan al borde de D . El valor de esta construcción para C 2 es 1/ n , su valor para los no ganadores es menor que 1/ n y su valor para los ganadores restantes es como máximo 1/ n .
Este proceso continúa con los ganadores restantes, hasta que solo quede un único ganador.
Si el territorio D está k -conectado con un k finito , entonces la división puede proceder por inducción en k .
Cuando k = 1, D es simplemente conexo y se puede dividir por el protocolo de la sección anterior.
En caso contrario ( k > 1), marque el límite exterior de D por B 1 y sus límites internos por B 2 , ..., B k .
Encuentre una línea L que conecte el límite exterior B 1 con el límite interior B k , de modo que todos los países valoren L como 0. Esto es posible mediante el siguiente argumento de conteo. Existe una infinidad incontable de líneas disjuntas por pares que conectan B 1 y B k y están contenidas en D . Pero la medida de D es finita, por lo que el número de líneas con una medida positiva debe ser finito.
El conjunto D \ L es ( k − 1)-conexo. Se divide recursivamente y luego se asigna L arbitrariamente a cualquier país adyacente a él. Esto no afecta la equidad de la asignación, ya que el valor de L es 0 para todos los países.