El round robin es un procedimiento para la asignación justa de artículos . Se puede utilizar para asignar varios elementos indivisibles entre varias personas, de modo que la asignación sea "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 los mismos derechos sobre estos objetos. Cada persona tiene diferentes preferencias sobre los objetos. Las preferencias de un agente vienen dadas por un vector de valores, un valor para cada objeto. Se supone que el valor de un paquete para un agente es la suma de los valores de los objetos en el paquete (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:
- Numere las personas arbitrariamente de 1 a ;
- Mientras haya objetos sin asignar:
- Deje que cada persona de 1 a elija un objeto no asignado.
Se supone que cada persona a su vez elige un objeto no asignado con un 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 un valor más alto). En otras palabras, asume que los artículos son bienes independientes . El requisito de aditividad se puede relajar a una aditividad débil .
Propiedades
El protocolo round-robin es muy simple de ejecutar: solo requiere m pasos. Cada agente puede ordenar los objetos por adelantado por valor descendente (esto toma O ( m log m ) tiempo por agente) y luego escoger un objeto en el tiempo O (1).
La asignación final es EF1 : sin envidia hasta un objeto. Esto significa que, para cada par de agentes i y j , si como máximo se elimina un objeto del paquete de j , entonces i no envidia a 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 terminar en . En las últimas subsecuencias, el agente elige primero, para que pueda elegir su mejor artículo, para no envidiar a ningún otro agente. 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 tiene envidia.
Además, el round robin garantiza que cada agente reciba el mismo número de elementos ( m / n , si m es divisible por n ), o casi el mismo número de elementos (si m no es divisible por n ). Por lo tanto, es útil en situaciones con restricciones de cardinalidad simples, como: asignar asientos de curso a estudiantes donde cada estudiante debe recibir el mismo número de cursos.
Consideraciones de eficiencia
El round-robin garantiza una equidad aproximada, pero el resultado puede ser ineficiente. Como ejemplo simple, suponga que las valoraciones son:
z | y | X | w | v | tu | |
---|---|---|---|---|---|---|
Valor de Alice: | 12 | 10 | 8 | 7 | 4 | 1 |
Valor de George: | 19 | dieciséis | 8 | 6 | 5 | 1 |
Round-robin, cuando Alice elige primero, produce la asignación (zxv, ywu) con utilidades (24,23) y bienestar social 47. No es Pareto eficiente , ya que está dominado por ejemplo y la asignación (yxw, zvu), con servicios públicos (25,25).
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 (y, z), la segunda es (w, x) y la tercera es (u, v). La asignación total es (ywu, zxv) con utilidades (18,32); el bienestar social (- la suma de los servicios públicos) es 50, que es más alto que en la asignación por turnos.
Tenga en cuenta que incluso el emparejamiento de peso máximo iterado no garantiza la eficiencia de Pareto, ya que la asignación anterior está dominada por (xwv, zyu) con utilidades (19,36).
Extensiones
1. El protocolo round-robin garantiza EF1 cuando los artículos son bienes (- valorados positivamente por todos los agentes) y cuando son tareas domésticas (- valorados negativamente por todos los agentes). Sin embargo, cuando hay tanto bienes como quehaceres, no garantiza EF1. Una adaptación de round-robin llamada doble round-robin garantiza EF1 incluso con una mezcla de bienes y tareas. [3]
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 round robin 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. [4]
Ver también
El round-robin es un caso especial de secuencia de selección .
Los protocolos de round-robin se utilizan en otras áreas además de la asignación justa de artículos. Por ejemplo, consulte la programación por turnos y el torneo por turnos .
Referencias
- ^ Caragiannis, Ioannis; Kurokawa, David; Moulin, Hervé; Procaccia, Ariel D .; Shah, Nisarg; Wang, Junxing (2016). La equidad irrazonable del máximo bienestar de Nash (PDF) . Actas de la Conferencia ACM 2016 sobre Economía y Computación - EC '16. pag. 305. doi : 10.1145 / 2940716.2940726 . ISBN 9781450339360.
- ^ Brustle, Johannes; Dippel, Jack; Narayan, Vishnu V .; Suzuki, Mashbat; Vetta, Adrian (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 . EC '20. Evento virtual, Hungría: Asociación de Maquinaria Informática: 23–39. arXiv : 1912.02797 . doi : 10.1145 / 3391403.3399447 . ISBN 978-1-4503-7975-5. S2CID 208637311 .
- ^ Haris Aziz, Ioannis Caragiannis, Ayumi Igarashi, Toby Walsh (2019). "Asignación justa de bienes y tareas indivisibles" (PDF) . Conferencia IJCAI 2019 .CS1 maint: varios nombres: lista de autores ( enlace )
- ^ 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.