División de tareas

La división de tareas es un problema de división justa en el que el recurso dividido es indeseable, de modo que cada participante quiere obtener lo menos posible. Es la imagen especular del problema de cortar la torta , en el que el recurso dividido es deseable de modo que cada participante quiere obtener lo máximo posible. Ambos problemas tienen recursos heterogéneos , lo que significa que los recursos no son uniformes. En la división de tortas, las tortas pueden tener bordes, esquinas y porciones centrales junto con diferentes cantidades de glaseado. Mientras que en la división de tareas, hay diferentes tipos de tareas y diferentes cantidades de tiempo necesarias para terminar cada tarea. De manera similar, ambos problemas suponen que los recursos son divisibles. Las tareas pueden ser infinitamente divisibles, porque el conjunto finito de tareas puede dividirse por tarea o por tiempo. Por ejemplo, una carga de ropa podría dividirse por la cantidad de prendas de vestir y/o por la cantidad de tiempo empleado en cargar la máquina. Sin embargo, los problemas difieren en la deseabilidad de los recursos. El problema de la división de tareas fue introducido por Martin Gardner en 1978. ^[1]

La división de tareas domésticas se denomina a menudo división justa de males , en contraste con el problema más común llamado "división justa de bienes" (un mal económico es lo opuesto a un bien económico). Otro nombre es problema de trabajo sucio . El mismo recurso puede ser bueno o malo, dependiendo de la situación. Por ejemplo, supongamos que el recurso a dividir es el patio trasero de una casa. En una situación de división de herencia, este patio se consideraría bueno, ya que cada heredero querría tener la mayor cantidad de tierra posible, por lo que es un problema de corte de pastel. Pero en una situación de división de tareas domésticas como cortar el césped , este patio se consideraría malo, ya que cada hijo probablemente querría tener la menor cantidad de tierra posible para cortar, por lo que es un problema de corte de tareas.

Algunos resultados de un reparto justo de la torta se pueden trasladar fácilmente al escenario de reparto de tareas. Por ejemplo, el procedimiento de dividir y elegir funciona igualmente bien en ambos problemas: uno de los socios divide el recurso en dos partes que son iguales a sus ojos, y el otro socio elige la parte que es "mejor" a sus ojos. La única diferencia es que "mejor" significa "más grande" en el reparto de la torta y "más pequeño" en el reparto de tareas. Sin embargo, no todos los resultados son tan fáciles de trasladar.

La definición de división proporcional en el reparto de tareas es la imagen especular de su definición en el reparto de tortas: cada socio debe recibir una porción que valga, según su propia función de desutilidad personal , como máximo el valor total (donde es el número total de socios): ${\estilo de visualización i}$$Estilo de visualización X_{i}}$ ${\estilo de visualización 1/n}$${\estilo de visualización n}$

${\displaystyle \forall i:V_{i}(X_{i})\leq V_{i}(Entero)/n}$

La mayoría de los protocolos para cortar la torta proporcionalmente se pueden trasladar fácilmente al corte de las tareas domésticas. Por ejemplo:

• Para utilizar el protocolo del último reductor : pídale a un agente que corte un trozo que valga exactamente para él. Si cualquier otro agente considera que ese trozo es demasiado grande, puede cortarlo más pequeño hasta que valga exactamente para él, y así sucesivamente. El "último reductor" recibe el trozo que vale exactamente para él y, al menos, para los demás.${\estilo de visualización 1/n}$${\estilo de visualización 1/n}$${\estilo de visualización 1/n}$${\estilo de visualización 1/n}$
• Para utilizar el protocolo Even-Paz : pida a cada agente que marque la línea de valor medio, asegurándose de que todas las líneas sean paralelas. Corte la torta en la mediana de las líneas, divida a los agentes en dos grupos de agentes y deje que cada mitad divida recursivamente la parte que NO contiene su línea.${\estilo de visualización n/2}$

Los procedimientos de división equitativa y de división exacta funcionan igualmente bien para las tortas y para las tareas domésticas, ya que garantizan valores iguales. Un ejemplo es el procedimiento del cuchillo móvil de Austin , que garantiza a cada socio una porción que valora exactamente como 1/ n del total.

La definición de ausencia de envidia en el corte de tareas domésticas es la imagen especular de su definición en el corte de la torta: cada socio debería recibir un pedazo que valga, de acuerdo con su propia función de desutilidad personal, como máximo tanto como cualquier otro pedazo: ${\estilo de visualización i}$$Estilo de visualización X_{i}}$

${\displaystyle \para todo i,j:V_{i}(X_{i})\leq V_{i}(X_{j})}$

Para dos socios, dividir y elegir produce un recorte de tareas sin envidia. Sin embargo, para tres o más socios, la situación es mucho más complicada. La principal dificultad está en el recorte : la acción de recortar un trozo para que sea igual a otro trozo (como se hace, por ejemplo, en el protocolo Selfridge-Conway ). Esta acción no se puede trasladar fácilmente al escenario de recorte de tareas.

Reza Oskui fue el primero en sugerir un procedimiento de corte de tareas para tres parejas. Su trabajo nunca se publicó formalmente; se describe en ^[2] páginas 73-75. Es similar al protocolo Selfridge-Conway , pero más complicado: requiere 9 cortes en lugar de 5.

A continuación, los socios se llaman Alice, Bob y Carl.

Primer paso. Alice divide la tarea en tres partes iguales a sus ojos (este es también el primer paso del protocolo Selfidge-Conway). Bob y Carl especifican su parte más pequeña. El caso fácil es que no estén de acuerdo, ya que entonces podemos darle a cada socio una parte más pequeña y listo. El caso difícil es que estén de acuerdo. Llamemos a la parte que Bob y Carl consideran más pequeña X1, y a las otras dos partes X2 y X3.

Segundo paso. Pedimos a Bob y Carl que marquen, en cada una de las piezas X2 y X3, dónde hay que cortar la pieza para que sea igual a X1. Consideramos varios casos.

Caso 1. Los ajustes de Bob son más débiles. Es decir, si Bob ajusta X2 a X2' y X3 a X3', de modo que tanto X2' como X3' son para él tan pequeños como X1, entonces Carl piensa que X1 sigue siendo la pieza más pequeña, ligeramente más pequeña que X2' y X3'. Entonces, la siguiente división parcial está libre de envidia:

• Carl obtiene X1;
• Alice obtiene el valor más pequeño de X2' y X3' (ambos son más pequeños que X1 para ella);
• Bob obtiene la pieza que no fue tomada por Alice (ambas son iguales a X1 para él).

Ahora tenemos que dividir los recortes E2 y E3. Para cada recorte se hace lo siguiente:

• Bob lo corta en tres trozos iguales.
• Los agentes eligen las piezas en el orden: Carl, Alice, Bob.

Carl no tiene envidia porque eligió primero; Bob no tiene envidia porque cortó; Alice no tiene envidia porque tenía una ventaja (negativa) sobre Carl: en el primer paso, Carl tomó X1, mientras que Alice tomó una pieza que es más pequeña que X1 por un máximo de (E2, E3), mientras que en el último paso, Alice tomó dos piezas que valen como máximo (E2+E3)/2.

Caso 2. Los ajustes de Carl son más débiles. Es decir, si Carl ajusta X2 a X2' y X3 a X3', de modo que tanto X2' como X3' son para él tan pequeños como X1, entonces Bob piensa que X1 sigue siendo la pieza más pequeña, ligeramente más pequeña que X2' y X3'. Luego, procedemos como en el caso 1, con los roles de Bob y Carl intercambiados.

Caso 3. El ajuste de Bob es más débil en X2 y el de Carl es más débil en X3. Es decir, si Bob ajusta X2 a X2', que es igual a X1 para él, y Carl ajusta X3 a X3', que es igual a X1 para él, entonces:

• Para Carl: X2' >= X1 = X3'
• Para Bob: X3' >= X1 = X2'

Entonces, la siguiente división parcial está libre de envidia:

• Alice obtiene el valor más pequeño de X2' y X3' (ambos son más pequeños que X1 para ella);
• Bob obtiene X2' (si no fue tomado por Alice) o X1 (en caso contrario);
• Carl obtiene X3' (si no fue tomado por Alice) o X1 (en caso contrario).

Los recortes, E2 y E3, se dividen de manera similar al Caso 1.

Oskui también mostró cómo convertir los siguientes procedimientos con cuchillo móvil de cortar una torta a cortar una tarea:

• Procedimiento de cuchillas móviles de Stromquist
• El procedimiento del cuchillo giratorio. ^{[2] : 77–78}

Peterson y Su ^[3] propusieron un procedimiento diferente para tres compañeros. Es más simple y simétrico que el procedimiento de Oskui, pero no es discreto, ya que se basa en un procedimiento de cuchillo móvil. Su idea clave es dividir las tareas en seis partes y luego darle a cada compañero las dos partes que considere al menos tan pequeñas como las que reciben los otros jugadores.

Paso uno. Divida las tareas en 3 partes usando cualquier método de corte de pastel que no genere envidia y asigne cada parte al jugador que la encuentre más grande.

Paso dos.

• Utilizando el procedimiento de cuchillo móvil de Austin , divida la pieza 1 en dos porciones que los socios 1 y 2 consideren iguales. Deje que el socio 3 elija la porción que le parezca más pequeña y entregue la otra porción al socio 2.
• De manera similar, divida la pieza 2 en dos porciones que los socios 2 y 3 consideren iguales, deje que el socio 1 elija la porción más pequeña y le dé la otra porción al socio 3.
• De manera similar, divida la pieza 3 en dos porciones que los socios 3 y 1 consideren iguales, deje que el socio 2 elija la porción más pequeña y le dé la otra porción al socio 1.

Análisis. El socio 1 tiene dos porciones: una de la porción 2 y otra de la porción 3. A los ojos del socio 1, la porción de la porción 2 es más pequeña que la porción que le dio al socio 3, y la porción de la porción 3 es más pequeña que la porción que le dio al socio 2. Además, ambas porciones son más pequeñas que las porciones de la porción 1, ya que la porción 1 es más grande que la porción 2 y la porción 3 (según el Paso Uno). Por lo tanto, el socio 1 cree que su porción es (débilmente) más pequeña que cada una de las otras dos porciones. Las mismas consideraciones se aplican a los socios 2 y 3. Por lo tanto, la división está libre de envidia.

Peterson y Su extienden su procedimiento continuo a cuatro socios. ^[3]

La existencia de un procedimiento discreto para cinco o más socios permaneció como una cuestión abierta, hasta que en 2009 Peterson y Su publicaron un procedimiento para n socios. ^[4] Es análogo al procedimiento de Brams-Taylor y utiliza la misma idea de ventaja irrevocable . En lugar de recortar, utilizan la adición de la reserva .

Peterson y Su proporcionaron un procedimiento con cuchillo móvil para la división de tareas entre cuatro personas. Dehghani et al. ^[5] proporcionaron el primer protocolo discreto y acotado sin envidia para la división de tareas entre cualquier número de agentes.

Los siguientes procedimientos se pueden adaptar para dividir un pastel malo con pedazos desconectados:

• Procedimiento de bisturí rotatorio de Robertson-Webb ^{[2] : ejercicio 5.10}
• Procedimiento de cuchillas móviles de Stromquist ^{[2] : ejercicio 5.11}
• Protocolos Simmons-Su . Simmons desarrolló originalmente un protocolo para cortar la torta sin envidia de manera aproximada con piezas conectadas, basado en el lema de Sperner . Su demostró, utilizando un lema dual, que se puede utilizar un protocolo similar para la división aproximada de tareas sin envidia. En particular, demuestra que siempre existe una división de tareas sin envidia con piezas conectadas.

Heydrich y van Stee ^[6] calculan el precio de la equidad en la división de tareas cuando las piezas deben estar conectadas.

Tal vez sea posible utilizar procedimientos de división de tareas para dividir el trabajo y el costo de reducir el cambio climático entre las naciones. Los problemas surgen con la moral y la cooperación entre las naciones. Sin embargo, el uso de procedimientos de división de tareas reduce la necesidad de una autoridad supranacional para dividir y supervisar el trabajo de esas naciones. ^[7]

Otro uso para la división de tareas sería el problema de la armonía en el alquiler .

• Corte de pastel sin envidia
• Malo (economía)
• Armonía en el alquiler