Secuencia de selección

Una secuencia de selección es un protocolo para la asignación justa de artículos . Supongamos que se deben dividir m artículos 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.

Por ejemplo, supongamos que hay que dividir 4 artículos entre Alicia y Roberto. Algunas posibles secuencias de selección son:

• AABB - Alice elige dos artículos, luego Bob elige los dos artículos restantes.
• ABAB: Alice elige un objeto, luego Bob elige otro objeto, luego Alice vuelve a elegir otro objeto y luego Bob vuelve a elegir otro. Esto es más "justo" que AABB, ya que le da a Bob más posibilidades de obtener un objeto mejor.
• ABBA: Alice elige un objeto, luego Bob elige dos y luego Alice recibe el objeto restante. Esto es intuitivamente aún más "justo" que ABAB, ya que, en ABAB, Bob siempre está detrás de Alice, mientras que ABBA es más equilibrado. ^[1]

Ventajas

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

• Simplicidad: es muy fácil para los agentes comprender cómo funciona el protocolo y qué deben hacer en cada paso: simplemente elegir el mejor elemento.
• Privacidad: los agentes no tienen por qué revelar toda su función de valoración ni siquiera toda su clasificación. Solo tienen que revelar qué artículo es el 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 . ${\displaystyle \Theta (m\log {m})}$

Maximización del bienestar

¿Cómo se debe seleccionar la secuencia de selecció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 en los artículos, pero hay 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, su segundo mejor artículo vale 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 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 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 suma de utilidades máxima esperada. ^{[2] : 308}

Equidad con diferentes derechos

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; a los partidos más grandes se les deben asignar más ministerios o ministerios más prestigiosos. Este es un caso especial de asignación justa de ítems 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 partido 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 de los elementos y tiene preferencias receptivas sobre paquetes de elementos. Esto significa que, en cada punto de la secuencia de selección, hay un único elemento restante que es el "mejor elemento" para el agente. Se dice que un agente es sincero ( veraz ) si, en cada punto, elige su mejor elemento. 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 verazmente; puede que sea mejor para ellos hacer elecciones 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 elecciones veraces como las estratégicas conducen a asignaciones Pareto-eficientes . Además, el juego es monótono en el sentido siguiente: un agente siempre está en mejor situación si una o más de sus posiciones en la secuencia mejoran (por ejemplo, Alice está en mejor situación en la secuencia ABBA que en BABA). Ambas propiedades siguen siendo ciertas 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 llevar a asignaciones ineficientes (es decir, el equilibrio perfecto en subjuegos podría no ser eficiente en términos de Pareto).
• 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 tener un peor desempeño si elige 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 : la selección veraz de los elementos es una estrategia dominante. Por lo tanto, existe un equilibrio perfecto en subjuegos que es óptimo en el sentido de Pareto y el juego es monótono.

Determinación de la secuencia de selección

Teniendo en cuenta 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 la distribución de escaños en el Congreso entre los 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:

• Calcular 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).
• Calcular la cuota : la cantidad fraccionaria de artículos a los que tiene derecho cada agente. Esta es la cantidad de artículos a los que tiene derecho dividida por el divisor (por ejemplo, para un agente con una cantidad de artículos a los que tiene 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 condición fuerte de equidad y eficiencia llamada equilibrio competitivo . ^[7]

Véase 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 , ...

En los juegos de patio de la escuela, a menudo es necesario seleccionar "equipos". Cuando se utiliza la selección "ABBA", el equipo "A" declarará "primera elección" y el equipo B declarará "segunda elección": Lista de juegos infantiles tradicionales

Referencias

1. Steven Brams y Alan D. Taylor (1999-2000).'La solución en la que todos ganan: garantizar una distribución justa de los beneficios para todos' . Nueva York: WW Norton.
2. Sylvain Bouveret y Yann Chevaleyre y Nicolas Maudet, "Asignación justa de bienes indivisibles". Capítulo 12 en: Brandt, Felix; Conitzer, Vincent; Endriss, Ulle; Lang, Jérôme; Procaccia, Ariel D. (2016). Manual de elección social computacional. Cambridge University Press. ISBN 9781107060432.(versión gratuita en línea)
3. Un protocolo general libre de obtención de información para la asignación de bienes indivisibles. doi :10.5591/978-1-57735-516-8/ijcai11-024.
4. Un procedimiento de asignación secuencial óptima del bienestar social. AAAI-13. 2013.
5. Capítulo 9 en Steven J. Brams (2008). Matemáticas y democracia: diseño de mejores procedimientos de votación y de división justa . Princeton, NJ: 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.
6. O'Leary, Brendan; Grofman, Bernard; Elklit, Jorgen (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.
7. Segal-Halevi, Erel (2020-02-20). "Equilibrio competitivo para casi todos los ingresos: existencia y equidad". Agentes autónomos y sistemas multiagente . 34 (1): 26. arXiv : 1705.04212 . doi :10.1007/s10458-020-09444-z. ISSN  1573-7454. S2CID  254232282.