Asignación de artículos por turno rotativo

El sistema round robin es un procedimiento para la asignación equitativa de artículos . Se puede utilizar para asignar varios artículos indivisibles entre varias personas, de manera que la asignación sea prácticamente libre de envidia : cada agente cree que el conjunto que recibió es al menos tan bueno como el conjunto de cualquier otro agente, cuando como máximo se retira un artículo del conjunto del otro. En los deportes, el procedimiento round robin se denomina draft .

Hay m objetos para asignar y n personas ("agentes") con los mismos derechos sobre estos objetos. Cada persona tiene preferencias diferentes respecto a los objetos. Las preferencias de un agente se representan mediante un vector de valores: un valor para cada objeto. Se asume que el valor de un conjunto para un agente es la suma de los valores de los objetos que lo componen (es decir, las valoraciones de los agentes son una función aditiva del conjunto de objetos).

El protocolo procede de la siguiente manera:

1. Numere a las personas arbitrariamente del 1 al ${\displaystyle n}$;
2. Mientras haya objetos no asignados:
   • Que cada persona del 1 al${\displaystyle n}$Seleccione un objeto no asignado.

Se supone que cada persona, por turnos, elige un objeto no asignado con el valor más alto entre los objetos restantes.

El protocolo round-robin requiere aditividad, ya que exige que cada agente elija su "mejor artículo" sin saber qué otros artículos recibirá; la aditividad de las valoraciones garantiza que siempre existe un "mejor artículo" (el de mayor valor). En otras palabras, presupone que los artículos son bienes independientes . El requisito de aditividad puede flexibilizarse a una aditividad débil .

El protocolo round-robin es muy sencillo de ejecutar: solo requiere m pasos. Cada agente puede ordenar los objetos de antemano por valor descendente (esto lleva${\displaystyle O(m{\text{log}}m)}$tiempo por agente) y luego elegir un objeto en el tiempo${\displaystyle O(1)}$.

La asignación final es EF1 : libre de envidia hasta un objeto. Esto significa que, para cada par de agentes${\displaystyle i}$y${\displaystyle j}$, si como máximo se elimina un objeto del paquete de${\displaystyle j}$, entonces${\displaystyle i}$no envidia${\displaystyle j}$.

Prueba: ^{[ 1 ]} Para cada agente${\displaystyle i}$, divide las selecciones realizadas por los agentes en subsecuencias: la primera subsecuencia comienza en el agente 1 y termina en el agente${\displaystyle i-1}$; las subsecuencias posteriores comienzan en${\displaystyle i}$y termina en${\displaystyle i-1}$En las subsecuencias posteriores, el agente${\displaystyle i}$Elige primero, para poder elegir su mejor artículo, para no envidiar a ningún otro agente. Agente${\displaystyle i}$Solo uno de los agentes puede envidiar${\displaystyle 1,...,i-1}$y la envidia proviene únicamente de un elemento que seleccionaron en la primera subsecuencia. Si se elimina este elemento, el agente${\displaystyle i}$no tiene envidia.

Además, el método round-robin garantiza que cada agente reciba la misma cantidad de elementos ( m / n , si m es divisible por n ), o casi la misma cantidad (si m no es divisible por n ). Por lo tanto, resulta útil en situaciones con restricciones de cardinalidad simples, como la asignación de plazas en cursos a estudiantes, donde cada estudiante debe recibir la misma cantidad de cursos.

El sistema round-robin garantiza una equidad aproximada, pero el resultado podría ser ineficiente. Como ejemplo sencillo, supongamos que las valoraciones son:

En el sistema round-robin, cuando Alice elige primero, se obtiene la asignación.${\displaystyle (zxv,ywu)}$con utilidades (24,23) y bienestar social 47. No es eficiente en el sentido de Pareto , ya que está dominado por la asignación${\displaystyle (yxw,zvu)}$, con utilidades (25,25).

Un algoritmo alternativo, que puede lograr un mayor bienestar social, es el algoritmo de emparejamiento iterativo de peso máximo . ^{[ 2 ]} En cada iteración, encuentra un emparejamiento de peso máximo en el grafo bipartito en el que los nodos son los agentes y los elementos, y los pesos de las aristas son los valores de los agentes para los elementos. En el ejemplo anterior, el primer emparejamiento es${\displaystyle (y,z)}$, el segundo es${\displaystyle (w,x)}$y el tercero es${\displaystyle (u,v)}$. La asignación total es${\displaystyle (ywu,zxv)}$con utilidades (18,32); el bienestar social (- la suma de utilidades) es 50, que es mayor que en la asignación round-robin.

Tenga en cuenta que incluso el emparejamiento iterado de peso máximo no garantiza la eficiencia de Pareto, ya que la asignación anterior está dominada por (xwv, zyu) con utilidades (19,36).

El método round-robin no es un mecanismo veraz . Por ejemplo, supongamos que hay 60 artículos que Alice valora en 60, 59, ..., 2, 1. George clasifica los artículos de la siguiente manera (donde usamos la valoración de Alice como nombre del artículo): 59 > 57 > ... > 3 > 1 > 2 > 4 > ... > 58 > 60.

Alice juega primero. Si declara sus valoraciones reales, obtiene los treinta artículos de valor par (60, 58, ..., 4, 2) mientras que George toma los treinta de valor impar, por lo que el valor de Alice es 930. Pero si Alice declara 59 > 57 > ..., > 25 > 23 > 60 > 58 > ... > 24 > 22 > ... entonces primero obtiene diez artículos de valor impar 59, 55, ..., 27, 23 y luego 20 de valor par 60, 58, ..., 24, 22, y su valor es 410 + 820 = 1230. En lugar de los diez artículos pares de bajo valor 2, ..., 20, obtuvo diez artículos impares de alto valor; su ganancia es 21 + 23 + ... + 37 + 39 = 300.

El algoritmo round-robin se puede utilizar para asignar artículos de manera justa entre grupos . En este contexto, todos los miembros de cada grupo consumen el mismo paquete, pero los 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é artículo elegir en su turno. Supongamos que el objetivo de cada grupo es maximizar la fracción de sus miembros que están "contentos", es decir, que sienten que la asignación es justa (de acuerdo con sus preferencias personales). Supongamos también que los agentes tienen valoraciones aditivas binarias, es decir, cada agente valora cada artículo con 1 ("aprobar") o 0 ("desaprobar"). Entonces, cada grupo puede decidir qué artículo elegir utilizando votación de aprobación ponderada : ^{[ 3 ]}

• A cada miembro del grupo se le asigna un peso. El peso del miembro j es una determinada función w ( r _j , s _j ), donde:
  • r _j es el número de bienes restantes que j aprueba;
  • s _j es el número de bienes que jEl grupo de debe seguir obteniendo tal que se satisfaga el criterio de equidad elegido para j .
• A cada elemento restante se le asigna un peso. El peso del elemento g es la suma de los pesos de los agentes que aprueban g : suma de w ( r _j , s _j ) para todo j tal que j valora g en 1.
• El grupo elige el objeto con mayor peso.

El algoritmo resultante se denomina RWAV (round-robin con votación de aprobación ponderada). La función de ponderación w ( r , s ) se determina en función de una función auxiliar B ( r , s ), definida por la siguiente relación de recurrencia :

• ${\displaystyle B(r,s):=1~~{\text{si}}~~s\leq 0;}$

• ${\displaystyle B(r,s):=0~~{\text{si}}~~0<s~{\text{y}}~r<s;}$
• ${\displaystyle B(r,s):=\min {\bigg [}{\frac {1}{2}}[B(r-1,s)+B(r-1,s-1)],B(r-2,s-1){\bigg ]}~~{\text{en otro caso}}}$.

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 estar satisfecho. Si 0 < s y r < s , entonces esta probabilidad es 0: el agente no puede estar satisfecho, ya que necesita más bienes de los disponibles. En caso 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 deseado 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 calculado B( r , s ), la función de ponderación w se define de la siguiente manera:

${\displaystyle w(r,s):=B(r,s)-B(r-1,s)}$

Al usar esta función de ponderación y ejecutar 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 participación maximin de 1 de 3 , s ( r ) = floor( 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 consideran que la asignación es justa en una proporción de 1 de cada 3 MMS.

1. El protocolo round-robin garantiza EF1 cuando los elementos son bienes (valorados positivamente por todos los agentes) y cuando son tareas (valoradas negativamente por todos los agentes). Sin embargo, cuando hay tanto bienes como tareas, no garantiza EF1. Una adaptación del round-robin, denominada doble round-robin, garantiza EF1 incluso con una mezcla 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, existe un límite superior en la cantidad de elementos que cada agente puede obtener de dicha categoría), el algoritmo round-robin podría fallar. Sin embargo, la combinación de round-robin con el procedimiento de grafo de envidia da como resultado un algoritmo que encuentra asignaciones que son EF1 y satisfacen las restricciones de cardinalidad. ^{[ 5 ]}

3. Cuando los agentes tienen diferentes ponderaciones (es decir, los agentes tienen diferentes derechos sobre el total de elementos), un protocolo round-robin generalizado llamado round-robin ponderado garantiza EF1 cuando los elementos son bienes (valorados positivamente por todos los agentes) ^{[ 6 ]} y el round-robin ponderado inverso garantiza EF1 cuando los elementos son tareas (valoradas negativamente por todos los agentes). ^{[ 7 ]}

El sistema round-robin es un caso especial de secuencia de selección .

Los protocolos round-robin se utilizan en otros ámbitos además de la asignación equitativa de elementos. Por ejemplo, véase la programación round-robin y el torneo round-robin .