La división de tareas es un problema de división justa en el que el recurso dividido es indeseable, por lo que cada participante quiere obtener la menor cantidad posible. Es la imagen especular del problema de la tarta justa , en el que el recurso dividido es deseable para que cada participante quiera obtener la mayor cantidad posible. Ambos problemas tienen heterogeneidadrecursos, lo que significa que los recursos no son uniformes. En la división de pasteles, los pasteles pueden tener bordes, esquinas y partes intermedias 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 asumen 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 el número de prendas de vestir y / o por la cantidad de tiempo que se dedica a cargar la máquina. Sin embargo, los problemas difieren en la conveniencia de los recursos. El problema de la división de tareas fue introducido por Martin Gardner en 1978. [1]
La división de tareas a menudo se denomina división justa de cosas malas , en contraste con el problema más común llamado "división justa de bienes". Otro nombre es problema del trabajo sucio . El mismo recurso puede ser bueno o malo, según la situación. Por ejemplo, suponga que el recurso que se va a dividir es el patio trasero de una casa. En una situación de herencia dividida, este patio se consideraría bueno, ya que a cada heredero le gustaría tener la mayor cantidad de tierra posible, por lo que es un problema de tarta. Pero en una situación en la que se dividen las tareas del hogar, como cortar el césped , este jardín se consideraría malo, ya que a cada niño probablemente le gustaría tener la menor cantidad de tierra posible para cortar, por lo que es un problema de quehaceres domésticos .
Algunos resultados de un corte de pastel justo se pueden traducir fácilmente al escenario de corte 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" al cortar pasteles y "más pequeño" al cortar los quehaceres. Sin embargo, no todos los resultados son tan fáciles de traducir. Se dan más detalles a continuación.
Tarea proporcional
La definición de división proporcional en el corte de tareas es la imagen especular de su definición en el corte de pasteles: cada socio debería recibir una pieza que vale, de acuerdo con su propia función de disfunción personal , a lo sumo del valor total (donde es el número total de socios):
La mayoría de los protocolos para el corte proporcional de pasteles se pueden traducir fácilmente al corte de tareas. Por ejemplo:
- Para usar el protocolo del último reductor : pídale a un agente que corte una pieza que valga exactamentepara él. Si cualquier otro agente siente que esta pieza es demasiado pequeña, puede agrandarla hasta que valga exactamentepara él, y así sucesivamente. La "última ampliadora" recibe la pieza, que vale exactamente para el y al menos para los demás.
- Para usar 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 el pastel en la mediana de las líneas, divida los agentes en dos grupos de agentes, y deje que cada mitad divida recursivamente la pieza que NO contiene su línea.
Tareas de trabajo equitativas y exactas
Los procedimientos para la división equitativa y la división exacta funcionan igualmente bien para pasteles y para las tareas del hogar, ya que garantizan valores iguales. Un ejemplo es el procedimiento de cuchilla móvil de Austin , que garantiza a cada socio una pieza que valora exactamente como 1 / n del total.
Cortar las tareas sin envidia
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 pasteles: cada socio debería recibir una pieza que vale, según su propia función de desutilidad personal, a lo sumo tanto como cualquier otra pieza:
Para dos socios, dividir y elegir produce un corte 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 una pieza para igualarla a otra pieza (como se hace, por ejemplo, en el protocolo Selfridge-Conway ). Esta acción no se puede traducir fácilmente al escenario de recortes de tareas.
Procedimiento discreto de Oskui para tres socios
Reza Oskui fue el primero que sugirió un procedimiento de reducción de tareas para tres socios. 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 cortes.
A continuación, los socios se llaman Alice, Bob y Carl.
Paso uno. Alice corta la tarea en tres partes iguales a sus ojos (este es también el primer paso en el protocolo Selfidge-Conway). Bob y Carl especifican su pieza más pequeña. El caso fácil es que no estén de acuerdo, ya que entonces podemos darle a cada socio una pieza más pequeña y listo. Lo difícil es que estén de acuerdo. Llamemos a la pieza que tanto Bob como Carl ven como la más pequeña, X1, y las otras dos piezas, X2 y X3.
Segundo paso. Pida a Bob y Carl que marquen, en cada una de las piezas X2 y X3, dónde debe cortarse la pieza para que sea igual a X1. Consideramos varios casos.
Caso 1. Los adornos de Bob son más débiles. Es decir, si Bob recorta 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 una 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 más pequeño de X2 'y X3' (ambos son más pequeños que X1 para ella);
- Bob obtiene la pieza que no se llevó Alice (ambos son iguales a X1 para él).
Ahora tenemos que dividir las guarniciones E2 y E3. Para cada recorte, se hace lo siguiente:
- Bob lo corta en tres partes iguales.
- El agente elige piezas en el orden: Carl, Alice, Bob.
Carl no siente envidia porque eligió primero; Bob no tiene envidia desde que cortó; Alice no tiene envidia ya que 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 max (E2, E3), mientras que en el último paso, Alice tomó dos piezas que valen como máximo (E2 + E3) / 2.
Caso 2. Los adornos de Carl son más débiles. Es decir, si Carl recorta X2 a X2 'y X3 a X3', de modo que tanto X2 'y X3' son para él tan pequeños como X1, entonces Bob piensa que X1 sigue siendo una 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 recorta X2 a X2 'que es igual a X1 para él, y Carl recorta 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 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 (de lo contrario);
- Carl obtiene X3 '(si no fue tomado por Alice) o X1 (de lo contrario).
Los recortes, E2 y E3, se dividen de forma similar al Caso 1.
Oskui también mostró cómo convertir los siguientes procedimientos de cuchillos móviles de cortar pasteles a cortar tareas domésticas:
- Procedimiento de cuchillas móviles Stromquist
- El procedimiento de la cuchilla giratoria. [2] : 77–78
Los procedimientos continuos de Peterson y Su para tres y cuatro socios
Peterson y Su [3] sugirieron un procedimiento diferente para tres socios. Es más simple y simétrico que el procedimiento de Oskui, pero no es discreto, ya que se basa en un procedimiento de cuchilla móvil. Su idea clave es dividir las tareas en seis partes y luego darle a cada socio las dos que sientan que son 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 sin envidia y asigne cada parte al jugador que la encuentre más grande.
Segundo paso.
- Usando el procedimiento de la cuchilla móvil de Austin , divida la pieza 1 en dos rebanadas que los socios 1 y 2 consideren iguales. Deje que el compañero 3 elija la rebanada que es más pequeña a sus ojos y dé la otra rebanada al compañero 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 el trozo más pequeño y entregue el otro trozo 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 dé la otra porción al socio 1.
Análisis. El socio 1 tiene dos rebanadas: una de la pieza 2 y otra de la pieza 3. A los ojos del socio 1, la rebanada de la pieza 2 es más pequeña que la rebanada dada al socio 3, y la rebanada de la pieza 3 es más pequeña que la rebanada dada al compañero 2. Además, estas dos rebanadas son más pequeñas que las rebanadas de la pieza 1, ya que la pieza 1 es más grande que la pieza 2 y la pieza 3 (según el Paso Uno). Por lo tanto, el socio 1 cree que su participación es débilmente) menor que cada una de las otras dos acciones. Las mismas consideraciones se aplican a los socios 2 y 3. Por lo tanto, la división no tiene envidia.
Peterson y Su extienden su procedimiento continuo a cuatro socios. [3]
El procedimiento discreto de Peterson y Su para cualquier número de socios
La existencia de un procedimiento discreto para cinco o más socios siguió siendo 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 reserva .
Procedimiento discreto y limitado de Dehghani et al. Para cualquier número de socios
Peterson y Su dieron un procedimiento de cuchillo en movimiento para la división de tareas de 4 personas. Dehghani y col. [5] proporcionó el primer protocolo libre de envidia discreto y limitado para la división de tareas entre cualquier número de agentes.
Procedimientos para piezas conectadas
Los siguientes procedimientos se pueden adaptar para dividir un pastel en mal estado con trozos desconectados:
- Procedimiento de cuchilla giratoria 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 pasteles aproximadamente sin envidia con piezas conectadas, basado en el lema de Sperner . Su demostró, usando un lema dual, que se puede usar un protocolo similar para una división de tareas sin envidia aproximada. En particular, muestra que siempre existe una división de tareas sin envidia con piezas conectadas.
Precio de equidad
Heydrich y van Stee [6] calculan el precio de la equidad en la división de tareas cuando las piezas deben estar conectadas.
Aplicaciones
Puede ser posible utilizar procedimientos de división de tareas para dividir el trabajo y el costo de reducir el cambio climático entre las naciones. Ocurren problemas con la moral y la cooperación entre 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 de la división de tareas domésticas sería el problema de la armonía del alquiler .
Referencias
- ^ Gardner, Martin (1978). ¡Ajá! Insight . Nueva York: WF Freeman and Co. ISBN 978-0-7167-1017-2.
- ^ a b c d Robertson, Jack; Webb, William (1998). Algoritmos para cortar pasteles: sea justo si puede . Natick, Massachusetts: AK Peters. ISBN 978-1-56881-076-8. LCCN 97041258 . OL 2730675W .
- ^ a b Peterson, Eliseo; Su, Francis Edward (1 de abril de 2002). "División de tareas sin envidia de cuatro personas". Revista de Matemáticas . 75 (2): 117-122. CiteSeerX 10.1.1.16.8992 . doi : 10.2307 / 3219145 . JSTOR 3219145 .
- ^ Peterson, Eliseo; Francis Edward Su (2009). "División de tareas sin envidia de N-personas". arXiv : 0909.0303 [ math.CO ].
- ^ Dehghani, Sina; Alireza Farhadi; MohammadTaghi Hajiaghayi; Hadi Yami (2018). División de tareas sin envidia para un número arbitrario de agentes . Actas del vigésimo noveno simposio anual ACM-SIAM sobre algoritmos discretos. págs. 2564-2583. doi : 10.1137 / 1.9781611975031.164 .
- ^ Heydrich, Sandy; Van Stee, Rob (2015). "Dividir equitativamente las tareas relacionadas" . Informática Teórica . 593 : 51–61. doi : 10.1016 / j.tcs.2015.05.041 . hdl : 2381/37387 .
- ^ Traxler, Martino (1 de enero de 2002). "División de tareas justas para el cambio climático". Teoría y práctica social . 28 (1): 101-134. doi : 10.5840 / soctheorpract20022814 . JSTOR 23559205 .
Ver también
- Corte de pastel sin envidia
- Malo (economía)
- Armonía de alquiler