Votación de múltiples ganadores

Proceso de elección de más de un ganador en la misma elección/distrito

La votación multiganador ^[1] , la votación general o la votación por comité ^{[2] [3]} se refiere a sistemas electorales que eligen a varios candidatos a la vez. Dichos métodos pueden utilizarse para elegir parlamentos o comités .

Objetivos

Existen muchos escenarios en los que la votación con múltiples ganadores resulta útil. Se pueden clasificar en tres grandes categorías, según el objetivo principal de la elección del comité: ^[4]

1. Excelencia. En este caso, los votantes juzgan la calidad de cada candidato individualmente. El objetivo es encontrar a los mejores candidatos "objetivamente". Un ejemplo de aplicación es la preselección : seleccionar, de una lista de empleados candidatos, un pequeño grupo de finalistas, que pasarán a la etapa final de evaluación (por ejemplo, mediante una entrevista). En este caso, cada candidato es evaluado independientemente de los demás. Si dos candidatos son similares, entonces probablemente ambos serán elegidos o ambos serán rechazados.
2. Diversidad . En este caso, los candidatos elegidos deben ser lo más diferentes posible. Por ejemplo, supongamos que los candidatos son posibles lugares para construir una instalación, como un parque de bomberos. La mayoría de los ciudadanos prefieren naturalmente un parque de bomberos en el centro de la ciudad. Sin embargo, no es necesario tener dos parques de bomberos en el mismo lugar; es mejor diversificar la selección y colocar el segundo en un lugar más remoto. A diferencia del escenario de "excelencia", si dos candidatos son similares, entonces probablemente exactamente uno de ellos será elegido. Otro escenario en el que la diversidad es importante es cuando un motor de búsqueda selecciona resultados para mostrar, o cuando una aerolínea selecciona películas para proyectar durante un vuelo.
3. Proporcionalidad . En este caso, los candidatos electos deben representar , en la medida de lo posible, la diversidad de opiniones de la población de votantes, medida por los votos emitidos. Este es un objetivo común en las elecciones parlamentarias ; véase representación proporcional .

Familias de métodos

Un desafío importante en el estudio de la votación con múltiples ganadores es encontrar adaptaciones razonables de los conceptos de la votación con un solo ganador. Estas pueden clasificarse según el tipo de votación: votación de aprobación o votación por orden de preferencia .

Algunos sistemas electorales eligen a múltiples miembros mediante concursos entre candidatos individuales. Estos sistemas son algunas variantes del voto múltiple no transferible y del voto único transferible .

En otros sistemas, los candidatos se agrupan en comités (listas) y los votantes emiten sus votos para los comités (o listas).

Votación de aprobación para comités

La votación aprobatoria es un método común en las elecciones con un solo ganador y, a veces, en las elecciones con varios ganadores. En las elecciones con un solo ganador, cada votante marca al candidato que aprueba y el candidato con más votos gana.

En el sistema de votación con múltiples ganadores, existen muchas maneras de decidir qué candidato debe ser elegido. En algunas, cada votante clasifica a los candidatos; en otras, emite X votos. Asimismo, cada votante puede emitir un solo voto o varios.

Ya en 1895, Thiele sugirió una familia de reglas basadas en pesos llamadas reglas de votación de Thiele . ^{[2] [5]} Cada regla de la familia está definida por una secuencia de k pesos débilmente positivos, w ₁ ,..., w _k (donde k es el tamaño del comité). Cada votante asigna, a cada comité que contiene p candidatos aprobados por el votante, una puntuación igual a w ₁ +...+ w _p . Se elige el comité con la puntuación total más alta. Algunas reglas de votación comunes en la familia de Thiele son:

• Voto múltiple no transferible (VMT): el vector de peso es (1,1,...,1). También se denomina votación de aprobación por pluralidad general .
• Aprobación-Chamberlin-Courant (ACC): el vector de pesos es (1,0,...,0). Es decir, cada votante otorga 1 punto a un comité, si y sólo si este contiene a uno de sus candidatos aprobados.
• Votación aprobatoria proporcional (PAV): el vector de pesos es la progresión armónica (1, 1/2, 1/3, ..., 1/ k ).

Existen reglas basadas en otros principios, como la votación aprobatoria minimax ^[6] y sus generalizaciones, ^[7] así como las reglas de votación de Phragmen ^[8] y el método de partes iguales . ^{[9] [10]}

La complejidad de determinar los ganadores varía: los ganadores de MNTV se pueden encontrar en tiempo polinomial, mientras que Chamberlin-Courant ^[11] y PAV son ambos NP-duros.

Reglas de puntuación posicional para comités

Las reglas de puntuación por posición son comunes en las votaciones con un solo ganador basadas en el orden de preferencia. Cada votante clasifica a los candidatos del mejor al peor, una función preestablecida asigna una puntuación a cada candidato en función de su posición y el candidato con la puntuación total más alta es elegido.

En las votaciones con múltiples ganadores que se realizan con estos sistemas, es necesario asignar puntajes a los comités en lugar de a los candidatos individuales. Hay varias formas de hacerlo, por ejemplo: ^[1]

• Voto único intransferible : cada votante otorga 1 punto a un comité, si este contiene a su candidato preferido. En otras palabras: cada votante vota por un solo candidato en una contienda que elige a múltiples ganadores, y los k candidatos con el mayor número de votos son elegidos. Esto generaliza el voto por mayoría simple . Puede calcularse en tiempo polinomial.

• Voto múltiple intransferible (también llamado voto en bloque ): cada votante otorga 1 punto a un comité por cada escaño vacante en su top k . En otras palabras: cada votante vota por k candidatos en los que hay k escaños vacantes y los k candidatos con mayor número de votos son elegidos.

• k -Borda: cada votante entrega a cada miembro del comité su puntaje Borda . Cada votante clasifica a los candidatos y las clasificaciones se puntúan en conjunto. Los k candidatos con el puntaje Borda total más alto son elegidos.
• Borda-Chamberlin-Courant (BCC): cada votante entrega a cada comité el recuento Borda de su candidato preferido en el comité. ^[12] Calcular el ganador con BCC es NP-hard. ^[11]

Comités Condorcet

En la votación con un solo ganador, un ganador de Condorcet es un candidato que gana en cada elección directa contra cada uno de los otros candidatos. Un método de Condorcet es un método que selecciona un ganador de Condorcet cuando existe. Hay varias formas de adaptar el criterio de Condorcet a la votación con múltiples ganadores:

• La primera adaptación fue de Peter Fishburn : ^{[13] [14]} un comité es un comité Condorcet si es preferido, por una mayoría de votantes, a cualquier otro comité posible. Fishburn asumió que los votantes clasifican los comités por el número de miembros en su conjunto de aprobación (es decir, tienen preferencias dicotómicas ). Trabajos posteriores asumieron que los votantes clasifican los comités por otros criterios, como por su recuento de Borda . Es coNP-completo verificar si un comité satisface este criterio, y coNP-difícil decidir si existe un comité Condorcet. ^[15]
• Otra adaptación fue la de Gehrlein ^[16] y Ratliff: ^[17] un comité es un comité Condorcet si cada candidato que lo integra es preferido, por una mayoría de votantes, a cada candidato que no lo integra. Una regla de votación con múltiples ganadores a veces se denomina estable si selecciona un conjunto Condorcet siempre que exista. ^[18] Algunas reglas estables son: ^[19]
  • Método de Copeland de múltiples ganadores : cada comité se califica por el "número de derrotas externas": el número de pares ( c , d ) donde c está en el comité, d no está y c es preferido a d por la mayoría de los votantes.
  • Método Condorcet Minimax Multiwinner : cada comité se puntúa según el "tamaño de la oposición externa": el mínimo, sobre todos los pares ( c , d ), del número de votantes que prefieren c .
  • Variantes de múltiples ganadores de algunas otras reglas de Condorcet. ^[20]
• Una tercera adaptación fue realizada por Elkind , Lang y Saffidine: ^[21] un conjunto ganador de Condorcet es un conjunto en el que, para cada miembro d que no está en el conjunto, algún miembro c en el conjunto es preferido a d por una mayoría. Con base en esta definición, presentan una variante multiganador diferente del método Minimax Condorcet .

Elecciones de excelencia

Excelencia significa que el comité debe contener a los "mejores" candidatos. Las reglas de votación basadas en la excelencia a menudo se denominan reglas de selección. ^[18] A menudo se utilizan como un primer paso en la selección de un único mejor candidato, es decir, un método para crear una lista corta . Una propiedad básica que debe cumplir una regla de este tipo es la monotonía del comité (también llamada monotonía de la casa , una variante de la monotonía de los recursos ): si algunos k candidatos son elegidos por una regla, y luego el tamaño del comité aumenta a k +1 y la regla se vuelve a aplicar, entonces los primeros k candidatos aún deberían ser elegidos. Algunas familias de reglas monótonas del comité son:

• Reglas secuenciales: ^[18] Utilizando cualquier regla de votación con un solo ganador, elija un solo candidato y agréguelo al comité. Repita el proceso k veces.
• Reglas de los k mejores : ^[1] utilizando cualquier regla de puntuación, asigne una puntuación a cada candidato. Elija los k candidatos con las puntuaciones más altas.

La propiedad de monotonía del comité es incompatible con la propiedad de estabilidad (una adaptación particular del criterio de Condorcet): existe un único perfil de votación que admite un único conjunto Condorcet de tamaño 2, y un único conjunto Condorcet de tamaño 3, y son disjuntos (el conjunto de tamaño 2 no está contenido en el conjunto de tamaño 3). ^[18]

Por otra parte, existe una familia de reglas de puntuación posicional (las reglas de puntuación posicional separables ) que son monótonas para el comité. Estas reglas también se pueden calcular en tiempo polinómico (si sus funciones de puntuación de ganador único subyacentes lo son). ^[1] Por ejemplo, k -Borda es separable, mientras que el voto múltiple no transferible no lo es.

Elecciones de diversidad

La diversidad significa que el comité debe estar compuesto por los candidatos mejor valorados por la mayor cantidad posible de votantes. Formalmente, los siguientes axiomas son razonables para las solicitudes centradas en la diversidad:

• Criterio de límite estrecho: ^[1] si existe un comité de tamaño k que contiene al candidato con mayor puntuación de cada votante, entonces éste debería ser elegido.
• Monotonía de los miembros superiores: ^[22] si se elige un comité y algún votante cambia el rango de su ganador preferido, entonces se debería elegir el mismo comité.

Elecciones proporcionales

Proporcionalidad significa que cada grupo cohesionado de votantes (es decir: un grupo de votantes con preferencias similares) debe estar representado por un número de ganadores proporcional a su tamaño. Formalmente, si el comité es de tamaño k , hay n votantes y algunos L * n / k votantes clasifican a los mismos L candidatos en la parte superior (o aprueban a los mismos L candidatos), entonces estos L candidatos deben ser elegidos. Este principio es fácil de implementar cuando los votantes votan por partidos (en sistemas de lista de partidos ), pero también se puede adaptar a la votación de aprobación o votación por orden de preferencia; véase representación justificada y proporcionalidad para coaliciones sólidas .

Véase también

• Presupuesto participativo : puede verse como una generalización de la votación con múltiples ganadores, donde los candidatos tienen diferentes costos.

Referencias

1. Elkind, Edith; Faliszewski, Piotr; Skowron, Piotr; Slinko, Arkadii (1 de marzo de 2017). "Propiedades de las reglas de votación de múltiples ganadores". Elección social y bienestar . 48 (3): 599–632. doi :10.1007/s00355-017-1026-z. ISSN  1432-217X. PMC  7089675 . PMID  32226187.
2. Aziz, Haris; Brill, Markus; Conitzer, Vincent; Elkind, Edith; Freeman, Rupert; Walsh, Toby (2017). "Representación justificada en la votación de comités basada en la aprobación". Elección social y bienestar . 48 (2): 461–485. arXiv : 1407.8269 . doi :10.1007/s00355-016-1019-3. S2CID  8564247.
3. Bock, Hans-Hermann; Day, William HE; McMorris, FR (1998-05-01). "Reglas de consenso para las elecciones de comités". Ciencias Sociales Matemáticas . 35 (3): 219–232. doi :10.1016/S0165-4896(97)00033-4. ISSN  0165-4896.
4. Piotr Faliszewski, Piotr Skowron, Arkadii Slinko, Nimrod Talmon (26 de octubre de 2017). "Votación de múltiples ganadores: un nuevo desafío para la teoría de la elección social". En Endriss, Ulle (ed.). Tendencias en la elección social computacional . Lulu.com. ISBN 978-1-326-91209-3.{{cite book}}: CS1 maint: multiple names: authors list (link)
5. Sánchez-Fernández, Luis; Elkind, Edith; Lackner, Martín; Fernández, Norberto; Fisteo, Jesús; Val, Pablo Basanta; Skowron, Piotr (10 de febrero de 2017). “Representación Proporcional Justificada”. Actas de la Conferencia AAAI sobre Inteligencia Artificial . 31 (1). doi : 10.1609/aaai.v31i1.10611 . hdl : 10016/26166 . ISSN  2374-3468. S2CID  17538641.
6. Brams, Steven J.; Kilgour, D. Marc; Sanver, M. Remzi (1 de septiembre de 2007). "Un procedimiento minimax para la elección de comités". Public Choice . 132 (3): 401–420. doi :10.1007/s11127-007-9165-x. ISSN  1573-7101. S2CID  46632580.
7. Amanatidis, Georgios; Barrot, Nathanaël; Lang, Jérôme; Markakis, Evangelos; Ries, Bernard (4 de mayo de 2015). "Referendos múltiples y elecciones con múltiples ganadores utilizando distancias de Hamming: complejidad y manipulación". Actas de la Conferencia internacional de 2015 sobre agentes autónomos y sistemas multiagente . AAMAS '15. Estambul, Turquía: Fundación Internacional para Agentes Autónomos y Sistemas Multiagente: 715–723. ISBN 978-1-4503-3413-6.
8. Brill, Markus; Freeman, Rupert; Janson, Svante; Lackner, Martin (10 de febrero de 2017). "Métodos de votación y representación justificada de Phragmén". Actas de la Conferencia AAAI sobre Inteligencia Artificial . 31 (1). arXiv : 2102.12305 . doi : 10.1609/aaai.v31i1.10598 . ISSN  2374-3468. S2CID  2290202.
9. Peters, Dominik; Skowron, Piotr (2020). "Proporcionalidad y los límites del bienestarismo". Actas de la 21.ª Conferencia de la ACM sobre economía y computación . EC'20. págs. 793–794. arXiv : 1911.11747 . doi :10.1145/3391403.3399465. ISBN . 9781450379755.S2CID208291203  .​
10. Pierczyński, Grzegorz; Peters, Dominik; Skowron, Piotr (2021). "Presupuesto participativo proporcional con utilidades aditivas". Actas de la Conferencia de 2021 sobre sistemas de procesamiento de información neuronal . NeurIPS'21. arXiv : 2008.13276 .
11. Procaccia, Ariel D.; Rosenschein, Jeffrey S.; Zohar, Aviv (19 de abril de 2007). "Sobre la complejidad de lograr una representación proporcional". Elección social y bienestar . 30 (3): 353–362. doi :10.1007/s00355-007-0235-2. S2CID  18126521.
12. Chamberlin, John R.; Courant, Paul N. (1983). "Deliberaciones representativas y decisiones representativas: representación proporcional y la regla de Borda". The American Political Science Review . 77 (3): 718–733. doi :10.2307/1957270. ISSN  0003-0554. JSTOR  1957270. S2CID  147162169.
13. Fishburn, Peter C. (1 de octubre de 1981). "Comités mayoritarios". Revista de teoría económica . 25 (2): 255–268. doi :10.1016/0022-0531(81)90005-3. ISSN  0022-0531.
14. Fishburn, Peter C. (1981-12-01). "Análisis de sistemas de votación simples para comités electorales". Revista SIAM de Matemática Aplicada . 41 (3): 499–502. doi :10.1137/0141041. ISSN  0036-1399.
15. Darmann, Andreas (1 de noviembre de 2013). "¿Qué tan difícil es determinar cuál es un comité Condorcet?". Ciencias Sociales Matemáticas . 66 (3): 282–292. doi :10.1016/j.mathsocsci.2013.06.004. ISSN  0165-4896. PMC 4376023 . PMID  25843993. 
16. Gehrlein, William V. (1985-12-01). "El criterio de Condorcet y la selección del comité". Ciencias Sociales Matemáticas . 10 (3): 199–209. doi :10.1016/0165-4896(85)90043-5. ISSN  0165-4896.
17. Ratliff, Thomas C. (1 de diciembre de 2003). "Algunas inconsistencias alarmantes en la elección de comités". Social Choice and Welfare . 21 (3): 433–454. doi :10.1007/s00355-003-0209-y. ISSN  1432-217X. S2CID  36949675.
18. Barberà, Salvador; Coelho, Danilo (2008). "Cómo elegir una lista no controvertida con k nombres". Elección social y bienestar . 31 (1): 79–96. doi :10.1007/s00355-007-0268-6. ISSN  0176-1714. JSTOR  41107910. S2CID  16974573.
19. Coelho, Danilo; Barberá, Salvador (2005). Comprender, evaluar y seleccionar reglas de votación mediante juegos y axiomas. Bellaterra: Universitat Autònoma de Barcelona. ISBN 978-84-689-0967-7.
20. Kamwa, Eric (1 de mayo de 2017). "Sobre reglas estables para la selección de comités". Revista de Economía Matemática . 70 : 36–44. doi :10.1016/j.jmateco.2017.01.008. ISSN  0304-4068. S2CID  125508393.
21. Elkind, Edith; Lang, Jérôme; Saffidine, Abdallah (2015). "Conjuntos ganadores de Condorcet". Elección social y bienestar . 44 (3): 493–517. doi :10.1007/s00355-014-0853-4. ISSN  0176-1714. JSTOR  43662603. S2CID  31128109.
22. Faliszewski, Piotr; Skowron, Piotr; Slinko, Arkadii; Talmon, Nimrod (9 de julio de 2016). "Reglas de puntuación del comité: clasificación axiomática y jerarquía". Actas de la 25.ª Conferencia conjunta internacional sobre inteligencia artificial . IJCAI'16. Nueva York, Nueva York, EE. UU.: AAAI Press: 250–256. ISBN 978-1-57735-770-4.