Secuencia de recolección

Una secuencia de selección es un protocolo para la asignación justa de artículos . Supongamos que m elementos deben dividirse entre n agentes. Una forma de asignar los artículos es dejar que un agente seleccione un solo artículo, luego dejar que otro agente seleccione un solo artículo, y así sucesivamente. Una secuencia de selección es una secuencia de m nombres de agentes, donde cada nombre determina qué agente es el siguiente en elegir un artículo.

Como ejemplo, supongamos que se deben dividir 4 elementos entre Alice y Bob. Algunas posibles secuencias de recolección son:

AABB: Alice elige dos elementos, luego Bob elige los dos elementos restantes.
ABAB: Alice elige un elemento, luego Bob elige un elemento, luego Alice nuevamente y luego Bob nuevamente. Esto es más "justo" que AABB ya que le permite a Bob tener más posibilidades de obtener un artículo mejor.
ABBA: Alice elige un artículo, luego Bob elige dos artículos y luego Alice recibe el artículo restante. Esto es intuitivamente incluso más "justo" que ABAB, ya que, en ABAB, Bob siempre está detrás de Alice, mientras que ABBA está más equilibrado. ^[1]

Ventajas

Una secuencia de selección tiene varios méritos como protocolo de división justa: ^[2]^{: 307}

Simplicidad: es muy fácil para los agentes entender cómo funciona el protocolo y qué deben hacer en cada paso; simplemente elija el mejor elemento.
Privacidad: los agentes no tienen que revelar toda su función de valoración ni siquiera su clasificación completa. Sólo tienen que revelar qué artículo es mejor para ellos en cada paso.
Baja complejidad de comunicación : requiere sólo m informes, cada uno de los cuales incluye un número entre 1 y m , por lo que la complejidad total es . $\Theta (m\log {m})$

Maximización del bienestar

¿Cómo se debe seleccionar la secuencia de recolección? Bouveret y Lang ^[3] estudian esta cuestión bajo los siguientes supuestos:

Cada agente tiene una función de utilidad aditiva (esto implica que los artículos son bienes independientes ).
Los agentes pueden tener diferentes clasificaciones de los artículos, pero existe una función de puntuación común que asigna las clasificaciones a valores monetarios (por ejemplo, para cada agente, su mejor artículo vale x dólares para él, su segundo mejor artículo vale para él y dólares, etc.).
El asignador no conoce las clasificaciones de los agentes, pero sabe que todas las clasificaciones son extracciones aleatorias de una distribución de probabilidad determinada .
El objetivo del asignador es maximizar el valor esperado de alguna función de bienestar social .

Muestran secuencias de selección que maximizan el bienestar utilitario esperado (suma de utilidades) o el bienestar igualitario esperado (utilidad mínima) en diversos entornos.

Kalinowski et al ^[4] muestran que, cuando hay dos agentes con una función de puntuación de Borda , y cada clasificación es igualmente probable, la secuencia "round robin" (ABABAB...) alcanza la máxima suma de utilidades esperada. ^[2]^{: 308}

Justicia con diferentes derechos

Brams y Kaplan ^[5] estudian el problema de la asignación de ministerios entre los partidos. Hay una coalición de partidos; cada partido tiene un número diferente de escaños en el parlamento; A los partidos más grandes se les deberían asignar más ministerios o ministerios más prestigiosos. Este es un caso especial de asignación justa de artículos con diferentes derechos. Una posible solución a este problema es determinar una secuencia de selección, basada en los diferentes derechos, y dejar que cada parte elija un ministerio por turno. Esta solución se utiliza en Irlanda del Norte, Dinamarca y el Parlamento Europeo. ^[6]

Brams supone que cada agente tiene un orden estricto sobre los artículos y tiene preferencias receptivas sobre los paquetes de artículos. Esto significa que, en cada punto de la secuencia de selección, queda un único artículo que es el "mejor artículo" para el agente. Un agente se llama sincero ( veraz ) si, en cada momento, elige lo mejor. Si los agentes tienen información completa sobre las preferencias de los demás (como es común entre las partes), puede que no sea racional que elijan con sinceridad; Puede que sea mejor para ellos tomar decisiones sofisticadas ( estratégicas ). Así, la secuencia de selección induce un juego secuencial y es interesante analizar su equilibrio perfecto en subjuegos . Se prueban varios resultados:

Con dos agentes, tanto las decisiones veraces como las estratégicas conducen a asignaciones eficientes en el sentido de Pareto . Además, el juego es monótono en el siguiente sentido: un agente siempre está mejor si una o más de sus posiciones en la secuencia mejoran (por ejemplo, Alice está mejor en la secuencia ABBA que en BABA). Ambas propiedades siguen siendo válidas con tres o más agentes, siempre que tomen decisiones veraces.
Con tres o más agentes que toman decisiones estratégicas, una secuencia de selección podría conducir a asignaciones ineficientes (es decir, el equilibrio perfecto en subjuegos podría no ser eficiente en el sentido de Pareto).
Con tres o más agentes que toman decisiones estratégicas, el juego podría no ser monótono , es decir, a un agente le podría ir peor si eligiera antes en la secuencia. ^[5]^{: 210-212}
Para dos agentes, existe una modificación simple de la secuencia de selección que es un mecanismo veraz : seleccionar artículos verazmente es una estrategia dominante. Por lo tanto, existe un equilibrio perfecto en subjuegos que es óptimo de Pareto y el juego es monótono.

Determinar la secuencia de recolección

Dados los diferentes derechos de los agentes, ¿cuál sería una secuencia de selección justa? Brams ^[5]^{: 202–206} sugiere utilizar métodos divisores , similares a los utilizados para el reparto de escaños en el Congreso entre estados . Los dos métodos más utilizados son los propuestos por Daniel Webster y Thomas Jefferson . Ambos métodos comienzan de la misma manera:

Calcule el divisor : la suma de los derechos dividida por el número de artículos (por ejemplo, si la suma de todos los derechos es 201 y hay 15 artículos para compartir, entonces el divisor es 201/15).
Calcule la cuota : el número fraccionario de artículos a los que tiene derecho cada agente. Este es el derecho dividido por el divisor (por ejemplo, para un agente con un derecho de 10 de 201, la cuota es 10*15/201 ~ 0,75 artículos).

Equilibrio competitivo

Las secuencias de selección se pueden utilizar para encontrar asignaciones que satisfagan una fuerte condición de equidad y eficiencia llamada equilibrio competitivo . ^[7]

Ver también

El protocolo de asignación de artículos por turnos es un caso especial de una secuencia de selección en la que la secuencia es cíclica: 1, 2, ..., n , 1, 2, ..., n , ...

Los juegos de patio de escuela a menudo requieren la selección de "equipos". Al utilizar la selección "ABBA", el equipo "A" declarará "primera elección" y el equipo B declarará "Segunda-Dos": Lista de juegos infantiles tradicionales

Referencias

^ Steven Brams y Alan D. Taylor (1999-2000).'La solución beneficiosa para todos: garantizar una participación justa para todos' . Nueva York: WW Norton.
^ ab Sylvain Bouveret y Yann Chevaleyre y Nicolas Maudet, "Asignación justa de bienes indivisibles". Capítulo 12 en: Brandt, Felix; Conitzer, Vicente; Endriss, Ulle; Lang, Jérôme; Procaccia, Ariel D. (2016). Manual de elección social computacional. Prensa de la Universidad de Cambridge. ISBN 9781107060432.(versión gratuita en línea)
^ Un protocolo general sin obtención de información para la asignación de bienes indivisibles. doi :10.5591/978-1-57735-516-8/ijcai11-024.
^ Un procedimiento de asignación secuencial óptimo de bienestar social. AAAI-13. 2013.
^ abc Capítulo 9 en Steven J. Brams (2008). Matemáticas y democracia: diseño de mejores procedimientos de votación y división justa . Princeton, Nueva Jersey: Princeton University Press. ISBN 9780691133218.. Adaptado de Brams, Steven J.; Kaplan, Todd R. (2004). "Dividiendo lo indivisible". Revista de Política Teórica . 16 (2): 143. doi :10.1177/0951629804041118. hdl : 10036/26974 . S2CID 154854134.
^ O'Leary, Brendan; Grofman, Bernard; Elklit, Jörgen (2005). "Métodos divisores para la asignación secuencial de carteras en órganos ejecutivos multipartidistas: evidencia de Irlanda del Norte y Dinamarca". Revista Estadounidense de Ciencias Políticas . 49 : 198-211. doi :10.1111/j.0092-5853.2005.00118.x. S2CID 547519.
^ Segal-Halevi, Erel (20 de febrero de 2020). "Equilibrio competitivo para casi todas las rentas: existencia y justicia". Agentes Autónomos y Sistemas Multiagente . 34 (1): 26. arXiv : 1705.04212 . doi :10.1007/s10458-020-09444-z. ISSN 1573-7454. S2CID 254232282.