Fair Cake cortando cuando los jugadores se unen tarde

Question

La declaración habitual del Problema de corte de pastel de feria Asume que todos los jugadores de $ N $ obtienen su acción al mismo tiempo. Sin embargo, en muchos casos los jugadores llegan de forma incremental. Por ejemplo, podemos dividir un pastel de más de $ N $ jugadores, pero luego llega un nuevo jugador y quiere una acción.

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

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

Answer 1

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

Fondo. Permítanme indicar claramente el modelo para la reducción de pastel. Deseamos dividir el intervalo $ [0,1] $ entre $ N $ jugadores. Cada jugador $ i $ tiene una función de valoración $ v_i (s) $ sobre subconjuntos $ s $ del pastel. Asumiremos que esta función es una medida de probabilidad; No es negativo y aditivo (para disjunto $ a, b subseteq [0,1] $, $ v_i (a cup b) = v_i (a) + v_i (b) $) y $ v_i ([0,1] ) = 1 $. Una solución a este problema es un protocolo o algoritmo que consulta a los jugadores y asigna partes del intervalo. Tenga en cuenta que los jugadores pueden informar mal/mentir en responder consultas.

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

Deje que las piezas asignadas a los reproductores sean $ {S_1, DOTS, S_N } $. A menudo queremos las siguientes propiedades de un protocolo:

• proporcionalidad: Cada jugador $ i $ tiene una estrategia que garantiza que reciba un valor de al menos $ (1/n) v_i ([0,1]) $. (Desde la perspectiva de $ I $, obtiene $ 1/n $ del valor total del pastel).
• envidia de la envidia: Cada jugador tiene una estrategia que garantiza que $ v_i (s_i) geq v_i (s_j) $ por cualquier otro jugador $ j $. (Cada jugador prefiere su propia pieza a la pieza de cualquier otro jugador).

Tenga en cuenta que la envidia de envidia implica proporcionalidad.

También hay propiedades "operativas" que podríamos querer, como cortar en pocas piezas, tiempo de ejecución polinomial (o de hecho computabilidad/construcción en absoluto: ¡no queremos usar el axioma de elección para seleccionar un subconjunto de la torta! ), y así.

---

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

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

1. Supongamos que tenemos una asignación sin envidia para $ N $ jugadores. ¿Cómo redistribuimos para producir una asignación sin envidia entre los jugadores $ N+1 $?

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

1. Supongamos que tenemos una asignación proporcional por $ N $; ¿Cómo redistribuimos para obtener una asignación proporcional por $ n+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 una porción de $ 1/n $. Entonces, lo que sea que haga el nuevo jugador requerirá reorganizar entre todos. Aquí hay otro caso malo: suponga que el jugador $ 1 $ tiene una valoración de exactamente $ 1/n $ por su porta, pero valora el reproductor de jugador $ 2 $ 's Slice a $ (N-1)/n $. Supongamos que el jugador $ 2 $ valora su propia porción a exactamente $ 1/n $, pero valora el porta de jugador $ 3 $ 's Slice a $ (N-1)/n $, y así sucesivamente, con el jugador $ n $ valora su propia porta a $ 1/ N $ y el jugador $ 1 $ 'S Slice a $ (N-1)/N $. Ahora llega el nuevo jugador. No importa lo que el nuevo jugador quiera, su protocolo terminará teniendo que remodelar algo del jugador $ 2 $ al jugador $ 1 $, del jugador $ 3 $ al jugador $ 2 $, etc.

---

Una referencia podría ser Walsh, Corte de pastel en línea, en la teoría de la decisión algorítmica 2011 (enlace PDF). Pero creo que el documento supone que sabemos de antemano el número de agentes que llegan, y asume que los jugadores deben asignarse una pieza con precisión cuando se van (que es antes del final del protocolo), por lo que realmente no es 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 de $ N $ presentes reduzca su pieza de pastel asignado en $ n+1 $ piezas que él mismo valora igualmente. El jugador $ N+1 $ ahora elegirá la mejor pieza, según él, de cada uno de los recortes de $ N $ jugador. Es fácil demostrar que la asignación resultante también es proporcional.

Answer 2

Suponga que el pastel/área es un círculo $ C $ con Radius $ r $. Luego, podemos crear $ n $ piezas justas mediante el corte de pastel canónico y, por lo tanto, asignar a cada jugador un área de $ frac { pi r^2} {n} $. Luego podemos asignar el $ (n+1) $ th un pequeño círculo alrededor del centro, y los nuevos jugadores posteriores suena alrededor de eso (parte de la parte del círculo interior), y así sucesivamente. De esta manera, cada jugador obtiene una pieza/trama contigua que se reduce de manera monótona para los primeros jugadores de $ N+1 $, y se mueve hacia el centro para quienes se unen más tarde.

Resolver los números es simple; Para el primer jugador nuevo, simplemente resuelva

$ qquad pi r_1^2 = frac { pi r^2} {n+1} $

Para obtener el radio de su trama. Para el segundo, resolver

$ qquad begin {align} pi r_1^2 & = frac { pi r^2} {n+2} pi r_2^2 - pi r_1^2 & = frac { pi r ^2} {n+2} end {align} $

para obtener radios (externos) para ambos jugadores nuevos, y así sucesivamente. Parece que el reproductor $ n + i $ obtiene radio exterior $ r_i = frac {r sqrt {i}} { sqrt {n + k}} $ después de que $ k $ se hayan unido jugadores adicionales, pero no probé esto .

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

^[fuente]

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