Compartir pastel

El problema de compartir un pastel es un problema de la teoría de la elección social , en el que un grupo de agentes con diferentes preferencias debe elegir conjuntamente un subconjunto de un recurso heterogéneo y divisible, como el tiempo o el espacio. Tienen un presupuesto fijo que determina el tamaño máximo del subconjunto que pueden elegir. Aquí hay dos ejemplos.

1. Compartir tiempo : un grupo de personas quiere organizar una fiesta de dos horas el domingo. Cada persona tiene preferencias diferentes sobre el horario (por ejemplo, Alice está disponible de 8:00 a 12:00 y de 16:00 a 20:00, George de 10:00 a 17:00, etc.). Deben elegir un período de dos horas del total de 24 horas disponibles.
2. Espacio compartido : Un grupo de personas desea construir un nuevo asentamiento de un tamaño fijo. Cada persona tiene preferencias diferentes respecto a la ubicación. Deben elegir un subconjunto del tamaño especificado, dentro de la región total disponible.

El problema fue presentado por Bei, Lu y Suksompong en 2022-2025. ^{[ 1 ] [ 2 ]}

Existe un recurso llamado pastel , modelado por un intervalo [0, c ], para algún c > 0. Hay un conjunto de agentes numerados del 1 al n . Cada agente i tiene una función de densidad de valor v _i sobre el pastel. El valor de i para una porción de pastel W , denotado V _i ( W ), es la integral de v _i sobre W (en otras palabras, V _i es una medida no atómica sobre el pastel).

Existe un "presupuesto" fijo b < c . Los agentes deben elegir colectivamente un subconjunto de [0, c ], con una longitud total de como máximo b . Si se elige el subconjunto W , entonces cada agente i disfruta de una utilidad de V _i ( W ); esto formaliza el hecho de que W , una vez elegido, es un bien público.

En una variante denominada configuración excluyente , es posible excluir a algunos agentes de disfrutar de ciertas partes del subconjunto elegido. Es decir, además de elegir W , a cada agente i se le asigna un subconjunto W _i de W y disfruta de una utilidad de V _i ( W _i ); los W _i no tienen por qué ser disjuntos.

En un modelo más general, ^{[ 2 ] : Apéndice} A cada parte del pastel puede tener un costo diferente. Formalmente, existe una función de densidad de costos sobre el pastel, y el costo de cada trozo de pastel es la integral de la función de densidad de costos sobre ese pastel. El objetivo es seleccionar un trozo de pastel con un costo total de como máximo b (en el modelo simple, el costo de cada trozo de pastel es igual a su longitud).

Bei, Lu y Suksompong ^{[ 2 ]} suponen que los agentes tienen valoraciones uniformes por partes . Esto significa que la densidad de valor de cada agente en cada punto es 0 o 1. De forma equivalente, el agente iLas preferencias del agente están representadas por un subconjunto A _i del pastel que el agente aprueba . La utilidad que el agente i obtiene de un subconjunto W es la longitud de la intersección de A _i con W. Estudian dos reglas de selección.

El problema de compartir un pastel difiere de otros problemas de elección social estrechamente relacionados.

1. El problema de repartir un pastel es otro problema que involucra un recurso heterogéneo y divisible, como el tiempo o el espacio, y agentes con diferentes preferencias sobre dicho recurso. En el reparto del pastel, se asigna el recurso completo y cada agente recibe su propio trozo (es decir, cada trozo es un bien privado ); en el reparto del pastel, solo se asigna un subconjunto del recurso y todos los agentes lo disfrutan juntos (es decir, es un bien público ). También existe un escenario intermedio llamado división justa entre grupos , en el que un recurso debe asignarse entre grupos de agentes, donde cada trozo del recurso es un bien público entre los miembros del grupo, pero privado con respecto a los demás grupos.

2. La votación multiganador es otro problema en el que agentes con diferentes preferencias deben elegir juntos un subconjunto (un comité) que los represente a todos. Al igual que en el reparto de pasteles, el tamaño del subconjunto seleccionado (el número de miembros del comité) se fija de antemano. La diferencia radica en que, en la votación multiganador, los candidatos son discretos, mientras que en el reparto de pasteles el pastel es continuo; en efecto, existe un continuo de candidatos diferentes. El reparto de pasteles con valoraciones uniformes por partes es el análogo continuo de la votación de aprobación multiganador .

3. La votación de aprobación fraccionaria (también llamada mezcla justa ) es una variante de la votación de múltiples ganadores en la que se pueden elegir fracciones de candidatos (por ejemplo, si hay tres candidatos x, y, z, y el tamaño del comité es 2, entonces es posible elegir 1/3 de x, 2/3 de y y todos los z). Las fracciones pueden corresponder a los candidatos que sirven a tiempo parcial o que sirven con cierta probabilidad. Este problema se puede reducir a un reparto de pastel de la siguiente manera. ^{[ 3 ] : Sec.4} El pastel es el intervalo [0, m ], donde m es el número de candidatos. Cada candidato j corresponde al subintervalo [j-1,j]. Un agente de votación fraccionaria que aprueba un conjunto de candidatos se asigna a un agente de reparto de pastel que aprueba el conjunto correspondiente de subintervalos.

4. La agregación de propuestas presupuestarias es un problema en el que un presupuesto fijo debe asignarse entre varios asuntos. Cada agente propone una asignación presupuestaria diferente, y el objetivo es agregar todas las propuestas en una única asignación presupuestaria. Este problema (cuando las preferencias de los agentes se basan en la distancia L1) puede reducirse a un reparto de pastel de la siguiente manera. ^{[ 3 ] : Sec.4} El pastel es el intervalo [0, m ], donde m es el número de asuntos. Cada asunto j corresponde al subintervalo [ j -1, j ]. Un agente de agregación presupuestaria que quiere asignar x _j a cada agente j, se asigna a un agente de reparto de pastel que aprueba, de cada intervalo [ j -1, j ], el subintervalo [ j -1, j -1+ x _j ].

5. El problema del subconjunto aceptable es otro problema en el que agentes con diferentes preferencias deben elegir conjuntamente un subconjunto que les sea útil a todos. Sin embargo, el tamaño del subconjunto no está fijado de antemano; el requisito es que el subconjunto elegido sea, según todos los agentes, al menos tan bueno como el subconjunto restante (no elegido); y, en consecuencia, el subconjunto elegido debe ser lo más pequeño posible.

Lu, Peters, Aziz, Bei y Suksompong ^{[ 4 ]} extienden el reparto de pasteles a escenarios con candidatos mixtos divisibles e indivisibles: existe un conjunto de m candidatos indivisibles, así como un pastel [0, c ]. Su escenario extendido generaliza tanto el reparto de pasteles como la votación de múltiples ganadores.

La definición extendida de EJR, que permite grupos L- cohesivos con L no entero , puede ser inalcanzable. Definen dos relajaciones:

• EJR-M garantiza a cualquier subconjunto L -cohesivo de agentes, cuando existe un conjunto de recursos de tamaño total exactamente L , que al menos un agente en el subconjunto recibe una utilidad de al menos L. EJR-M se reduce a EJR tanto en entornos con solo candidatos indivisibles como en entornos con solo un candidato divisible.
• EJR- β (para cualquier número real β ) garantiza a cualquier grupo L-cohesivo que al menos un miembro del grupo recibe una utilidad mayor que L- β .

Ellos demuestran que:

• Para cualquier β <1, EJR- β puede ser inalcanzable.
• La regla de Nash no satisface EJR- β para ningún β .
• Una regla llamada Greedy-EJR satisface EJR-M, pero se ejecuta en tiempo exponencial y tiene un grado de proporcionalidad de aproximadamente L /2.
• Una generalización del método de partes iguales satisface EJR-1 pero no EJR-M, pero satisface EJR para instancias divisibles solamente, y tiene un grado de proporcionalidad ~ L /2.
• Una generalización de PAV , utilizando una extensión analítica a la serie armónica , satisface EJR-1 pero no EJR-M, no satisface EJR para instancias solo divisibles, pero tiene un grado de proporcionalidad mayor que L -1.