Elección social computacional
De Wikipedia, la enciclopedia libre
Saltar a navegación Saltar a búsqueda

La elección social computacional es un campo en la intersección de la teoría de la elección social , la informática teórica y el análisis de sistemas de múltiples agentes . [1] Consiste en el análisis de problemas derivados de la agregación de preferencias de un grupo de agentes desde una perspectiva computacional. En particular, la elección social computacional se ocupa del cálculo eficiente de los resultados de las reglas de votación , de la complejidad computacional de varias formas de manipulación y de las cuestiones que surgen del problema de representar y suscitar preferencias en entornos combinatorios.

Determinación del ganador

La utilidad de un sistema de votación en particular puede verse seriamente limitada si se necesita mucho tiempo para calcular el ganador de una elección. Por lo tanto, es importante diseñar algoritmos rápidos que puedan evaluar una regla de votación cuando se reciben boletas como entrada. Como es común en la teoría de la complejidad computacional , se cree que un algoritmo es eficiente si requiere tiempo polinomial . Muchas reglas de votación populares se pueden evaluar en tiempo polinomial de una manera sencilla (es decir, contando), como el conteo de Borda , la votación de aprobación o la regla de pluralidad . Para reglas como el método Schulze o pares clasificados, se pueden usar algoritmos más sofisticados para mostrar el tiempo de ejecución polinomial. [2] [3] Ciertos sistemas de votación, sin embargo, son computacionalmente difíciles de evaluar. [4] En particular, la determinación ganador para el método Kemeny-Young , el método de Dodgson , y método de Young son todos los problemas NP-duros. [4] [5] [6] [7] Esto ha llevado al desarrollo de algoritmos de aproximación y algoritmos manejables de parámetros fijos para mejorar el cálculo teórico de tales problemas. [8] [9] [10]

Dureza de la manipulación

Según el teorema de Gibbard-Satterthwaite , todas las reglas de votación no triviales pueden manipularse en el sentido de que los votantes a veces pueden lograr un mejor resultado al tergiversar sus preferencias, es decir, envían una boleta no veraz al sistema de votación. Los teóricos de la elección social han considerado durante mucho tiempo formas de eludir este problema, como la propuesta de Bartholdi, Tovey y Trick en 1989 basada en la teoría de la complejidad computacional. [11] Consideraron la regla de Copeland de segundo orden (que se puede evaluar en tiempo polinomial) y demostraron que es NP-completapara que un votante decida, sabiendo cómo han votado todos los demás, si es posible manipular de tal manera que algún candidato favorecido sea el ganador. La misma propiedad tiene derecho a voto único transferible . [12]

Por lo tanto, asumiendo la hipótesis ampliamente aceptada de que P ≠ NP , hay casos en los que el tiempo polinomial no es suficiente para establecer si es posible una manipulación beneficiosa. Debido a esto, las reglas de votación que vienen con un problema de manipulación NP-hard son "resistentes" a la manipulación. Cabe señalar que estos resultados solo se refieren al peor de los casos : bien podría ser posible que un problema de manipulación sea generalmente fácil de resolver y solo requiera tiempo superpolinomial en entradas muy inusuales. [13]

Otros temas

Soluciones de torneo

Una solución de torneo es una regla que asigna a cada torneo un conjunto de ganadores. Dado que un perfil de preferencia induce un torneo a través de su relación de mayoría , cada solución de torneo también puede verse como una regla de votación que solo usa información sobre los resultados de los concursos de mayoría por pares. [14] Se han propuesto muchas soluciones para torneos y los teóricos de la elección social computacional han estudiado la complejidad de los problemas asociados de determinación de ganadores. [15] [1]

Restricciones de preferencia

Los dominios de preferencias restringidas, como las preferencias de un solo pico o de un solo cruce , son un área importante de estudio en la teoría de la elección social , ya que las preferencias de estos dominios evitan la paradoja de Condorcet y, por lo tanto, pueden eludir resultados de imposibilidad como el teorema de Arrow y el teorema de Gibbard-Satterthwaite. . [16] [17] [18] [19] Desde una perspectiva computacional, tales restricciones de dominio son útiles para acelerar los problemas de determinación de ganadores, tanto las reglas computacionalmente estrictas de ganador único como de ganador múltiple pueden calcularse en tiempo polinómico cuando las preferencias están estructuradas adecuadamente. [20] [21][22] [23] Por otro lado, los problemas de manipulación también tienden a ser fáciles en estos dominios, por lo que los escudos de complejidad contra la manipulación son menos efectivos. [21] [24] Otro problema computacional asociado con las restricciones de preferencia es el de reconocer cuándo un perfil de preferencia dado pertenece a algún dominio restringido. Esta tarea se puede resolver en tiempo polinomial en muchos casos, incluso para preferencias de un solo pico y un solo cruce, pero puede ser difícil para clases más generales. [25] [26] [27]

Elecciones de múltiples ganadores

Si bien la mayoría de las reglas de votación tradicionales se centran en seleccionar un solo ganador, muchas situaciones requieren seleccionar varios ganadores. Este es el caso cuando se va a elegir un parlamento o un comité de tamaño fijo , aunque las reglas de votación de múltiples ganadores también se pueden usar para seleccionar un conjunto de recomendaciones o instalaciones o un paquete compartido de elementos. El trabajo en la elección social computacional se ha centrado en definir tales reglas de votación, comprender sus propiedades y estudiar la complejidad de los problemas asociados de determinación de ganadores. Ver votación de múltiples ganadores .

Ver también

  • Algocracia
  • Teoría algorítmica de juegos
  • Diseño de mecanismo algorítmico
  • Corte de pastel
  • División justa
  • Juegos hedónicos

Referencias

  1. ^ a b Brandt, Felix; Conitzer, Vincent; Endriss, Ulle; Lang, Jérôme; Procaccia, Ariel D. (25 de abril de 2016). Manual de elección social computacional . Prensa de la Universidad de Cambridge. ISBN 9781107060432.
  2. ↑ Schulze, Markus (11 de julio de 2010). "Un nuevo método de elección de un solo ganador monótono, independiente de clones, simétrico de reversión y consistente condorcet". Elección social y bienestar . 36 (2): 267-303. doi : 10.1007 / s00355-010-0475-4 . S2CID 1927244 . 
  3. ^ Brill, Markus; Fischer, Felix (1 de enero de 2012). "El precio de la neutralidad para el método de pares clasificados" . Actas de la XXVI Conferencia AAAI sobre Inteligencia Artificial . AAAI'12: 1299–1305.
  4. ↑ a b Bartholdi III, J .; Tovey, CA; Trick, MA (1 de abril de 1989). "Esquemas de votación para los que puede ser difícil saber quién ganó las elecciones". Elección social y bienestar . 6 (2): 157-165. doi : 10.1007 / BF00303169 . S2CID 154114517 . 
  5. ^ Hemaspaandra, Edith; Spakowski, Holger; Vogel, Jörg (16 de diciembre de 2005). "La complejidad de las elecciones de Kemeny" . Informática Teórica . 349 (3): 382–391. doi : 10.1016 / j.tcs.2005.08.031 .
  6. ^ Hemaspaandra, Edith; Hemaspaandra, Lane A .; Rothe, Jörg (1997). "Análisis exacto de las elecciones de Dodgson: el sistema de votación de 1876 de Lewis Carroll está completo para el acceso paralelo a NP". J. ACM . 44 (6): 806–825. arXiv : cs / 9907036 . doi : 10.1145 / 268999.269002 . S2CID 367623 . 
  7. ^ Rothe, Jörg; Spakowski, Holger; Vogel, Jörg (6 de junio de 2003). "Complejidad exacta del problema del ganador para elecciones jóvenes". Teoría de los sistemas informáticos . 36 (4): 375–386. arXiv : cs / 0112021 . doi : 10.1007 / s00224-002-1093-z . S2CID 3205730 . 
  8. ^ Caragiannis, Ioannis; Covey, Jason A .; Feldman, Michal ; Homan, Christopher M .; Kaklamanis, Christos; Karanikolas, Nikos; Procaccia, Ariel D .; Rosenschein, Jeffrey S. (1 de agosto de 2012). "Sobre la aproximabilidad de las elecciones de Dodgson y Young" . Inteligencia artificial . 187 : 31–51. doi : 10.1016 / j.artint.2012.04.004 .
  9. ^ Ailon, Nir; Charikar, Moisés; Newman, Alantha (1 de noviembre de 2008). "Agregación de información inconsistente: clasificación y agrupación". J. ACM . 55 (5): 23: 1–23: 27. doi : 10.1145 / 1411509.1411513 . S2CID 5674305 . 
  10. ^ Betzler, Nadja; Becarios, Michael R .; Guo, Jiong; Niedermeier, Rolf; Rosamond, Frances A. (23 de junio de 2008). Fleischer, Rudolf; Xu, Jinhui (eds.). Algoritmos de parámetros fijos para puntuaciones de Kemeny . Apuntes de conferencias en Ciencias de la Computación. Springer Berlín Heidelberg. págs. 60–71. CiteSeerX 10.1.1.145.9310 . doi : 10.1007 / 978-3-540-68880-8_8 . ISBN  9783540688655.
  11. ^ Bartholdi, JJ; Tovey, CA; Trick, MA (1989). "La dificultad computacional de manipular una elección". Elección social y bienestar . 6 (3): 227–241. doi : 10.1007 / BF00295861 . S2CID 16158098 . 
  12. ^ Bartholdi, John J .; Orlin, James B. (1991). "El voto único transferible resiste el voto estratégico". Elección social y bienestar . 8 (4): 341–354. CiteSeerX 10.1.1.127.97 . doi : 10.1007 / BF00183045 . S2CID 17749613 .  
  13. ^ Faliszewski, Piotr; Procaccia, Ariel D. (23 de septiembre de 2010). "La guerra de la IA contra la manipulación: ¿estamos ganando?" . Revista AI . 31 (4): 53–64. CiteSeerX 10.1.1.205.2873 . doi : 10.1609 / aimag.v31i4.2314 . 
  14. ↑ Fishburn, P. (1 de noviembre de 1977). "Funciones de elección social de Condorcet". Revista SIAM de Matemática Aplicada . 33 (3): 469–489. doi : 10.1137 / 0133030 .
  15. ↑ Moon, John W. (1 de enero de 1968). Temas sobre torneos . Holt, Rinehart y Winston.
  16. ↑ Black, Duncan (1 de enero de 1948). "Sobre el fundamento de la toma de decisiones en grupo". Revista de Economía Política . 56 (1): 23–34. doi : 10.1086 / 256633 . JSTOR 1825026 . S2CID 153953456 .  
  17. ↑ Rothstein, P. (1 de diciembre de 1990). "Orden de preferencias restringidas y regla de la mayoría". Elección social y bienestar . 7 (4): 331–342. doi : 10.1007 / BF01376281 . S2CID 153683957 . 
  18. ↑ Arrow, Kenneth J. (26 de junio de 2012). Elección social y valores individuales . Prensa de la Universidad de Yale. ISBN 978-0300186987.
  19. ^ Sen, Amartya; Pattanaik, Prasanta K (1 de agosto de 1969). "Condiciones necesarias y suficientes para la elección racional bajo decisión mayoritaria". Revista de teoría económica . 1 (2): 178–202. doi : 10.1016 / 0022-0531 (69) 90020-9 .
  20. ^ Elkind, Edith ; Lackner, Martin; Peters, Dominik (1 de julio de 2016). "Restricciones de preferencia en la elección social computacional: progreso reciente" (PDF) . Actas de la 25ª Conferencia Internacional sobre Inteligencia Artificial . IJCAI'16: 4062–4065.
  21. ^ a b Brandt, Felix; Brill, Markus; Hemaspaandra, Edith; Hemaspaandra, Lane (1 de enero de 2015). "Eludir las protecciones combinatorias: algoritmos de tiempo polinomial para electorados de un solo pico" . Revista de Investigación en Inteligencia Artificial . 53 : 439–496. doi : 10.1613 / jair.4647 .
  22. ^ N., Betzler; A., Slinko; J., Uhlmann (2013). "Sobre el cálculo de la representación totalmente proporcional" . Revista de Investigación en Inteligencia Artificial . 47 (2013): 475–519. arXiv : 1402.0580 . Código bibliográfico : 2014arXiv1402.0580B . doi : 10.1613 / jair.3896 . S2CID 2839179 . 
  23. ^ Skowron, Piotr; Yu, Lan; Faliszewski, Piotr; Elkind, Edith (2 de marzo de 2015). "La complejidad de la representación totalmente proporcional para los electorados de un solo cruce". Informática Teórica . 569 : 43–57. arXiv : 1307.1252 . doi : 10.1016 / j.tcs.2014.12.012 .
  24. ^ Faliszewski, Piotr; Hemaspaandra, Edith; Hemaspaandra, Lane A .; Rothe, Jörg (1 de febrero de 2011). "El escudo que nunca fue: las sociedades con preferencias únicas están más abiertas a la manipulación y el control". Información y Computación . 209 (2): 89-107. arXiv : 0909.3257 . doi : 10.1016 / j.ic.2010.09.001 .
  25. ↑ Peters, Dominik (25 de febrero de 2016). "Reconocimiento de preferencias euclidianas multidimensionales". arXiv : 1602.08109 [ cs.GT ].
  26. ^ Doignon, JP; Falmagne, JC (1 de marzo de 1994). "Un algoritmo de tiempo polinomial para representaciones desplegables unidimensionales". Revista de algoritmos . 16 (2): 218-233. doi : 10.1006 / jagm.1994.1010 .
  27. ^ Escoffier, Bruno; Lang, Jérôme; Öztürk, Meltem (1 de enero de 2008). Consistencia de un solo pico y su complejidad . Actas de la Conferencia de 2008 sobre ECAI 2008: 18ª Conferencia Europea de Inteligencia Artificial . págs. 366–370. ISBN 9781586038915.

enlaces externos

  • El sitio web de COMSOC , que ofrece una colección de materiales relacionados con la elección social computacional, como talleres académicos, tesis de doctorado y una lista de correo.
Obtenido de " https://en.wikipedia.org/w/index.php?title=Computational_social_choice&oldid=1030344569 "
Contribute a better translation