Round Robin es un procedimiento para la asignación justa de artículos . Puede utilizarse para asignar varios artículos indivisibles entre varias personas, de modo que la asignación esté "casi" libre de envidia : cada agente cree que el paquete que recibió es al menos tan bueno como el paquete de cualquier otro agente, cuando como máximo uno El artículo se elimina del otro paquete. En los deportes, el procedimiento de todos contra todos se llama draft .
Hay m objetos para asignar y n personas ("agentes") con iguales derechos sobre estos objetos. Cada persona tiene diferentes preferencias sobre los objetos. Las preferencias de un agente están dadas por un vector de valores: un valor para cada objeto. Se supone que el valor de una cesta para un agente es la suma de los valores de los objetos de la cesta (en otras palabras, las valoraciones de los agentes son una función de conjunto aditiva sobre el conjunto de objetos).
El protocolo procede de la siguiente manera:
Se supone que cada persona, a su vez, elige un objeto no asignado con el valor más alto entre los objetos restantes.
El protocolo round-robin requiere aditividad, ya que requiere que cada agente elija su "mejor artículo" sin saber qué otros artículos va a obtener; La aditividad de las valoraciones garantiza que siempre habrá un "mejor artículo" (un artículo con el valor más alto). En otras palabras, se supone que los artículos son bienes independientes . El requisito de aditividad se puede relajar hasta una aditividad débil .
El protocolo round-robin es muy sencillo de ejecutar: sólo requiere m pasos. Cada agente puede ordenar los objetos con anticipación por valor descendente (esto lleva tiempo por agente) y luego seleccionar un objeto a tiempo .
La asignación final es EF1 : hasta un objeto sin envidia. Esto significa que, por cada par de agentes y , si como máximo se elimina un objeto del conjunto de , entonces no envidia .
Además, el round-robin garantiza que cada agente reciba la misma cantidad de artículos ( m / n , si m es divisible por n ), o casi la misma cantidad de artículos (si m no es divisible por n ). Por lo tanto, es útil en situaciones con restricciones de cardinalidad simples, como: asignar plazas de cursos a estudiantes donde cada estudiante debe recibir la misma cantidad de cursos.
El round-robin garantiza una equidad aproximada, pero el resultado puede ser ineficiente. Como ejemplo sencillo, supongamos que las valoraciones son:
El round robin, cuando Alice elige primero, produce la asignación con servicios públicos (24,23) y bienestar social 47. No es eficiente en el sentido de Pareto , ya que está dominado, por ejemplo, por la asignación con servicios públicos (25,25).
Un algoritmo alternativo, que puede lograr un mayor bienestar social, es el algoritmo de coincidencia de peso máximo iterado . [2] En cada iteración, encuentra una coincidencia de peso máximo en el gráfico bipartito en el que los nodos son los agentes y los elementos, y los pesos de los bordes son los valores de los agentes para los elementos. En el ejemplo anterior, la primera coincidencia es , la segunda es y la tercera es . La asignación total es con servicios públicos (18,32); el bienestar social (- la suma de las utilidades) es 50, que es mayor que en la asignación por turnos.
Tenga en cuenta que incluso la coincidencia de peso máximo iterada no garantiza la eficiencia de Pareto, ya que la asignación anterior está dominada por (xwv, zyu) con las utilidades (19,36).
El algoritmo de operación por turnos se puede utilizar para asignar elementos de manera justa entre grupos . En este entorno, todos los miembros de cada grupo consumen el mismo paquete, pero diferentes miembros de cada grupo pueden tener diferentes preferencias sobre los artículos. Esto plantea la cuestión de cómo cada grupo debería decidir qué elemento elegir a su vez. Supongamos que el objetivo de cada grupo es maximizar la fracción de sus miembros que están "felices", es decir, sienten que la asignación es justa (según sus preferencias personales). Supongamos también que los agentes tienen valoraciones aditivas binarias, es decir, cada agente valora cada elemento en 1 ("aprobar") o 0 ("desaprobar"). Luego, cada grupo puede decidir qué elemento elegir mediante votación de aprobación ponderada : [3]
El algoritmo resultante se llama RWAV (round-robin con votación de aprobación ponderada). La función de peso w ( r , s ) se determina con base en una función auxiliar B ( r , s ), definida por la siguiente relación de recurrencia:
Intuitivamente, B( r , s ) de un agente representa la probabilidad de que el agente esté satisfecho con la asignación final. Si s ≤ 0, entonces, por definición, esta probabilidad es 1: el agente no necesita más bienes para ser feliz. Si 0< s y r < s , entonces esta probabilidad es 0: el agente no puede ser feliz, ya que necesita más bienes de los disponibles. De lo contrario, B( r , s ) es el promedio entre B( r -1, s ) - cuando el otro grupo toma un bien deseado por el agente, y B( r -1, s-1 ) - cuando el grupo del agente toma un bien buscado por el agente. El término B( r -2, s -1) representa la situación en la que ambos grupos toman un bien deseado por el agente. Una vez que se calcula B( r , s ), la función de peso w se define de la siguiente manera:
Cuando se utiliza esta función de ponderación y se ejecuta RWAV con dos grupos, la fracción de miembros felices en el grupo 1 es al menos B( r , s( r )), y la fracción de miembros felices en el grupo 2 es al menos B( r -1 , s( r )). [3] : Lema 3.6 La función s ( r ) está determinada por el criterio de equidad. Por ejemplo, para una equidad de acciones maximin 1 de 3, s ( r ) = piso ( r /3). La siguiente tabla muestra algunos valores de la función B , con los valores de B(r-1, floor(r/3)) en negrita:
De esto se puede concluir que el algoritmo RWAV garantiza que, en ambos grupos, al menos el 75% de los miembros sientan que la asignación de 1 de 3 MMS es justa.
1. El protocolo round-robin garantiza EF1 cuando los artículos son bienes (- valorados positivamente por todos los agentes) y cuando son tareas (- valorados negativamente por todos los agentes). Sin embargo, cuando hay tanto bienes como tareas, no garantiza EF1. Una adaptación del round-robin llamada doble round-robin garantiza EF1 incluso con una combinación de bienes y tareas. [4]
2. Cuando los agentes tienen restricciones de cardinalidad más complejas (es decir, los elementos se dividen en categorías y, para cada categoría de elementos, hay un límite superior en la cantidad de elementos que cada agente puede obtener de esta categoría), la operación por turnos puede fallar. . Sin embargo, la combinación de round-robin con el procedimiento de gráfico de envidia proporciona un algoritmo que encuentra asignaciones que son EF1 y satisfacen las restricciones de cardinalidad. [5]
3. Cuando los agentes tienen pesos diferentes (es decir, los agentes tienen diferentes derechos sobre el total de artículos), un protocolo de turnos generalizado llamado turnos ponderados garantiza EF1 cuando los artículos son bienes (valorados positivamente por todos los agentes) [6] y el round robin ponderado invertido garantiza EF1 cuando los elementos son tareas (valoradas negativamente por todos los agentes). [7]
El round-robin es un caso especial de secuencia de selección .
Los protocolos de turnos se utilizan en otras áreas además de la asignación justa de artículos. Por ejemplo, consulte programación de todos contra todos y torneo de todos contra todos .
{{cite web}}
: Mantenimiento CS1: varios nombres: lista de autores ( enlace ){{cite web}}
: Mantenimiento CS1: varios nombres: lista de autores ( enlace )