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 de múltiples ganadores , ^[1] también llamada votación de comité ^[2] o elecciones de comité , ^[3] es un sistema electoral en el que se eligen múltiples candidatos. El número de candidatos elegidos suele fijarse de antemano. Por ejemplo, puede ser el número de escaños en el parlamento de un país o el número requerido de miembros en un comité .

Hay muchos escenarios en los que resulta útil la votación de varios ganadores. Se pueden clasificar en términos generales en tres clases, según el objetivo principal de la elección del comité: ^[4]

1. Excelencia . Aquí, cada votante es un experto, y cada voto expresa su opinión sobre qué candidato/s es "mejor" para una determinada tarea. El objetivo es encontrar los "mejores" candidatos. 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). Aquí, cada candidato es evaluado independientemente de los demás candidatos. Si dos candidatos son similares, entonces probablemente ambos serán elegidos (si ambos son buenos) o ambos serán rechazados (si ambos son malos).
2. Diversidad . En este caso, los candidatos elegidos deberían ser lo más diferentes posible. Por ejemplo, supongamos que los candidatos son posibles ubicaciones para construir una instalación, como una estación de bomberos. Naturalmente, la mayoría de los ciudadanos prefieren 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 la segunda estación en un lugar más remoto. A diferencia del escenario de "excelencia", si dos candidatos son similares, 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 mostrarlos, o cuando una aerolínea selecciona películas para proyectarlas durante un vuelo.
3. Proporcionalidad . Aquí, los candidatos electos deben representar de manera científicamente equilibrada, en la medida de lo posible, la opinión diversa de la población de votantes, medida por los votos que emiten. Este es un objetivo común en las elecciones parlamentarias ; ver representación proporcional .

Conceptos básicos

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. Estos se pueden clasificar según el tipo de votación: votación de aprobación versus votación clasificada .

Algunos sistemas electorales eligen a varios miembros mediante competencia entre candidatos individuales. Dichos sistemas son algunas variaciones del voto múltiple intransferible y del voto único transferible .

En otros sistemas, los candidatos se agrupan en comités (listas) y los votantes emiten sus votos por los comités (o listas). Estos sistemas basados ​​en comités se describen aquí:

Votación de aprobación de las comisiones.

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

Con la votación de múltiples ganadores, hay muchas maneras de decidir qué candidato debe ser elegido. En algunos, cada votante clasifica a los candidatos; en otros emitieron X votos. Asimismo, cada elector podrá emitir votos únicos o múltiples.

Ya en 1895, Thiele sugirió una familia de reglas basadas en el peso llamadas reglas de votación de Thiele . ^{[2] [5]} Cada regla de la familia se define 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 contenga 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 intransferible (MNTV): el vector de ponderación es (1,1,...,1). También se denomina votación de aprobación por pluralidad general .
• Aprobación-Chamberlin-Courant (ACC): el vector de peso es (1,0,...,0). Es decir, cada votante da 1 punto a un comité, si éste contiene uno de sus candidatos aprobados.
• Votación de aprobación proporcional (PAV): el vector de peso es la progresión armónica (1, 1/2, 1/3, ...., 1/ k ).

Existen reglas basadas en otros principios, como la votación de aprobación minimax ^[6] y sus generalizaciones, ^[7] reglas de votación de Phragmen . ^[8] y el Método de Partes Iguales . ^{[9] [10]}

Calcular el ganador con SNTV se puede hacer en tiempo polinómico, pero con ACC es NP-duro, ^[11] al igual que con PAV.

Reglas de puntuación posicional para comités

Las reglas de puntuación posicional son comunes en la votación de un solo ganador basada en rangos. Cada votante clasifica a los candidatos de mejor a peor, una función preespecificada asigna una puntuación a cada candidato en función de su rango y se elige al candidato con la puntuación total más alta.

In multiwinner voting held using these systems, we need to assign scores to committees rather than to individual candidates. There are various ways to do this, for example:^[1]

• Single non-transferable vote: each voter gives 1 point to a committee, if it contains his most preferred candidate. In other words: each voter votes for a single candidate in a contest that elects multiwinners, and the k candidates with the largest number of votes are elected. This generalizes First-past-the-post voting. It can be computed in polynomial time.

• Multiple non-transferable vote (also called bloc voting): each voter gives 1 point to a committee for each open seat in his top k. In other words: each voter votes for k candidates where k seats are open, and the k candidates with the largest number of votes are elected.

• k-Borda: each voter gives, to each committee member, his Borda count. Each voter ranks the candidates and the rankings are scored together. The k candidates with the highest total Borda score are elected.
• Borda-Chamberlin-Courant (BCC): each voter gives, to each committee, the Borda count of his most preferred candidate in the committee.^[12] Computing the winner with BCC is NP-hard.^[11]

Condorcet committees

In single-winner voting, a Condorcet winner is a candidate who wins in every head-to-head election against each of the other candidates. A Condorcet method is a method that selects a Condorcet winner whenever it exists. There are several ways to adapt Condorcet's criterion to multiwinner voting:

• The first adaptation was by Peter Fishburn:^[13][14] a committee is a Condorcet committee iff it is preferred, by a majority of voters, to any other possible committee. Fishburn assumed that the voters rank committees by the number of members in their approval set (i.e., they have dichotomous preferences). Later works assumed that the voters rank committees by other criteria, such as by their Borda count. It is coNP-complete to check if a committee satisfies this criterion, and coNP-hard to decide if there exist a Condorcet committee.^[15]
• Otra adaptación fue la de Gehrlein ^[16] y Ratliff: ^[17] un comité es un conjunto de Condorcet si cada candidato en él es preferido, por una mayoría de votantes, a cada candidato fuera de él. Una regla de votación con múltiples ganadores a veces se denomina estable si selecciona un conjunto de Condorcet siempre que exista. ^[18] Algunas reglas estables son: ^[19]
  • Método de Copeland de múltiples ganadores : cada comité se califica según el "número de derrotas externas": el número de pares ( c , d ) donde c está en el comité, d no y c es preferido a d por la mayoría de los votantes.
  • Método Minimax Condorcet de ganadores múltiples : cada comité se califica 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 del conjunto es preferido a d por una mayoría. A partir de esta definición, presentan una variante diferente del método Minimax Condorcet, multiganador .

Otros criterios

Calcular comités eficientes en el sentido de Pareto es NP-difícil en general. ^[22]

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 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 ser satisfecha por tal regla es la monotonicidad del comité (también llamada monotonicidad de la casa , una variante de la monotonicidad de los recursos ): si algunos k candidatos son elegidos por una regla, entonces 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 de comité son:

• Reglas secuenciales: ^[18] utilizando cualquier regla de votación de un solo ganador, elija un solo candidato y agréguelo al comité. Repetir el proceso k veces.
• Reglas Best- k : ^[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 monotonicidad 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 conjunto Condorcet único de tamaño 2 y un conjunto Condorcet único de tamaño 3, y son disjuntos (el conjunto de talla 2 no está contenido en el conjunto de talla 3). ^[18]

Por otro lado, existe una familia de reglas de puntuación posicional (las reglas de puntuación posicional separables ) que son monótonas en el comité. Estas reglas también son computables en tiempo polinómico (si sus funciones subyacentes de puntuación de un solo ganador lo son). ^[1] Por ejemplo, k -Borda es separable mientras que el voto múltiple intransferible no lo es.

Elecciones de diversidad

Diversidad significa que el comité debe contener a los candidatos mejor clasificados de la mayor cantidad de votantes posible. Formalmente, los siguientes axiomas son razonables para aplicaciones centradas en la diversidad:

• Criterio de cima estrecha: ^[1] si existe un comité de tamaño k que contenga al candidato mejor clasificado de cada votante, entonces debería ser elegido.
• Monotonicidad de los principales miembros: ^[23] si se elige un comité y algún votante sube el rango de su ganador preferido, entonces se debe elegir el mismo comité.

Elecciones proporcionales

Proporcionalidad significa que cada grupo cohesivo 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 cima (o aprueban los mismos L candidatos), entonces estos L candidatos deberían ser elegidos. Este principio es fácil de implementar cuando los votantes votan por partidos (en sistemas de listas de partidos ), pero también puede adaptarse a la votación de aprobación o a la votación por orden de preferencia; ver representación justificada .

Otras lecturas

• Encontrar un conjunto colectivo de elementos: de la multirrepresentación proporcional a la recomendación grupal. ^[24]
• Elección social presupuestada: del consenso a la toma de decisiones personalizada. ^[25]
• Lograr una representación plenamente proporcional: resultados de aproximabilidad. ^[26]

Ver también

• Presupuesto participativo : puede verse como una extensión de la votación con múltiples ganadores en la que cada candidato tiene un "costo". En la votación de múltiples ganadores, el precio de cada candidato es 1 y el presupuesto es k .

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; Genial, Markus; Conitzer, Vicente; Elkind, Edith; Freeman, Ruperto; Walsh, Toby (2017). "Representación justificada en la votación del comité 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; Día, William HE; McMorris, FR (1 de mayo de 1998). "Normas 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}}: Mantenimiento CS1: varios nombres: lista de autores ( enlace )
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 los comités electorales". Elección pública . 132 (3): 401–420. doi :10.1007/s11127-007-9165-x. ISSN  1573-7101. S2CID  46632580.
7. Amanatidis, Georgios; Barrot, Natanaël; Lang, Jérôme; Markakis, Evangelos; Ries, Bernard (4 de mayo de 2015). "Múltiples referendos y elecciones con múltiples ganadores utilizando distancias de Hamming: complejidad y manipulabilidad". 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 Multiagentes: 715–723. ISBN 978-1-4503-3413-6.
8. Genial, Markus; Freeman, Ruperto; Janson, Svante; Lackner, Martín (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. Pedro, Dominik; Skowron, Piotr (2020). "Proporcionalidad y los límites del bienestarismo". Actas de la 21ª Conferencia ACM sobre Economía y Computación . CE'20. págs. 793–794. arXiv : 1911.11747 . doi :10.1145/3391403.3399465. ISBN 9781450379755. S2CID  208291203.
10. Pierczyński, Grzegorz; Peters, Dominik; Skowron, Piotr (2020). "Presupuesto Participativo Proporcional con Servicios Aditivos". 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 la 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 regla de Borda". La revista estadounidense de ciencias políticas . 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. (1 de diciembre de 1981). "Un 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 saber 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. (1 de diciembre de 1985). "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 sorprendentes al elegir comités". Elección social y bienestar . 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 los comités de selección". 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). "Sets 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. Aziz, Haris; Monnot, Jérôme (17 de febrero de 2020). "Cálculo y prueba de comités óptimos de Pareto". Agentes Autónomos y Sistemas Multiagente . 34 (1): 24. arXiv : 1803.06644 . doi :10.1007/s10458-020-09445-y. ISSN  1573-7454. S2CID  3955482.
23. Faliszewski, Piotr; Skowron, Piotr; Slinko, Arkadii; Talmón, Nimrod (9 de julio de 2016). "Reglas de puntuación del comité: clasificación axiomática y jerarquía". Actas de la Vigésima Quinta Conferencia Internacional Conjunta sobre Inteligencia Artificial . IJCAI'16. Nueva York, Nueva York, Estados Unidos: AAAI Press: 250–256. ISBN 978-1-57735-770-4.
24. Skowron, Piotr; Faliszewski, Piotr; Lang, Jerome (1 de enero de 2015). Encontrar un conjunto colectivo de elementos: de la multirrepresentación proporcional a la recomendación grupal. AAAI'15. vol. 1402, págs. 2131-2137. arXiv : 1402.3044 . Código Bib : 2014arXiv1402.3044S. ISBN 978-0262511292. {{cite book}}: |journal=ignorado ( ayuda )
25. Lu, Tyler; Boutilier, Craig (1 de enero de 2011). Elección social presupuestada: del consenso a la toma de decisiones personalizada . IJCAI'11. págs. 280–286. doi :10.5591/978-1-57735-516-8/IJCAI11-057. ISBN 9781577355137. {{cite book}}: |journal=ignorado ( ayuda )
26. Skowron, Piotr; Faliszewski, Piotr; Slinko, Arkadii (1 de mayo de 2015). "Lograr una representación totalmente proporcional: resultados de proximidad". Inteligencia artificial . 222 : 67-103. arXiv : 1312.4026 . doi :10.1016/j.artint.2015.01.003. S2CID  467056.