Distribución máxima por rango

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 9 de enero de 2021; la verificación requiere 1 edición .

La asignación de rango máximo ( RM) es la regla para una división justa de artículos indivisibles .  Supongamos que necesitamos distribuir varios artículos entre un número determinado de personas. Cada persona puede clasificar los elementos de mejor a peor. La regla MP dice que debemos dar a tantas personas como sea posible el mejor elemento (# 1 en la lista). Luego, deberíamos darle a tantas personas como sea posible el segundo elemento más importante (#2 en la lista), y así sucesivamente.

En el caso especial en el que cada persona debe recibir un elemento (por ejemplo, si los "elementos" son algunas acciones, y cada acción debe ser realizada por una sola persona), el problema se denomina coincidencia de rango máximo o coincidencia codiciosa .

La idea es similar a la de cortar el pastel según la utilidad , donde el objetivo es maximizar la suma de las utilidades de todos los participantes. Sin embargo, la regla de utilidad funciona con funciones de utilidad cardinales (cantidad) , mientras que la regla MP funciona con utilidades ordinales (clasificación).

Definiciones

Hay varios elementos y varios agentes. Cada agente tiene una ordenación lineal de elementos. Es posible que los agentes no valoren ciertos artículos. Para cada agente, podemos dividir los elementos en clases de equivalencia que contengan elementos del mismo rango. Por ejemplo, si la relación de preferencia de Alice es x > y, z > w , esto significa que la mejor opción de Alice es x , que es mejor que todos los demás elementos. Entonces Alice prefiere y y z , que a sus ojos tienen el mismo valor pero no son tan valiosos como x . En último lugar, Alice tiene w , que considera el peor de todos los elementos.

Para cualquier distribución de artículos a agentes, construimos su vector de rango de la siguiente manera. El elemento #1 en el vector es igual a la cantidad total de elementos que están en primer lugar para los propietarios, el elemento #2 es igual a la cantidad total de elementos que están en segundo lugar para los propietarios, y así sucesivamente.

La distribución de rango máximo es la distribución en la que el vector de rango es máximo (en orden lexicográfico ).

Ejemplo

Los tres elementos, x, y y z, se dividirán entre tres agentes, cuya clasificación es la siguiente:

En la distribución ( x , y , z ), Alice obtiene el primer elemento ( x ), Bob obtiene el segundo elemento ( y ) y Carl obtiene el tercer elemento ( z ). El vector de rango es entonces (1,1,1).

En la distribución ( x , z , y ), Alice y Carl obtienen los elementos en primer lugar, mientras que Bob obtiene el elemento que coloca en el tercer lugar. El vector de rango es entonces (2,0,1), que es lexicográficamente más grande que el vector (1,1,1) - le da a más personas la posibilidad de elegir el 1er lugar.

Es fácil comprobar que ninguna distribución da un vector de rango lexicográficamente mayor. Por lo tanto, la distribución ( x , z , y ) es máxima en rango. De manera similar, la distribución ( z , x , y ) es de rango máximo: da el mismo vector de rango (2,0,1).

Algoritmos

Los emparejamientos de MP fueron estudiados por primera vez por Robert Irving, quien los llamó emparejamientos codiciosos . Propuso un algoritmo que encuentra una coincidencia de MP en el tiempo , donde n es el número de agentes yc es la longitud máxima de la lista de preferencias del agente [1] .

Más tarde, se encontró un algoritmo que se ejecuta en el tiempo , donde m es la longitud total de todas las listas de preferencias (el número total de aristas en el gráfico) y C es el rango máximo del elemento utilizado en la coincidencia de MP (es decir, el número máximo de elementos distintos de cero en el vector de rango óptimo) [2] .

Una solución diferente que utiliza la coincidencia de peso máximo logra un tiempo de ejecución similar - [3] .

Opciones

La tarea tiene varias opciones.

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

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

Tanto la coincidencia de MP de tamaño máximo como la coincidencia justa se pueden encontrar reduciendo a la coincidencia de peso máximo [3] .

3. En el problema de la coincidencia de MR capacitiva, cada agente tiene una capacidad superior, que determina el límite superior del número total de elementos que se pueden transferir al agente. Cada artículo tiene una cuota superior, que especifica un límite superior en la cantidad de agentes diferentes a los que se puede entregar el artículo. El problema fue estudiado por Melhorn y Mikhail, quienes propusieron un algoritmo con tiempo de ejecución [4] . Hay un algoritmo mejorado con el tiempo de ejecución , donde B es la suma mínima de las cuotas de los agentes y la suma de las cuotas de los artículos. Se basa en una extensión de la descomposición de Galai-Edmonds de coincidencias de varios bordes [5] .

Véase también

Notas

  1. ↑ Irving, 2003 , pág. Tr–2003–136.
  2. ↑ Irving, Kavitha et al., 2006 , pág. 602–610.
  3. ↑ 12 Michael , 2007 , pág. 125–132.
  4. ↑ Mehlhorn, Michael, 2005 .
  5. ↑ Paluch, 2013 , pág. 324–335.

Literatura