Secuencia de selección

Una secuencia de selección es un protocolo para la asignación equitativa de artículos . Supongamos que m artículos deben dividirse entre n agentes. Una forma de asignar los artículos es permitir que un agente seleccione un artículo, luego otro agente seleccione otro, 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 seleccionar un artículo.

Por ejemplo, supongamos que hay que repartir 4 artículos entre Alice y Bob . Algunas posibles secuencias de reparto son:

• AABB - Alice elige dos artículos, luego Bob elige los dos artículos restantes.
• ABAB: Alice elige un objeto, luego Bob elige otro, luego Alice de nuevo, y luego Bob otra vez. Esto es más "justo" que AABB, ya que le da a Bob más posibilidades de obtener un mejor objeto.
• ABBA - Alice elige un artículo, luego Bob elige dos artículos, y luego Alice recibe el artículo restante. Intuitivamente, esto es incluso más "justo" que ABAB, ya que, en ABAB, Bob siempre está detrás de Alice, mientras que ABBA es más equilibrado. ^{[ 1 ]}

Una secuencia de selección tiene varias ventajas como protocolo de división justa : ^{[ 2 ] : 307}

• Sencillez: a los agentes les resulta muy fácil comprender cómo funciona el protocolo y qué deben hacer en cada paso; simplemente deben elegir la mejor opción.
• Privacidad: los agentes no tienen que revelar toda su función de valoración ni su clasificación completa. Solo tienen que revelar qué artículo es el mejor para ellos en cada paso.
• Baja complejidad de comunicación : requiere solo m informes, cada uno de los cuales incluye un número entre 1 y m , de modo que la complejidad total es${\displaystyle \Theta (m\log {m})}$.

¿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 relaciona las clasificaciones con valores monetarios (por ejemplo, para cada agente, su mejor artículo vale x dólares, su segundo mejor artículo vale y dólares, etc.).
• El asignador desconoce la clasificación de los agentes, pero sabe que todas las clasificaciones son extracciones aleatorias de una distribución de probabilidad dada .
• 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 contextos.

Kalinowski et al. ^{[ 4 ]} demuestran 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 suma esperada máxima de utilidades. ^{[ 2 ] : 308}

Brams y Kaplan ^{[ 5 ]} estudian el problema de la asignación de ministerios entre los partidos. Existe una coalición de partidos; cada partido tiene un número diferente de escaños en el parlamento; los partidos más grandes deberían recibir más ministerios o ministerios más prestigiosos. Este es un caso especial de asignación equitativa de cargos con diferentes prerrogativas. Una posible solución a este problema es determinar una secuencia de selección, basada en las diferentes prerrogativas, y permitir que cada partido elija un ministerio por turnos. Esta solución se utiliza en Irlanda del Norte, Dinamarca y el Parlamento Europeo. ^{[ 6 ]}

Brams supone que cada agente tiene un orden estricto de los artículos y preferencias receptivas sobre los conjuntos 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. Se dice que un agente es sincero ( veraz ) si, en cada punto, elige su mejor artículo. Si los agentes tienen información completa sobre las preferencias de los demás (como suele ocurrir entre las partes), puede que no sea racional que elijan con sinceridad; puede que sea mejor para ellos tomar decisiones sofisticadas ( estratégicas ). Por lo tanto, la secuencia de selección induce un juego secuencial y es interesante analizar su equilibrio perfecto en subjuegos . Se demuestran varios resultados:

• Con dos agentes, tanto las decisiones veraces como las estratégicas dan lugar a asignaciones eficientes de Pareto . Además, el juego es monótono en el sentido siguiente: un agente siempre se beneficia si una o más de sus posiciones en la secuencia mejoran (por ejemplo, a Alice le conviene más la secuencia ABBA que la BABA). Ambas propiedades se mantienen 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 Pareto-eficiente).
• Con tres o más agentes que toman decisiones estratégicas, el juego podría no ser monótono , es decir, un agente podría obtener peores resultados si elige antes en la secuencia. ^{[ 5 ] : 210–212}
• Para dos agentes, existe una modificación simple de la secuencia de selección que constituye un mecanismo veraz : seleccionar elementos con veracidad es una estrategia dominante. Por lo tanto, existe un equilibrio perfecto en subjuegos que es óptimo de Pareto, y el juego es monótono.

Las secuencias de selección pueden utilizarse para encontrar asignaciones que satisfagan una condición de equidad y eficiencia estricta denominada equilibrio competitivo . ^{[ 7 ]}

• Asignación de elementos round-robin , un caso especial de una secuencia de selección en la que la secuencia es cíclica (1, 2, ..., n , 1, 2, ..., n , ...)
• Lista de juegos infantiles tradicionales que a menudo requieren la selección de equipos.