asignación de rango máximo

La asignación de rango máximo (RM) es una regla para la división equitativa de elementos indivisibles. Supongamos que debemos distribuir algunos elementos entre varias personas. Cada persona puede clasificar los elementos del mejor al peor. La regla RM establece que debemos dar a la mayor cantidad de personas posible su mejor elemento (n.° 1). Además, debemos dar a la mayor cantidad posible su segundo mejor elemento (n.° 2), y así sucesivamente.

En el caso especial en el que cada persona debe recibir un solo elemento (por ejemplo, cuando los "elementos" son tareas y cada tarea debe ser realizada por una sola persona), el problema se denomina emparejamiento de rango máximo o emparejamiento voraz .

La idea es similar a la del reparto utilitarista de pasteles , donde el objetivo es maximizar la suma de las utilidades de todos los participantes. Sin embargo, la regla utilitarista funciona con funciones de utilidad cardinales (numéricas) , mientras que la regla RM funciona con utilidades ordinales (clasificaciones).

Hay varios elementos y varios agentes. Cada agente tiene un orden total sobre los elementos. Los agentes pueden ser indiferentes entre algunos elementos; para cada agente, podemos dividir los elementos en clases de equivalencia que contienen elementos del mismo rango. Por ejemplo, si la relación de preferencia de Alice es x > y, z > w , significa que la primera opción de Alice es x, que es mejor para ella que todos los demás elementos; la segunda opción de Alice es y y z, que son igualmente buenas a sus ojos pero no tan buenas como x; y la tercera opción de Alice es w, que considera peor que todos los demás elementos.

Para cada asignación de artículos a los agentes, construimos su vector de clasificación de la siguiente manera. El elemento n.° 1 del vector es el número total de artículos que son la primera opción para sus dueños; el elemento n.° 2 es el número total de artículos que son la segunda opción para sus dueños; y así sucesivamente.

Una asignación de rango máximo es aquella en la que el vector de rango es máximo, en orden lexicográfico .

Tres elementos, xy y z, deben dividirse entre tres agentes cuyas clasificaciones son:

• Alicia: x > y > z
• Bob: x > y > z
• Carl: y > x > z

En la asignación ( x , y , z ), Alice obtiene su primera opción ( x ), Bob obtiene su segunda opción ( y ) y Carl obtiene su tercera opción ( z ). Por lo tanto, el vector de rangos es (1,1,1).

En la asignación ( x , z , y ), tanto Alice como Carl obtienen su primera opción y Bob obtiene su tercera opción. El vector de rangos es, por lo tanto, (2, 0, 1), que es lexicográficamente superior a (1, 1, 1), ya que otorga a más personas su primera opción.

Es fácil comprobar que ninguna asignación produce un vector de rango lexicográficamente superior. Por lo tanto, la asignación ( x , z , y ) es de rango máximo. De manera similar, la asignación ( z , x , y ) también es de rango máximo, ya que produce el mismo vector de rango (2, 0, 1).

Los emparejamientos RM fueron estudiados por primera vez por Robert Irving, quien los llamó emparejamientos voraces . Presentó un algoritmo que encuentra un emparejamiento RM en tiempo${\displaystyle O(n^{2}c^{3})}$donde n es el número de agentes y c es la longitud máxima de una lista de preferencias de un agente. ^{[ 1 ]}

Más tarde se encontró un algoritmo mejorado que se ejecuta en tiempo real.${\displaystyle O(m\cdot \min(n,C{\sqrt {n}}))}$, donde m es la longitud total de todas las listas de preferencias (número total de aristas en el grafo), y C es el rango máximo de un elemento utilizado en un emparejamiento RM (es decir, el número máximo de elementos distintos de cero en un vector de rango óptimo). ^{[ 2 ]} El algoritmo reduce el problema a un emparejamiento de cardinalidad máxima . Intuitivamente, nos gustaría primero encontrar un emparejamiento de cardinalidad máxima utilizando solo aristas de rango 1; luego, extender este emparejamiento a un emparejamiento de cardinalidad máxima utilizando solo aristas de rangos 1 y 2; luego, extender este emparejamiento a un emparejamiento de cardinalidad máxima utilizando solo aristas de rangos 1, 2 y 3; y así sucesivamente. El problema es que, si elegimos el emparejamiento de cardinalidad máxima "incorrecto" para el rango 1, podríamos perder el emparejamiento óptimo para el rango 2. El algoritmo de ^{[ 2 ]} resuelve este problema utilizando la descomposición de Dulmage-Mendelsohn , que es una descomposición que utiliza un emparejamiento de cardinalidad máxima, pero no depende de qué emparejamiento se elija (la descomposición es la misma para cualquier emparejamiento de cardinalidad máxima elegido). Funciona de la siguiente manera.

1. Sea G ₁ el subgrafo de G que contiene solo aristas de rango 1 (el rango más alto).
2. Encuentra un emparejamiento de cardinalidad máxima en G ₁ , y úsalo para encontrar la descomposición de G ₁ en E ₁ , O ₁ y U ₁ .
3. Una propiedad de la descomposición es que cada emparejamiento de cardinalidad máxima en G ₁ satura todos los vértices en O ₁ y U ₁ . Por lo tanto, en un emparejamiento de rango máximo, todos los vértices en O ₁ y U ₁ son adyacentes a una arista de rango 1. Así, podemos eliminar del grafo todas las aristas con rango 2 o superior adyacentes a cualquiera de estos vértices.
4. Otra propiedad de la descomposición es que cualquier emparejamiento de cardinalidad máxima en G ₁ contiene solo aristas E ₁ -O ₁ y U ₁ -U _1. Por lo tanto, podemos eliminar todas las demás aristas (aristas O ₁ -O ₁ y O ₁ -U ₁ ) del grafo.
5. Añade a G1 _todas las aristas con el siguiente rango más alto. Si no existen tales aristas, detente. De lo contrario, vuelve al paso 2.

Otra solución, que utiliza emparejamientos de peso máximo , logra un tiempo de ejecución similar:${\displaystyle O(m\cdot \min(n+C,C{\sqrt {n}}))}$. ^{[ 3 ]}

El problema tiene varias variantes.

1. En el emparejamiento RM de cardinalidad máxima , el objetivo es encontrar, entre todos los diferentes emparejamientos RM, aquel con el número máximo de emparejamientos.

2. En el emparejamiento justo , el objetivo es encontrar un emparejamiento de cardinalidad máxima tal que se utilice el número mínimo de aristas de rango r , dado que se utiliza el número mínimo de aristas de rango r −1, y así sucesivamente.

Tanto el emparejamiento RM de cardinalidad máxima como el emparejamiento justo se pueden encontrar mediante la reducción al emparejamiento de peso máximo. ^{[ 3 ]}

3. En el problema de emparejamiento RM con capacidad limitada , cada agente tiene una capacidad máxima que indica un límite superior en el número total de elementos que debe obtener. Cada elemento tiene una cuota máxima que indica un límite superior en el número de agentes diferentes a los que se le puede asignar. Fue estudiado por primera vez por Melhorn y Michail, quienes proporcionaron un algoritmo con tiempo de ejecución.${\displaystyle O(Cnm\log(n^{2}/m)\log(n))}$. ^{[ 4 ]} Existe un algoritmo mejorado con tiempo de ejecución${\displaystyle O(m\cdot \min(B,C{\sqrt {B}}))}$donde B es el mínimo de la suma de las cuotas de los agentes y la suma de las cuotas de los elementos. Se basa en una extensión de la descomposición de Gallai-Edmonds a emparejamientos de múltiples aristas. ^{[ 5 ]}

• Asignación de artículos justos
• Emparejamiento estable
• Emparejamiento sin envidia
• Coincidencia de prioridades