Corte de pastel justo cuando los jugadores se unen tarde

11

La afirmación habitual del problema de la tarta justa supone que todos los jugadores obtienen su parte al mismo tiempo. Sin embargo, en muchos casos los jugadores llegan de forma incremental. Por ejemplo, podemos dividir un pastel entre jugadores, pero luego llega un nuevo jugador y quiere compartir.nnn

Por lo general, la división de pastel justo requiere mucho esfuerzo (por ejemplo, requiere que los jugadores respondan muchas preguntas), especialmente cuando el número de jugadores es grande.

¿Es posible usar la división existente del pastel sobre jugadores, para crear una nueva división del pastel para jugadores, con un esfuerzo adicional mínimo (es decir, un esfuerzo sustancialmente menor que redistribuir el pastel desde cero)?n + 1nn+1

Erel Segal-Halevi
fuente
2
¿Han comenzado a comer los primeros jugadores? ¿Es justo darle a un jugador múltiples piezas, o todos tienen que obtener exactamente una pieza? n
Raphael
@Raphael, estoy específicamente interesado en una división equitativa de la tierra, por lo tanto, los jugadores no pueden literalmente comenzar a comer su parte (pueden aprovechar su parte, pero ignoremos este problema por el momento). Es preferible dar a cada jugador exactamente una pieza, sin embargo, esto aparentemente no es posible de manera justa en caso de que llegue una sola persona nueva. Probablemente debería preguntar qué pasa si llegan nuevos jugadores. En ese caso, es posible (al menos en teoría) dividir cada parte de los primeros jugadores en 2 nuevas partes. En cualquier caso, cualquier referencia es bienvenida. nn
Erel Segal-Halevi
En caso de tierra no utilizada, ¿por qué no redistribuir todo?
Raphael
2
Creo que tienes que aclarar cuál es tu objetivo. ¿Minimizar el número de cortes de actualización? ¿Minimizar la longitud total de nuevos cortes? ¿Podemos reasignar partes a jugadores antiguos, o el único puede perder?
Raphael
Ah, ahora entiendo lo que quieres decir: quieres decir que algunos de los jugadores comenzaron a comer su parte, y ahora llegan nuevos jugadores, y queremos dividir los recordatorios de manera justa, teniendo en cuenta lo que cada jugador ya ha comido. Si bien este es un problema interesante en sí mismo, mi intención era diferente; espero que mi edición reciente lo aclare.
Erel Segal-Halevi

Respuestas:

6

Diré por adelantado que no puedo proporcionar una buena respuesta a su pregunta (creo que tal vez podría obtener un documento de investigación si pudiera), pero creo que puedo ayudar definiendo el problema formalmente y estableciendo dónde de las dificultades mienten.

Antecedentes . Permítanme indicar claramente el modelo para cortar pasteles. Deseamos dividir el intervalo entre jugadores. Cada jugador tiene una función de valoración sobre los subconjuntos del pastel. Asumiremos que esta función es una medida de probabilidad; no es negativa y es aditiva (para disjuntos , ) y . Una solución a este problema es un protocolo o algoritmo que consulta a los jugadores y asigna porciones del intervalo. Tenga en cuenta que los jugadores pueden informar mal / mentir al responder consultas.n i v i ( S ) S A , B [ 0 , 1 ] v i ( A B ) = v i ( A ) + v i ( B ) v i ( [ 0 , 1 ] ) = 1[0,1]nivi(S)SA,B[0,1]vi(AB)=vi(A)+vi(B)vi([0,1])=1

Algunos documentos tendrán restricciones más específicas; por ejemplo , las funciones de valoración son continuas, o por partes-lineales, o por partes-constantes.

Deje que las piezas asignadas a los jugadores sean . A menudo queremos las siguientes propiedades de un protocolo:{S1,,Sn}

  • proporcionalidad : cada jugador tiene una estrategia que garantiza que recibe un valor de al menos . (Desde la perspectiva de , él / ella obtiene del valor total del pastel).( 1 / n ) v i ( [ 0 , 1 ] ) i 1 / ni(1/n)vi([0,1])i1/n
  • sin envidia : cada jugador tiene una estrategia que garantiza que para cada otro jugador . (Cada jugador prefiere su propia pieza a la de cualquier otro jugador).jvi(Si)vi(Sj)j

Tenga en cuenta que la ausencia de envidia implica proporcionalidad.

También hay propiedades "operativas" que podríamos desear, como cortar en pocas partes, tiempo de ejecución polinomial (o, de hecho, computabilidad / capacidad de construcción, ¡no queremos usar el Axioma de elección para seleccionar un subconjunto del pastel! ), y así.


Preguntas específicas para hacer . Dos notas Primero, cualquier respuesta a su pregunta resolverá el problema general: comience por darle todo el pastel al jugador , luego deje que los otros jugadores lleguen en línea y apliquen este protocolo de forma iterativa. Por lo tanto, debemos esperar que este problema sea más difícil que la configuración estándar de corte de torta a la que lo aplicamos.1

En segundo lugar, siempre podemos resolver su problema retirando todo el pastel de todos y utilizando un algoritmo conocido para redistribuirlo desde cero. Entonces la pregunta es si hay una forma algo más elegante de hacer esto. Creo que una buena manera de cuantificar esto es "¿cuándo la redistribución requiere menos tiempo o menos cortes que comenzar desde cero y / o cuándo los jugadores pueden mantener una porción significativa de su porción actual?"

  1. Supongamos que tenemos una asignación libre de envidia para jugadores. ¿Cómo redistribuimos para producir una asignación libre de envidia entre los jugadores?n + 1nn+1

Sospecho que esto es muy difícil. La razón es que encontrar una asignación eficiente y sin envidia ya es un problema difícil. Hasta donde yo sé, los protocolos conocidos podrían requerir un número ilimitado de cortes en el pastel y son muy complejos. (Ver Brams y Taylor, Un Protocolo de División de Tortas sin Envidia , 1995). Por lo tanto, puede que no haya nada mejor que quitarle todo el pastel a todos y redistribuirlo a los agentes usando Brams-Taylor.n+1

  1. Supongamos que tenemos una asignación proporcional para ; ¿Cómo redistribuimos para obtener una asignación proporcional para ?nn+1

Creo que esto sigue siendo difícil (aunque más factible). Considere el caso en el que cada jugador valora el pastel de manera uniforme y cada jugador tiene un corte de tamaño . Entonces, lo que sea que haga el nuevo jugador requerirá una reorganización entre todos. Aquí hay otro caso negativo: supongamos que el jugador tiene una valoración de exactamente para su porción, pero valora la porción del jugador en . Supongamos que el jugador valora su propia porción exactamente a , pero valora la porción del jugador a , y así sucesivamente, con el jugador valorando su propia porción a la porción del jugador a1/n11/n2(n1)/n21/n3(n1)/n1 / n 1 ( n - 1 ) / n 2 1 3 2n1/n1(n1)/n . Ahora llega el nuevo jugador. No importa lo que quiera el nuevo jugador, su protocolo terminará teniendo que reorganizar algo del jugador al jugador , del jugador al jugador , etc.2132


Una referencia podría ser Walsh, Online Cake Cutting , en Algorithmic Decision Theory 2011 (enlace pdf). Pero creo que el documento supone que sabemos de antemano el número de agentes que llegan, y supone que a los jugadores se les debe asignar una pieza precisamente cuando se van (que es antes del final del protocolo), por lo que realmente no es tan aplicable a su problema.


Una forma de redistribuir una asignación proporcional que mantiene la proporcionalidad es la siguiente. Deje que cada uno de los jugadores actuales corte su porción de pastel asignada en piezas que él mismo valora por igual. El jugador ahora elegirá la mejor pieza, según él, de cada uno de los cortes del jugador. Es fácil demostrar que la asignación resultante también es proporcional.n + 1 n + 1 nnn+1n+1n

usul
fuente
No estoy seguro de cómo el problema general (con preferencia no uniforme) es de ayuda aquí; whoops ? Resolver el problema para jugadores que no cambian (y formas razonables) es fácil. Supongo que tendremos que arreglar qué significa "eficiente" o "bueno" significa recortes / asignaciones de wrt y cambios de los mismos.
Raphael
1
@Raphael: por lo que puedo decir, la pregunta se refiere a la resolución del problema general. (Estoy de acuerdo en que deberíamos usar una estructura adicional si se especifica alguna).
usul
Gracias, su definición capturó con precisión mi intención. Y la referencia sobre el corte de pasteles en línea es interesante y relevante.
Erel Segal-Halevi
6

Suponga que el pastel / área es un círculo con radio . Luego, podemos crear piezas justas cortando el pastel canónico y así asignar a cada jugador un área de . Luego podemos asignar al th un pequeño círculo alrededor del centro, y los nuevos jugadores posteriores suenan alrededor de ese (tragando parte del círculo interno), y así sucesivamente. De esta manera, cada jugador obtiene una pieza / trama contigua que se reduce de forma monótona para los primeros jugadores, y se mueve hacia el centro para aquellos que se unen más tarde.r n π r 2Crn (n+1)n+1πr2n(n+1)n+1

Resolver los números es simple; para el primer jugador nuevo, simplemente resuelve

πr12=πr2n+1

para obtener el radio de su trama. Para el segundo, resuelve

πr12=πr2n+2πr22πr12=πr2n+2

para obtener radios (externos) para ambos jugadores nuevos, y así sucesivamente. Parece que el jugador obtiene el radio exterior después de que se hayan unido jugadores adicionales, pero no lo probé.r i = r n+i kri=rin+kk

Esto es lo que obtienes por y :k = 0 , 1 , 2 , 3n=6k=0,1,2,3

ejemplo [ fuente ]

La misma idea funciona para polígonos regulares con lados. Si asume un rectángulo como forma básica, puede hacer algo similar al asignar las primeras columnas de igual tamaño y las siguientes filas de jugadores (comenzando en un lado).nnn

Rafael
fuente
1
Sería interesante comparar el área que se reasigna mediante este método con el área que se reasigna insertando una nueva pieza (es decir, sector) de torta y moviendo (y reduciendo) todas las piezas existentes en el sentido de las agujas del reloj. El número de partes afectadas por un movimiento (no solo una pérdida) difiere solo por una constante. También tenga en cuenta que los anillos no son más efectivos que los sectores, pero el cambio de un método a otro permite no mover el área asignada por el primer método.
frafl
@frafl Estoy de acuerdo. ¿Puedes presentar las otras variantes en una respuesta? (Tienes razón: no parece haber una buena razón para mezclar los métodos. Para mí fue motivado por el problema del pastel: supongamos que el pastel ya está cortado, ¿qué hacer?)
Raphael
@frafl Tenga en cuenta que una ventaja del esquema que uso puede ser que las piezas de los primeros jugadores solo se reducen pero no se mueven. En otras palabras, este esquema hace menos cortes (completamente) obsoletos que la inserción de nuevos sectores. n+1
Rafael
1
Esta es una hermosa solución gemoétrica, sin embargo, es relevante solo para pasteles uniformes y prereferencias uniformes. Me referí al problema general de cortar el pastel: en.wikipedia.org/wiki/Fair_division, que supone que el pastel puede no ser uniforme, y que diferentes jugadores pueden tener valoraciones diferentes para diferentes partes del pastel.
Erel Segal-Halevi