Una secuencia de selección es un protocolo para la asignación de artículos justos . Suponga que deben dividirse m elementos 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 recoger un artículo.
Como ejemplo, suponga que se deben dividir 4 elementos entre Alice y Bob. Algunas secuencias de selección posibles son:
- AABB: Alice elige dos elementos, luego Bob elige los dos elementos restantes.
- ABAB: Alice elige un artículo, luego Bob elige un artículo, luego Alice nuevamente, luego Bob nuevamente. Esto es más "justo" que AABB, ya que le da a Bob más oportunidades de obtener un artículo mejor.
- ABBA: Alice elige un artículo, luego Bob elige dos artículos, 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 es 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 comprender 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 o incluso su ranking completo. Solo tienen que revelar qué elemento es el mejor para ellos en cada paso.
- Baja complejidad de la comunicación : solo requiere m informes, cada uno de los cuales incluye un número entre 1 y m , por lo que la complejidad total es.
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 en los elementos, pero hay una función de puntuación común que asigna las clasificaciones a los valores monetarios (por ejemplo, para cada agente, su mejor artículo vale para él x dólares, 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 al azar 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 varios 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 los ministerios del gabinete 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 de artículos justos 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 asume que cada agente tiene un orden estricto de los artículos y tiene preferencias de respuesta en los paquetes de artículos. Esto significa que, en cada punto de la secuencia de selección, hay un solo artículo restante que es el "mejor artículo" para el agente. Un agente se llama 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 es común entre las partes), puede que no sea racional que elijan con sinceridad; puede ser 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, las opciones tanto verdaderas como 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 se mejoran una o más de sus posiciones en la secuencia (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 Pareto-eficiente).
- Con tres o más agentes que toman decisiones estratégicas, el juego puede no ser monótono , es decir, un agente podría hacerlo peor eligiendo antes en la secuencia. [5] : 210–212
- Para dos agentes, existe una simple modificación de la secuencia de selección, que es un mecanismo veraz : la selección de los elementos de manera veraz es una estrategia dominante. Por lo tanto, existe un equilibrio perfecto en subjuegos que es el óptimo de Pareto y el juego es monótono.
Determinación de 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 de división , 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:
- 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 denominada 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 en el patio de la escuela a menudo necesitan seleccionar "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 de ganar-ganar: Garantizar acciones equitativas para todos . Nueva York: WW Norton.
- ^ a b 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 . Prensa de la Universidad de Cambridge. ISBN 9781107060432.( versión gratuita en línea )
- ^ Un protocolo general libre de elicitació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.
- ^ a b c 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 .
- ^ O'Leary, Brendan; Grofman, Bernard; Elklit, Jorgen (2005). "Métodos de divisor para la asignación secuencial de cartera en órganos ejecutivos multipartitos: 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 .
- ^ Segal-Halevi, Erel (20 de febrero de 2020). "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 .