Procedimiento de Selfridge-Conway

El procedimiento de Selfridge-Conway es un procedimiento discreto que ofrece un corte de torta sin envidia para tres participantes [1] . El procedimiento lleva el nombre de John Selfridge y John Conway . Selfridge descubrió el procedimiento en 1960 y se lo informó a Richard Guy , quien se lo contó a mucha gente, pero el propio Selfridge no publicó oficialmente su descubrimiento. John Conway descubrió más tarde el procedimiento de forma independiente y tampoco lo publicó [2] . Este fue el primer procedimiento discreto de corte de torta libre de envidia para tres participantes, y allanó el camino para procedimientos más avanzados para n participantes (ver corte de torta envidioso ).

El procedimiento da un resultado sin envidia en el caso de que cada participante en el proceso crea que ningún otro participante (según su valoración subjetiva) recibirá más que él. En este procedimiento, el número máximo de cortes es cinco. Las partes del pastel entregadas a los participantes no siempre serán continuas (pueden consistir en varias partes separadas).

Procedimiento

Supongamos que tenemos tres participantes, , y . Cuando un procedimiento proporciona un criterio para una decisión, ese criterio es óptimo para el jugador. ${\ estilo de visualización P1}$ ${\ estilo de visualización P2}$ ${\ estilo de visualización P3}$

${\ estilo de visualización P1}$ divide el pastel en tres partes, que considera iguales.
Que sea la pieza más grande, según . $A$ ${\ estilo de visualización P2}$
${\ estilo de visualización P2}$ corta una pieza para que sea igual a la segunda pieza más grande. Ahora divida en y corte la pieza . Dejándolo a un lado por ahora. $A$ $A$ $A1$ ${\ estilo de visualización A2}$ ${\ estilo de visualización A2}$
- Si considera que las dos piezas más grandes son iguales (por lo que no es necesario cortar), entonces cada jugador elige su pieza en el siguiente orden: , y finalmente . ${\ estilo de visualización P2}$ ${\ estilo de visualización P3}$ ${\ estilo de visualización P2}$ ${\ estilo de visualización P1}$
${\ estilo de visualización P3}$ elige una pieza entre y las dos piezas restantes. $A1$
${\ estilo de visualización P2}$ selecciona una pieza con una restricción, si no selecciona , debe tomarla. ${\ estilo de visualización P3}$ $A1$ ${\ estilo de visualización P2}$
${\ estilo de visualización P1}$ toma la pieza restante, dejando la pieza para una mayor división. ${\ estilo de visualización A2}$

Queda por dividir la pieza . La pieza fue elegida por el jugador o el jugador . Designemos al jugador que tomó esta pieza como , y asignemos el nombre al segundo jugador . ${\ estilo de visualización A2}$ $A1$ ${\ estilo de visualización P2}$ ${\ estilo de visualización P3}$ $Pensilvania$ $PB$

$Pensilvania$ o (pero necesariamente ) corta en tres partes iguales (en su opinión). $PB$ ${\ estilo de visualización P3}$ ${\ estilo de visualización A2}$
${\ estilo de visualización P1}$ quita parte de la pieza , déjala ser . ${\ estilo de visualización A2}$ ${\ estilo de visualización A22}$
${\ estilo de visualización P2}$ (déjalo ser ) quita parte de la pieza , a saber . $Pensilvania$ ${\ estilo de visualización A2}$ ${\ estilo de visualización A21}$
${\ estilo de visualización P3}$ (en nuestro caso es ) toma el resto de la pieza , lo denotaremos como . $PB$ ${\ estilo de visualización A2}$ ${\ estilo de visualización A23}$

Análisis

Veamos por qué tal división no contendrá la envidia. Debe demostrarse que la parte resultante de cada jugador no es menor (en su opinión) que las partes de los otros jugadores. Sin pérdida de generalidad, podemos escribir (ver la ilustración de arriba):

$Pensilvania$ recibido _ ${\ estilo de visualización A1 + A21}$
$PB$ recibido _ ${\ estilo de visualización B + A23}$
${\ estilo de visualización P1}$ recibido _ ${\ estilo de visualización C + A22}$

En el siguiente análisis, "más grande" significa "más grande según la puntuación del jugador":

$Pensilvania$ recibido _ para el y Y cree que eligió como la mayor parte de la pieza . Así que ningún otro jugador consiguió más que él: . ${\ estilo de visualización A1 + A21}$ ${\ estilo de visualización A1 \ geqslant B}$ $A1\geqslant C$ ${\ estilo de visualización A21}$ ${\ estilo de visualización A2}$ ${\ estilo de visualización A1 + A21 \ geqslant B + A23, C + A22}$
$PB$ recibido _ Por él y porque él eligió . También cortó la pieza en 3 piezas, por lo que para él todas estas piezas son iguales. ${\ estilo de visualización B + A23}$ $B\geqslant A1$ $B\geqslant C$ $B$ ${\ estilo de visualización A2}$
${\ estilo de visualización P1}$ recibido _ No puede comparar las piezas de la misma manera que o , ya que las piezas y ya han sido seleccionadas, y obtuvo la última pieza , pero: ${\ estilo de visualización C + A22}$ $Pensilvania$ $PB$ $A$ $B$ $C$
- ${\ estilo de visualización P1}$ cree que no recibió más de lo que recibió. En otras palabras, . Recordemos que eligió su parte antes , así que desde su punto de vista. $PB$ $C+A22\geqslant B+A23$ ${\ estilo de visualización P1}$ ${\ estilo de visualización A2}$ $PB$ $A22\geqslant A23$
- ${\ estilo de visualización P1}$ cree que ya no lo entendió. En otras palabras, . Recordemos que eligió su parte antes , así que desde su punto de vista. $Pensilvania$ $C+A22\geqslant A1+A21$ ${\ estilo de visualización P1}$ ${\ estilo de visualización A2}$ $Pensilvania$ $A22\geqslant A21$
- ${\ estilo de visualización P1}$ piensa eso y no obtuvo más que él, ya que la pieza es igual y también igual , ya que cortó el pastel desde el principio. Entonces, . Incluso si cualquiera tomó la pieza completa y no la recibió , después de todo , no tendrá envidia ). $Pensilvania$ $PB$ $C$ $A$ $B$ ${\ estilo de visualización A = A1 + A2 = A1 + (A21 + A22 + A23) = B = C}$ $Pensilvania$ $PB$ ${\ estilo de visualización A2}$ ${\ estilo de visualización P1}$ ${\ estilo de visualización A22}$ ${\ estilo de visualización P1}$ ${\ estilo de visualización A = B = C}$

Generalizaciones

Tenga en cuenta que si todo lo que queremos es un corte justo sin envidia por un trozo de pastel (es decir, permitimos descartar un trozo de pastel), entonces solo necesitamos usar la primera parte del procedimiento, es decir:

${\ estilo de visualización P1}$ divide el pastel en tres partes idénticas (en su opinión);
${\ estilo de visualización P2}$ corta como máximo una pieza para obtener al menos dos piezas idénticas (en su opinión).
${\ estilo de visualización P3}$ toma una pieza, luego , luego . ${\ estilo de visualización P2}$ ${\ estilo de visualización P1}$

Este procedimiento se puede generalizar a 4 participantes de la siguiente manera [3] :

${\ estilo de visualización P1}$ divide el pastel en 5 partes, idénticas, en su opinión;
${\ estilo de visualización P2}$ corta no más de 2 piezas, por lo que ahora hay 3 tres piezas idénticas, en su opinión;
${\ estilo de visualización P3}$ corta como máximo 1 pieza, por lo que ahora hay 2 piezas que son iguales para él;
${\ estilo de visualización P4}$ toma una pieza, luego , luego , luego . ${\ estilo de visualización P3}$ ${\ estilo de visualización P2}$ ${\ estilo de visualización P1}$

Por inducción, el procedimiento se puede generalizar a n participantes, el primero de los cuales divide la torta en partes, cada una de las cuales es igual a la torta, y los demás participantes siguen el procedimiento de corte. El corte resultante está libre de envidias, y cada socio recibe un valor al menos igual al de la torta entera. ${\ estilo de visualización 2^{n-2}+1}$ $1/2^{{n-1}}$

Podemos aplicar el mismo procedimiento para los residuos. Haciendo esto un número infinito de veces, obtenemos una partición sin envidia de todo el pastel [4] . Una mejora de este procedimiento infinito conduce a un procedimiento de partición finito libre de envidias, el procedimiento de Brahms-Taylor .

Notas

↑ Robertson, Webb, 1998 , pág. 13-14.
↑ Brams y Taylor 1996 , pág. 116-120.
↑ Brams y Taylor 1996 , pág. 131-137.
↑ Brams y Taylor 1996 , pág. 137.

Literatura

Jack Robertson, William Webb. Algoritmos de corte de torta: Sea justo si puede .. - CRC Press, 1998. - ISBN 978-1-56881-076-8 .
Steven J. Brams, Alan D. Taylor. División justa: desde el corte del pastel hasta la resolución de disputas . - Prensa de la Universidad de Cambridge, 1996. - ISBN 0521556449 .