Asignación de artículos por turnos

Procedimiento justo de asignación de artículos

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 .

Configuración

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).

Descripción

El protocolo procede de la siguiente manera:

1. Numere a las personas arbitrariamente del 1 al ; ${\displaystyle n}$
2. Mientras haya objetos sin asignar:
   • Deje que cada persona de 1 elija un objeto no asignado. ${\displaystyle n}$

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

Requisito de aditividad

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 .

Propiedades

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 . ${\displaystyle O(m{\text{log}}m)}$ ${\displaystyle O(1)}$

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 . ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle j}$ ${\displaystyle i}$ ${\displaystyle j}$

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

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.

Consideraciones de eficiencia

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). ${\displaystyle (zxv,ywu)}$ ${\displaystyle (yxw,zvu)}$

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. ${\displaystyle (y,z)}$ ${\displaystyle (w,x)}$ ${\displaystyle (u,v)}$ ${\displaystyle (ywu,zxv)}$

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).

Round-robin para grupos

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]

• 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 el grupo de j aún debería obtener de modo que se cumpla el criterio de equidad elegido para j .
• A cada elemento restante se le asigna un peso. El peso del ítem 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 valore g en 1.
• El grupo elige un artículo con el mayor peso.

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:

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

• ${\displaystyle B(r,s):=0~~{\text{if}}~~0<s~{\text{and}}~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{otherwise}}}$.

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:

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

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.

Extensiones

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]

Ver también

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 .

Referencias

1. Caragiannis, Ioannis; Kurokawa, David; Moulin, Hervé; Procaccia, Ariel D.; Shah, Nisarg; Wang, Junxing (2016). La imparcialidad irrazonable del máximo bienestar de Nash (PDF) . Actas de la Conferencia ACM sobre Economía y Computación de 2016 - EC '16. pag. 305. doi : 10.1145/2940716.2940726. ISBN 9781450339360.
2. Brustle, Johannes; Dippel, Jack; Narayan, Vishnu V.; Suzuki, Mashbat; Vetta, Adrián (13 de julio de 2020). "Un dólar cada uno elimina la envidia". Actas de la 21ª Conferencia ACM sobre Economía y Computación . CE '20. Evento virtual, Hungría: Asociación de Maquinaria de Computación. págs. 23–39. arXiv : 1912.02797 . doi :10.1145/3391403.3399447. ISBN 978-1-4503-7975-5. S2CID  208637311.
3. Segal-Halevi, Erel; Suksompong, Warut (1 de diciembre de 2019). "Asignación democrática y justa de bienes indivisibles". Inteligencia artificial . 277 : 103167. arXiv : 1709.02564 . doi :10.1016/j.artint.2019.103167. ISSN  0004-3702. S2CID  203034477.
4. Haris Aziz, Ioannis Caragiannis, Ayumi Igarashi, Toby Walsh (2019). "Asignación justa de bienes y tareas indivisibles" (PDF) . Conferencia IJCAI 2019 .{{cite web}}: Mantenimiento CS1: varios nombres: lista de autores ( enlace )
5. Biswas, Arpita; Camarero, Siddharth (13 de julio de 2018). "División justa bajo restricciones de cardinalidad". Actas de la 27ª Conferencia Internacional Conjunta sobre Inteligencia Artificial . IJCAI'18. Estocolmo, Suecia: AAAI Press: 91–97. arXiv : 1804.09521 . ISBN 978-0-9992411-2-7.
6. Chakraborty, Mithun; Igarashi, Ayumi; Suksompong, Warut; Zick, Yair (16 de agosto de 2021). "Libre de envidia ponderada en la asignación de artículos indivisibles". Transacciones ACM sobre Economía y Computación . CAm: 1–39.
7. Xiaowei Wu, Cong Zhang, Shengwei Zhou (2023). "Asignaciones ponderadas EF1 para tareas indivisibles". Conferencia CE 2023 .{{cite web}}: Mantenimiento CS1: varios nombres: lista de autores ( enlace )