Divisor solitario

El método del divisor único es un procedimiento para cortar un pastel de forma proporcional . Implica un recurso heterogéneo y divisible, como un pastel de cumpleaños, y n personas con diferentes preferencias sobre distintas partes del pastel. Permite que las n personas dividan el pastel entre ellas de manera que cada una reciba una porción cuyo valor sea al menos 1/ n del valor total, según su propia valoración subjetiva.

El procedimiento fue desarrollado por Hugo Steinhaus para n = 3 personas. ^{[ 1 ]} Posteriormente, Harold W. Kuhn lo extendió a n > 3, utilizando el teorema de Frobenius-König . ^{[ 2 ]} Una descripción de los casos n = 3 y n = 4 aparece en ^{[ 3 ]}^{: 31–35} y el caso general se describe en ^{[ 4 ]}^{: 83–87}

Descripción

Para mayor comodidad, normalizamos las valoraciones de manera que el valor del pastel completo sea n para todos los agentes. El objetivo es que cada agente reciba una porción con un valor de al menos 1.

Paso 1. Un jugador elegido arbitrariamente, llamado el divisor , corta el pastel en n trozos cuyo valor en su opinión es exactamente 1.

Paso 2. Cada uno de los otros n − 1 socios evalúa las n piezas resultantes y dice cuál de estas piezas considera "aceptable", es decir, que vale al menos 1.

Ahora el juego continúa según las respuestas de los jugadores en el paso 3. Presentamos primero el caso n = 3 y luego el caso general.

Procedimiento de Steinhaus para el caso n = 3

Hay dos casos.

Caso A: Al menos uno de los jugadores que no dividen marca dos o más piezas como aceptables. Luego, el tercer compañero elige una pieza aceptable (por el principio del palomar debe tener al menos una); el segundo compañero elige una pieza aceptable (tenía al menos dos antes, así que le queda al menos una); y finalmente, el que divide elige la última pieza (para el que divide, todas las piezas son aceptables).
Caso B: Los otros dos socios marcan solo una pieza como aceptable. Entonces, hay al menos una pieza que es aceptable solo para el divisor. El divisor toma esta pieza y se va a casa. Esta pieza vale menos de 1 para los dos socios restantes, por lo que las dos piezas restantes valen al menos 2 para ellos. La dividen entre ellos usando el método de dividir y elegir .

El procedimiento para cualquier n

Hay varias maneras de describir el caso general; la descripción más corta aparece en ^{[ 5 ]} y se basa en el concepto de emparejamiento sin envidia , un emparejamiento en el que ningún agente no emparejado está adyacente a una pieza emparejada.

Paso 3. Construya un grafo bipartito G = ( X + Y , E ) en el que cada vértice en X es un agente, cada vértice en Y es una pieza, y hay una arista entre un agente x y una pieza y si y solo si x tiene valores y al menos 1.

Paso 4. Hallar un emparejamiento libre de envidia de cardinalidad máxima en G. Nótese que el divisor es adyacente a todas las n piezas, por lo que | N _G ( X )| = n ≥ | X | (donde N _G ( X ) es el conjunto de vecinos de X en Y ). Por lo tanto, existe un emparejamiento libre de envidia no vacío.

Paso 5. Entregue cada pieza emparejada a su agente correspondiente. Tenga en cuenta que cada agente emparejado tiene un valor de al menos 1 y, por lo tanto, regresa a casa satisfecho.

Paso 6. Divide recursivamente el pastel restante entre los agentes restantes. Observa que cada agente restante valora cada trozo entregado en menos de 1, por lo que valora el pastel restante en más de un número de agentes, cumpliendo así la condición previa para la recursión.

Complejidad de la consulta

En cada iteración, el algoritmo solicita al único divisor un máximo de n consultas de marca , y a cada uno de los demás agentes un máximo de n consultas de evaluación . Hay como máximo n iteraciones. Por lo tanto, el número total de consultas en el modelo de consulta ^deRobertson-Webb es O( n² ) por agente y O( n³ ) en total. Esto es mucho más de lo requerido para ^elúltimo disminuidor (O( n ) por agente) y para Even-Paz (O(log n ) por agente).

Véase también

Para otros procedimientos para resolver el mismo problema, consulte el método de corte proporcional de pasteles .
Una ventaja del divisor único es que se puede modificar para obtener un procedimiento de corte de pastel simétrico y equitativo .
División justa: Método del divisor solitario en Cut-the-Knot .

Referencias

↑ Steinhaus, Hugo (1948). "El problema de la división justa". Econometrica . 16 (1): 101– 4. JSTOR 1914289 .
↑ Kuhn, Harold (1967), "Sobre juegos de división justa" , Ensayos de economía matemática en honor a Oskar Morgenstern , Princeton University Press, págs. 29-37 , archivado del original el 16 de enero de 2019 , consultado el 15 de enero de 2019.
↑ Brams, Steven J.; Taylor, Alan D. (1996). División justa: del reparto de pasteles a la resolución de disputas . Cambridge University Press. ISBN 0-521-55644-9.
↑ Robertson, Jack; Webb, William (1998). Algoritmos para el reparto de pasteles: Sea justo si puede . Natick, Massachusetts: AK Peters. ISBN 978-1-56881-076-8. LCCN 97041258 . OL 2730675W .
↑ Segal-Halevi, Erel; Aigner-Horev, Elad (2022). "Emparejamientos libres de envidia en grafos bipartitos y sus aplicaciones a la división justa". Information Sciences . 587 : 164–187 . arXiv : 1901.09527 . doi : 10.1016/j.ins.2021.11.059 . S2CID 170079201 .

[steinhaus48-1] Steinhaus, Hugo (1948). "El problema de la división justa". Econometrica . 16 (1): 101– 4. JSTOR 1914289 .

[2] Kuhn, Harold (1967), "Sobre juegos de división justa" , Ensayos de economía matemática en honor a Oskar Morgenstern , Princeton University Press, págs. 29-37 , archivado del original el 16 de enero de 2019 , consultado el 15 de enero de 2019.

[bt96-3] Brams, Steven J.; Taylor, Alan D. (1996). División justa: del reparto de pasteles a la resolución de disputas . Cambridge University Press. ISBN 0-521-55644-9.

[4] Robertson, Jack; Webb, William (1998). Algoritmos para el reparto de pasteles: Sea justo si puede . Natick, Massachusetts: AK Peters. ISBN 978-1-56881-076-8. LCCN 97041258 . OL 2730675W .

[5] Segal-Halevi, Erel; Aigner-Horev, Elad (2022). "Emparejamientos libres de envidia en grafos bipartitos y sus aplicaciones a la división justa". Information Sciences . 587 : 164–187 . arXiv : 1901.09527 . doi : 10.1016/j.ins.2021.11.059 . S2CID 170079201 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]