Asignación de artículos por turnos

Procedimiento de asignación justa de artículos

El método round robin es un procedimiento de asignación justa de ítems . Puede utilizarse para asignar varios ítems indivisibles entre varias personas, de modo que la asignación esté "casi" libre de envidias : cada agente cree que el paquete que recibió es al menos tan bueno como el paquete de cualquier otro agente, cuando como máximo se elimina un ítem del otro paquete. En los deportes, el procedimiento round robin se denomina draft .

Configuración

Hay m objetos para asignar y n personas ("agentes") con los mismos 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 un conjunto para un agente es la suma de los valores de los objetos en el conjunto (en otras palabras, las valoraciones de los agentes son una función aditiva del conjunto de objetos).

Descripción

El protocolo se desarrolla de la siguiente manera:

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

Se supone que cada persona en su turno 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 obtendrá; la aditividad de las valoraciones garantiza que siempre haya un "mejor artículo" (un artículo con el valor más alto). En otras palabras, supone que los artículos son bienes independientes . El requisito de aditividad puede flexibilizarse a aditividad débil .

Propiedades

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

La asignación final es EF1 (libre de envidia hasta un objeto). Esto significa que, para cada par de agentes y , si se elimina como máximo un objeto del conjunto de , entonces no envidia a . ${\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 en y terminan en . En las últimas subsecuencias, el agente elige primero, por lo que puede elegir su mejor elemento, por lo que no envidia a ningún otro agente. El agente solo puede envidiar a uno de los agentes , y la envidia proviene solo de un elemento que seleccionó en la primera subsecuencia. Si se elimina este elemento, el agente no envidia. ${\displaystyle i}$ ${\displaystyle i-1}$ ${\displaystyle i}$ ${\displaystyle i-1}$ ${\displaystyle i}$ ${\displaystyle i}$ ${\displaystyle 1,...,i-1}$ ${\displaystyle i}$

Además, el método round-robin garantiza que cada agente reciba la misma cantidad de ítems ( m / n , si m es divisible por n ), o casi la misma cantidad de ítems (si m no es divisible por n ). Por lo tanto, es útil en situaciones con restricciones de cardinalidad simples, como por ejemplo: asignar cupos a los estudiantes en un curso, donde cada estudiante debe recibir la misma cantidad de cursos.

Consideraciones de eficiencia

El método round-robin garantiza una imparcialidad aproximada, pero el resultado puede ser ineficiente. Como ejemplo simple, supongamos que las valoraciones son:

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

Un algoritmo alternativo, que puede lograr un mayor bienestar social, es el algoritmo de emparejamiento de peso máximo iterado . ^[2] En cada iteración, encuentra un emparejamiento 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 con respecto a los elementos. En el ejemplo anterior, el primer emparejamiento es , el segundo es y el tercero es . La asignación total es con utilidades (18,32); el bienestar social (- la suma de las utilidades) es 50, que es más alto que en la asignación round-robin. ${\displaystyle (y,z)}$ ${\displaystyle (w,x)}$ ${\displaystyle (u,v)}$ ${\displaystyle (ywu,zxv)}$

Téngase 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 utilidades (19,36).

Round-robin para grupos

El algoritmo round-robin puede utilizarse para asignar de forma justa los artículos entre los grupos . En este contexto, todos los miembros de cada grupo consumen el mismo paquete, pero los distintos miembros de cada grupo pueden tener distintas preferencias sobre los artículos. Esto plantea la cuestión de cómo debería decidir cada grupo 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 "felices", es decir, que 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 artículo en 1 ("aprueba") o 0 ("desaprueba"). Entonces, cada grupo puede decidir qué artículo 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 función determinada 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 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 todos los j tales que j valora g en 1.
• El grupo elige el objeto con mayor peso.

El algoritmo resultante se denomina RWAV (round-robin with weighted approved voting). La función de ponderación w ( r , s ) se determina a partir de 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é contento 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 contento. Si 0 < s y r < s , entonces esta probabilidad es 0: el agente no puede estar contento, ya que necesita más bienes de los que están 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 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 que se calcula 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 utilizar esta función de peso 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 máxima de 1 de cada 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 considera que la asignación es 1 de cada 3 MMS justa.

Extensiones

1. El protocolo round-robin garantiza EF1 cuando los ítems son bienes (valorados positivamente por todos los agentes) y cuando son tareas (valoradas negativamente por todos los agentes). Sin embargo, cuando hay bienes y tareas, no garantiza EF1. Una adaptación del round-robin llamada double 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 de elementos, existe un límite superior en la cantidad de elementos que cada agente puede obtener de esta categoría), el método round-robin podría fallar. Sin embargo, la combinación del método round-robin con el procedimiento envy-graph brinda un algoritmo que encuentra asignaciones que son EF1 y satisfacen las restricciones de cardinalidad. ^[5]

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

Véase también

El método round-robin es un caso especial de secuencia de selección .

Los protocolos de todos contra todos se utilizan en otras áreas además de la asignación justa de ítems. Por ejemplo, consulte la programación de todos contra todos y el torneo de todos contra todos .

Referencias

1. Caragiannis, Ioannis; Kurokawa, David; Moulin, Hervé; Procaccia, Ariel D.; Shah, Nisarg; Wang, Junxing (2016). La justicia irrazonable del bienestar máximo de Nash (PDF) . Actas de la Conferencia ACM de 2016 sobre Economía y Computación - EC '16. p. 305. doi :10.1145/2940716.2940726. ISBN 9781450339360.
2. Brustle, Johannes; Dippel, Jack; Narayan, Vishnu V.; Suzuki, Mashbat; Vetta, Adrian (13 de julio de 2020). "Un dólar por persona elimina la envidia". Actas de la 21.ª Conferencia de la ACM sobre economía y computación . EC '20. Evento virtual, Hungría: Association for Computing Machinery. págs. 23–39. arXiv : 1912.02797 . doi :10.1145/3391403.3399447. ISBN 978-1-4503-7975-5.S2CID208637311  .​
3. Segal-Halevi, Erel; Suksompong, Warut (1 de diciembre de 2019). "Asignación justa y democrática 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}}: CS1 maint: varios nombres: lista de autores ( enlace )
5. Biswas, Arpita; Barman, Siddharth (13 de julio de 2018). "División justa bajo restricciones de cardinalidad". Actas de la 27.ª Conferencia conjunta internacional 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). "Libreza ponderada de envidia en la asignación de elementos indivisibles". ACM Transactions on Economics and Computation . ACm: 1–39.
7. Xiaowei Wu, Cong Zhang, Shengwei Zhou (2023). "Asignaciones ponderadas EF1 para tareas indivisibles". Conferencia CE 2023 .{{cite web}}: CS1 maint: varios nombres: lista de autores ( enlace )