Protocolos Simmons - Su

Los protocolos de Simmons-Su son un conjunto de protocolos para la división envidiosa . Los protocolos se basan en el lema de Sperner . Las ventajas de estos protocolos son que imponen pocas restricciones a las preferencias de los participantes y hacen preguntas sencillas a los participantes de la división, como "¿qué pieza prefieres?".

Se han desarrollado protocolos para resolver varios problemas relacionados.

Corte de torta

En el problema de cortar el pastel envidioso , un recurso divisible heterogéneo ("pastel") debe dividirse en n participantes con diferentes preferencias en partes del pastel. El pastel debe dividirse en n partes para que (a) cada participante obtenga una sola parte conectada y (b) cada participante crea que su parte es (en un sentido débil) mejor que todas las demás partes. El protocolo de resolución de problemas fue desarrollado por Forest Simmons en 1980 con la ayuda de Michael Starbird. El protocolo fue publicado por primera vez por Francis Su en 1999 [1] .

Dado un trozo del pastel (en n trozos), decimos que el participante prefiere un determinado trozo de ese trozo si cree que este trozo es mejor que todos los demás. "En un sentido débil" significa que el competidor no puede distinguir entre la pieza recibida y una o más piezas, por lo que puede "preferir" más de una pieza.

El protocolo hace las siguientes suposiciones sobre las preferencias de los participantes en la división

  1. Independencia de otros participantes : la preferencia depende del participante y del corte específico de todo el pastel, pero no de la elección realizada por otros participantes.
  2. Participantes hambrientos : un participante nunca prefiere una pieza vacía.
  3. Conjuntos de preferencia topológicamente cerrados : cualquier pieza que se prefiera bajo una secuencia de corte convergente se preferirá como el límite de la secuencia. Por ejemplo, si el competidor prefiere la primera pieza en todos los cortes cuando el primer corte se hizo en un puntoy prefiere la segunda pieza en todos los cortes cuando el corte se hace en, entonces en el caso de un corte en punto, elcompetidor igualmente Prefiero ambas piezas.

Estas condiciones son muy débiles y, a diferencia de otros protocolos sencillos , no se requiere que las funciones de utilidad sean aditivas o monótonas .

El protocolo considera secciones unidimensionales. Por ejemplo, un pastel puede ser un segmento unidimensional [0; 1] y cada pieza es un intervalo . La tarta puede ser rectangular y los cortes se hacen por el lado más largo (paralelos al lado más corto) para que todas las piezas queden rectangulares. Cada corte puede ser representado por n números , donde es la longitud de la i -ésima pieza. Suponemos que la longitud total del pastel es 1, entonces . El espacio de posibles cortes es entonces un símplex dimensional con n vértices en el espacio . El protocolo funciona en este símplex de la siguiente manera:

  1. Triangulamos el símplex cortado en símplex más pequeños del tamaño deseado.
  2. Asignamos un miembro a cada vértice de la triangularización para que cada subsimplex tenga n etiquetas diferentes.
  3. Para cada vértice de la triangularización, le preguntamos a su propietario: "¿Qué pieza preferirías si el corte se hiciera de acuerdo con este punto?". Marcamos el vértice con el número de la pieza preferida.

El marcado resultante satisface los requisitos del lema de coloración de Sperner :

Por lo tanto, según el lema de Sperner, debe haber al menos un subsimplejo en el que todas las etiquetas sean distintas. En el paso #2, asignamos cada vértice de este subsimplejo a un miembro diferente. Por lo tanto, hemos encontrado n conjuntos de cortes muy similares en los que diferentes participantes prefieren diferentes piezas del pastel.

Ahora podemos dividir el subsimplejo en una cuadrícula de subsubsimplejos más pequeños y repetir el proceso. Obtenemos una secuencia de simples cada vez más pequeños que convergen en un solo punto. Este punto corresponde a un conjunto de cortes. Por el supuesto de que "los conjuntos de preferencias son cerrados", en este conjunto de cortes todos los participantes prefieren piezas diferentes, por lo que este corte no tiene envidia.

La existencia de cortar sin envidia se ha probado antes [2] , pero la prueba de Simmons da un algoritmo aproximado constructivo . Por ejemplo, supongamos que se necesita dividir una propiedad de tierra y los socios acuerdan que una diferencia de 1 centímetro no es significativa para ellos. Luego, el símplex original puede triangularse en simples con lados de menos de 1 cm. En este caso, un punto en cualquier subsimple con todas las etiquetas diferentes corresponde a un corte (aproximado) libre de envidia.

A diferencia de otros protocolos de compartir envidiosos, en los que cada participante puede obtener una gran cantidad de migajas, el protocolo Simmons le da a cada participante una pieza conectada. Además, si el pastel original es rectangular, todas las piezas seleccionadas serán rectangulares.

Unos años después de la publicación del algoritmo, se demostró que cualquier corte sin envidia con piezas conectadas no se puede encontrar mediante protocolos finitos [3] . Por lo tanto, el algoritmo de aproximación es lo mejor que podemos esperar lograr en un tiempo finito. Actualmente, el algoritmo de Simmons es el único algoritmo para aproximar un corte de pastel envidioso con piezas conectadas.

El algoritmo de Simmons es uno de los pocos algoritmos de división justa que se implementan y están disponibles en línea [4] .

Una cosa buena del algoritmo es que las consultas de los participantes son muy simples: solo tienen que decidir para cada división qué pieza prefieren. Esto es diferente de otros algoritmos que hacen consultas como "cortar una pieza con un valor de 1/3" o consultas similares.

Complejidad computacional

Si bien la división celosa con piezas conectadas se puede aproximar con cualquier precisión utilizando el protocolo anterior, la aproximación en sí puede llevar mucho tiempo. En particular [5]

Alquiler armonioso

En este problema , n amigos deciden alquilar una casa con n dormitorios por un alquiler determinado por el dueño de la casa. Cada uno de los amigos puede tener preferencias diferentes: uno puede preferir una habitación grande, otro puede preferir una habitación con vista a la naturaleza, etc. Las siguientes dos tareas deben resolverse simultáneamente: (a) asignar un dormitorio a cada participante, (b) determinar la cuota que pagará cada participante, de modo que el monto de las contribuciones pagadas sea igual al monto total de la renta. La asignación no debe tener envidia , es decir, cada participante debe (en un sentido amplio) preferir su propia habitación + tarifa sobre otros participantes. Es decir, ninguno de los participantes debe preferir otra habitación por una tarifa asignada a esa habitación. El protocolo para resolver este problema fue desarrollado por Francis Su en 1999 [1] .

La idea es la siguiente. Normalice la renta total a 1. Luego, cada esquema de distribución de pago es un punto en el símplex -dimensional con vértices en . El protocolo Su se ejecuta en la versión dual de este simplex como los protocolos de corte de torta Simmons-Su: para cualquier vértice de la triangularización del simplex dual que corresponde a un determinado esquema de distribución de pagos, el protocolo le pregunta al propietario "¿Qué habitación prefiere en este esquema de pago?". Esto lleva a una coloración de Sperner en el símplex dual, y luego hay un subsimplejo pequeño que corresponde a una distribución aproximada de habitaciones y tarifas sin envidia.

Los artículos de Sun [6] y Procaccia [7] brindan una explicación popularizada del protocolo de alquiler armonioso [8] , y la página [9] proporciona una implementación en línea del protocolo.

Ver el artículo El problema de compartir piso para otras soluciones a este problema.

División del trabajo rutinario

En este problema, hay algunas tareas rutinarias que deben dividirse entre n participantes, por ejemplo, cortar un césped grande (césped).

El protocolo de "Alquiler Armonioso" se puede utilizar para obtener una distribución de los trabajos rutinarios sin envidia, simplemente tratando el alquiler como una tarea e ignorando las instalaciones. La divisibilidad del trabajo rutinario se puede lograr dividiendo el tiempo dedicado al trabajo [1] .

Cortar varios pasteles

En este problema se deben dividir dos o más tortas simultáneamente entre dos o más participantes, entregando a cada participante una sola pieza de cada torta. Por supuesto, si las preferencias son independientes (es decir, la utilidad de cortar es igual a la suma de las utilidades de las piezas seleccionadas de cada pastel), entonces el problema se puede resolver mediante métodos de cortar un pastel: solo llevamos a cabo una división envidiosa de cada pastel por separado. La pregunta se vuelve más interesante cuando los participantes tienen preferencias relacionadas con la torta, cuando la porción de una torta que prefiere un participante tiene un impacto en la evaluación de una porción de otra torta dada a un participante. Por ejemplo, si los "pasteles" son turnos de trabajo en dos días adyacentes, normalmente un empleado puede preferir el mismo turno cada día (por ejemplo, mañana+mañana o tarde+noche) en lugar de dos turnos diferentes (por ejemplo, tarde+mañana ).

La solución a este problema para el caso de 2 participantes compartidos y 2 o 3 tortas fue publicada en 2009 [10] . Si el número de tortas es m y cada torta es divisible en k partes, entonces el espacio de corte se puede representar como un poliedro de dimensión d con n vértices, donde y . Una generalización del lema de Sperner a los politopos [11] garantiza que si este politopo se triangulariza y etiqueta adecuadamente, existen al menos subsimples completamente etiquetados. Cada uno de estos simples corresponde a una distribución (aproximada) libre de envidia en la que cada participante obtiene una combinación diferente de trozos. Sin embargo, las combinaciones pueden superponerse: un participante puede recibir los turnos de "mañana" y "noche", mientras que el otro recibirá los turnos de "noche" y "mañana". Aunque esta es una opción diferente, no es compatible. La sección 4 del artículo de Cloutier, Nyman y Su [10] demuestra que la división sin envidia entre dos con piezas disjuntas puede ser imposible si , pero siempre posible si y (es decir, al menos un pastel se divide en tres partes y cada una participante recibe un trozo de cada pastel, y al menos un trozo de pastel se desecha). Se probaron resultados similares para tres tortas.

Véase también

Notas

  1. ↑ 1 2 3 Dom, 1999 , p. 930–942.
  2. ↑ Stromquist, 1980 , pág. 640–644.
  3. ↑ Stromquist, 2008 .
  4. ↑ Una implementación de Francis Su, Elisha Peterson y Patrick Winograd está disponible en: https://www.math.hmc.edu/~su/fairdivision/ Archivado el 27 de octubre de 2018 en Wayback Machine .
  5. ↑ Deng, Qi, Saberi, 2012 , pág. 1461.
  6. ↑ Alberto Sun. Para dividir la renta, comience con un triángulo . Tiempos de Nueva York . Consultado el 26 de agosto de 2014. Archivado desde el original el 11 de noviembre de 2020.
  7. ↑ Ariel Procaccia. La división justa y el problema de los filósofos quejumbrosos . La mano invisible de Turing . Consultado el 26 de agosto de 2014. Archivado desde el original el 3 de septiembre de 2014.
  8. ↑ Copia archivada (enlace no disponible) . Consultado el 31 de diciembre de 2019. Archivado desde el original el 27 de octubre de 2018. 
  9. ↑ https://www.nytimes.com/interactive/2014/science/rent-division-calculator.html Archivado el 31 de diciembre de 2019 en Wayback Machine Divide tu alquiler de manera justa
  10. ↑ 1 2 Cloutier, Nyman, Su, 2010 , p. 26–37.
  11. ↑ De Loera, Peterson, Su, 2002 , p. 1–26.

Literatura