Comparte y elige

Delhi y elige (o corta y elige , así como yo corto, tú eliges ) es un procedimiento para cortar el pastel entre dos participantes, como resultado de lo cual no hay envidia . El problema asume bienes o recursos heterogéneos ("pastel") y dos participantes con diferentes preferencias por partes separadas del pastel. El protocolo funciona de la siguiente manera: uno de los participantes ("cortar") corta el pastel en dos partes, el segundo participante ("elegir") elige una de las partes y el cortador se queda con la parte restante.

Historia

El método divide y elige se menciona en la Biblia en el Libro de Génesis . Cuando Abraham y Lot llegaron a la tierra de Canaán , Abraham se ofreció a repartirla entre ellos. Entonces Abraham, que vino del sur, dividió la tierra en partes "izquierda" (occidental) y "derecha" (oriental) e invitó a Lot a elegir. Lot eligió la parte oriental, que incluía a Sodoma y Gomorra , mientras que Abraham obtuvo la parte occidental, que contenía Beerseba , Hebrón , Beit El y Siquem .

Análisis

El método divide y elige produce una partición libre de envidia en el siguiente sentido: cada uno de los dos participantes puede actuar de tal manera que, como resultado de la división, su parte (en su opinión) no será menos valiosa que la parte del segundo participante, independientemente del comportamiento del segundo participante. Así es como pueden comportarse los miembros:

Para un observador externo, la división puede parecer injusta, pero no hay razón para que los participantes en la división se envidien entre sí.

Si las funciones de calificación de los participantes son aditivas , entonces la división de divide y elige también es proporcional en el siguiente sentido: cada participante puede actuar de tal manera que se le garantice obtener una pieza con un valor de al menos 1/2 de la calificación total de la torta. Esto es consecuencia del hecho de que en el caso de estimaciones aditivas, cualquier corte libre de envidia también es proporcional.

El protocolo funciona de la misma manera para compartir un recurso deseado (como cortar el pastel ) que para compartir un recurso no deseado (como compartir deberes ).

El protocolo de divide y elige asume las mismas partes debidas y la decisión de dividirse entre ellos o utilizar la mediación , pero no un árbitro . Se supone que el bien es divisible de cualquier manera, pero los jugadores pueden valorar las partes de manera diferente.

Tiene sentido que el cortador divida el recurso de la manera más justa posible, de lo contrario, es posible que obtenga una parte no deseada. Esta regla es una aplicación específica del concepto de la cortina de la ignorancia .

El método divide y elige no garantiza que cada participante recibirá exactamente la mitad del pastel según su propia estimación, por lo que la división no es exacta . No existe un procedimiento finito para la división exacta, pero se puede hacer con dos cuchillas en movimiento . Consulte el artículo Procedimiento de cuchillo móvil de Austin .

Problemas de eficiencia

Delhi-and-choose puede dar un corte ineficiente.

Un ejemplo de uso común es el pastel , que es mitad vainilla y mitad chocolate . Supongamos que a Bob solo le gusta el chocolate y a Carol solo le gusta la vainilla. Si Bob es el cortador y no conoce las preferencias de Carol, su estrategia más segura es cortar el pastel de modo que cada pieza contenga la misma cantidad de chocolate. Pero luego, independientemente de la elección de Carol, Bob obtiene solo la mitad del chocolate, y está claro que cortar no es eficiente en el sentido de Pareto . Es muy posible que Bob, sin saberlo, separe toda la vainilla (y un poco de chocolate) en una porción grande, de modo que Carol obtenga todo lo que quería, mientras que Bob obtiene menos de lo que podría obtener después de una discusión conjunta.

Alternativas

Si Bob conoce las preferencias de Carol y le gusta, puede cortar el pastel en chocolate y vainilla, de modo que Carol elija la vainilla y Bob se quede todo el chocolate. Por otro lado, si no le gusta Carol, puede cortar el pastel en un poco más de la mitad de la porción de vainilla en una pieza, y el resto de la porción de vainilla y la porción de chocolate en otra pieza. Carol también puede tomar una pieza con un trozo de chocolate para fastidiar Bob. Existe un procedimiento para resolver incluso tales problemas, pero es muy inestable con pequeños errores en las estimaciones [1] . Existen soluciones más prácticas que garantizan la optimización, pero son mucho mejores que el método de dividir y elegir desarrollado por Stephen Brahms y Alan Taylor, en particular el procedimiento de " ajuste ganador " [2] [3] .

En 2006, Stephen J. Brahms, Michael A. Jones y Christian Klamer explicaron en detalle una nueva forma de cortar el pastel, denominada procedimiento excedente ( procedimiento excedente , SP), que satisface la condición de imparcialidad y, por lo tanto, resuelve lo anterior. problema [4] . Las valoraciones subjetivas de los jugadores sobre las piezas que les han sido asignadas en relación con la tarta entera son las mismas.  

Compartir entre más de dos participantes

Martin Gardner popularizó el desafío de desarrollar un procedimiento de división justa similar para grupos grandes en su columna de mayo de 1959 "Juegos matemáticos" en Scientific American [5] . Uno de los procedimientos comienza con el hecho de que uno de los participantes corta el pastel de acuerdo a su comprensión de una división justa. Cualquier otra persona puede cortar una parte de una pieza para hacerla más pequeña. El último en reducir una pieza está obligado a tomarla.

Aziz y McKenzie [7] propusieron un nuevo método en Scientific American [6 ] . Aunque en principio es más rápido que los métodos anteriores, sigue siendo potencialmente muy lento: , donde n es el número de fragmentos deseados.

Véase también

Notas

  1. ↑ Cake Cutting with Full Knowledge Archivado el 9 de febrero de 2020 en Wayback Machine David McQuillan 1999 (sin revisar)
  2. ↑ Brams, Taylor, 1996 .
  3. ↑ Brams, Taylor, 1999 .
  4. ↑ Brams, Jones, Klamler, 2006 , pág. 1313-1321.
  5. ↑ Garner, 1994 .
  6. ↑ Klarreich, 2016 .
  7. ↑ Aziz, Mackenzie, 2017 .

Literatura