Los protocolos Simmons-Su son varios protocolos para la división sin envidia . Se basan en el lema de Sperner . La ventaja de estos protocolos es que imponen pocas restricciones a las preferencias de los participantes y solo les plantean preguntas simples como "¿qué pieza prefiere?".
Se desarrollaron protocolos para resolver varios problemas relacionados:
En el problema de cortar la torta sin envidia , una "torta" (un recurso divisible heterogéneo) tiene que ser dividida entre n socios con diferentes preferencias sobre partes de la torta. La torta tiene que ser dividida en n partes de tal manera que: (a) cada socio reciba una sola parte conectada, y (b) cada socio crea que su parte es (débilmente) mejor que todas las otras partes. Un protocolo para resolver este problema fue desarrollado por Forest Simmons en 1980, en una correspondencia con Michael Starbird . Fue publicado por primera vez por Francis Su en 1999. [1]
Dado un conjunto de cortes (es decir, una determinada partición de la torta en n porciones), decimos que un compañero prefiere una porción dada si cree que esta porción es débilmente mejor que todas las demás. "Débilmente" significa que el compañero puede ser indiferente entre la porción y una o más porciones, por lo que puede (en caso de empate) "preferir" más de una porción.
El protocolo establece las siguientes presunciones sobre las preferencias de los socios:
La condición de cerramiento descarta la existencia de puntos únicos de la torta con deseabilidad positiva. [ ¿Por qué? ]
Estos supuestos son muy suaves: a diferencia de otros protocolos para una distribución justa de los beneficios , no se requiere que las funciones de utilidad sean aditivas o monótonas.
El protocolo considera conjuntos de cortes unidimensionales. Por ejemplo, la torta puede ser el intervalo unidimensional [0,1] y cada trozo es un intervalo; o bien, la torta puede ser un rectángulo cortado a lo largo de su lado más largo de modo que cada trozo sea un rectángulo. Cada conjunto de cortes puede representarse mediante n números x i , i = 1, ..., n , donde x i es la longitud del i ésimo trozo. Suponemos que la longitud total de la torta es 1, por lo que x 1 + ... + x n = 1. El espacio de particiones posibles es, por tanto, un símplex ( n − 1)-dimensional con n vértices en R n . El protocolo funciona con este símplex de la siguiente manera:
El etiquetado generado satisface los requisitos de coloración del lema de Sperner :
Por lo tanto, según el lema de Sperner, debe haber al menos un subsímplex en el que las etiquetas sean todas diferentes. En el paso n.° 2, asignamos cada vértice de este subsímplex a un compañero diferente. Por lo tanto, hemos encontrado n conjuntos de cortes muy similares en los que los diferentes compañeros prefieren diferentes porciones de pastel.
Ahora podemos triangular el subsímplex en una malla más fina de subsímplex y repetir el proceso. Obtenemos una secuencia de símplex cada vez más pequeños que convergen en un único punto. Este punto corresponde a un único conjunto de corte. Según el supuesto de que "los conjuntos de preferencias son cerrados", en este conjunto de corte cada miembro de la pareja prefiere una pieza diferente. ¡Esta es una partición sin envidias!
La existencia de una partición libre de envidias ya se ha demostrado anteriormente [2] , pero la prueba de Simmons también proporciona un algoritmo de aproximación constructiva. Por ejemplo, supongamos que se debe dividir una determinada finca y que los socios están de acuerdo en que una diferencia de más o menos 1 centímetro es irrelevante para ellos. Entonces, el símplex original se puede triangular en símplex con una longitud de lado inferior a 1 cm. Entonces, cada punto en el subsímplex en el que todas las etiquetas son diferentes corresponde a una partición (aproximada) libre de envidias.
A diferencia de otros protocolos libres de envidia, que pueden asignar a cada socio una gran cantidad de migajas, el protocolo de Simmons le otorga a cada socio un solo trozo conectado. Además, si la tarta original es rectangular, entonces cada trozo es un rectángulo.
Varios años después de que se publicara este algoritmo, se demostró que no se pueden encontrar particiones sin envidia con piezas conectadas mediante protocolos finitos. [3] Por lo tanto, un algoritmo de aproximación es lo mejor que podemos esperar en un tiempo finito. Actualmente, el algoritmo de Simmons es el único algoritmo de aproximación para el corte de pastel sin envidia con piezas conectadas.
El algoritmo de Simmons es uno de los pocos algoritmos de división justa que se han implementado y puesto en línea. [4]
Una de las ventajas del algoritmo es que las consultas que plantea a los socios son muy sencillas: sólo tienen que decidir, en cada partición, qué trozo prefieren. Esto contrasta con otros algoritmos, que plantean consultas numéricas como "cortar un trozo con un valor de 1/3", etc.
Si bien una división sin envidia con piezas conectadas se puede aproximar con cualquier precisión utilizando el protocolo anterior, la aproximación puede llevar mucho tiempo. En particular: [5]
En este problema, n compañeros de casa han decidido alquilar una casa de n habitaciones por un precio determinado por el propietario. Cada compañero de casa puede tener preferencias diferentes: uno puede preferir una habitación grande, otro puede preferir una habitación con vistas, etc. Los dos problemas siguientes deben resolverse simultáneamente: (a) Asignar una habitación a cada compañero, (b) Determinar el alquiler que cada socio debe pagar, de modo que la suma de los pagos sea igual al alquiler total. La asignación debe estar libre de envidias , en el sentido de que cada socio prefiere débilmente su parcela de habitación + alquiler sobre las otras parcelas, es decir, ningún socio querría tomar otra habitación por el alquiler asignado a esa habitación. En 1999, Francis Su desarrolló un protocolo para resolver este problema. [1]
La idea es la siguiente: se normaliza el alquiler total a 1. Luego, cada esquema de precios es un punto en un símplex de dimensión 1 con vértices en . El protocolo de Su opera sobre una versión dualizada de este símplex de manera similar a los protocolos Simmons-Su para el corte de torta: para cada vértice de una triangulación del símplex dual, que corresponde a un cierto esquema de precios, le pregunta al socio propietario "¿qué habitación prefiere en ese esquema de precios?". Esto da como resultado una coloración de Sperner del símplex dual y, por lo tanto, existe un pequeño subsímplex que corresponde a una asignación aproximada de habitaciones y alquileres sin envidia.
[6] y [7] proporcionan explicaciones popularizadas del protocolo Rental Harmony. [8] y [9] proporcionan implementaciones en línea.
Consulte Armonía de alquiler para obtener más soluciones a este problema.
En este problema, hay una tarea que debe dividirse entre n socios, por ejemplo, cortar el césped en un área grande.
El protocolo Rental Harmony se puede utilizar para lograr una distribución de tareas que no genere envidia, simplemente considerando los pagos del alquiler como tareas y haciendo caso omiso de las habitaciones. La divisibilidad de las tareas se puede lograr dividiendo el tiempo dedicado a ellas. [1]
En este problema, dos o más pasteles tienen que ser divididos simultáneamente entre dos o más socios, dando a cada socio un solo pedazo de cada pastel. Por supuesto, si las preferencias son independientes (es decir, la utilidad de una asignación es la suma de las utilidades del pedazo asignado en cada pastel), entonces el problema puede ser resuelto por métodos de división de un pastel – simplemente hacer una partición sin envidia en cada pastel por separado. La cuestión se vuelve interesante cuando los socios tienen preferencias vinculadas sobre los pasteles, en las que la porción de un pastel que prefiere el socio está influenciada por la porción de otro pastel que se le asigna. Por ejemplo, si los "pasteles" son los horarios de los turnos de trabajo en dos días consecutivos, un empleado típico puede preferir tener el mismo turno todos los días (por ejemplo, mañana-mañana o tarde-tarde) que tener turnos diferentes.
En 2009 se publicó una solución a este problema para el caso de 2 socios y 2 o 3 pasteles. [10] Si el número de pasteles es m , y cada pastel se divide en k pedazos, entonces el espacio de particiones puede representarse por un politopo de dimensión d y n vértices , donde d = m ( k − 1) y n = k m . Una generalización del lema de Sperner a los politopos [11] garantiza que, si este politopo se triangula y se etiqueta de manera apropiada, hay al menos n − d subsímplices con un etiquetado completo; cada uno de estos símplices corresponde a una asignación (aproximada) libre de envidia en la que cada socio recibe una combinación diferente de pedazos. Sin embargo, las combinaciones pueden superponerse: un socio puede obtener los turnos "matutino" y "vespertino" mientras que otro socio puede obtener "vespertino" y "nocturno". Aunque estas son selecciones diferentes, son incompatibles. La sección 4 de [10] demuestra que una división sin envidia entre dos socios con partes disjuntas podría ser imposible si m = k = 2, pero siempre es posible si m = 2 y k = 3 (es decir, al menos una torta se divide en tres partes, cada socio recibe una sola parte de cada torta y al menos una parte se descarta). Se demuestran resultados similares para tres tortas.
