stringtranslate.com

El método de Dodgson

El método de Dodgson es un sistema electoral basado en una propuesta del matemático Charles Dodgson, más conocido como Lewis Carroll . El método busca un ganador preferido por la mayoría ; si no se encuentra tal ganador, el método procede a encontrar al candidato que podría transformarse en un ganador de Condorcet con el menor número de ediciones de la papeleta posible, donde una edición de la papeleta cambia a dos candidatos vecinos en la papeleta de un votante. [1]

Descripción

En el método de Dodgson, cada votante presenta una lista ordenada de todos los candidatos según su propia preferencia (del mejor al peor). El ganador se define como el candidato para el que necesitamos realizar el número mínimo de intercambios por pares en cada votación (sumados sobre todos los candidatos) antes de que se convierta en un ganador de Condorcet .

Cálculo

En resumen, debemos encontrar el perfil de votación con la mínima distancia de tau de Kendall desde la entrada, de modo que tenga un ganador de Condorcet; luego, el ganador de Condorcet se declara vencedor. Calcular el ganador o incluso la puntuación Dodgson de un candidato (la cantidad de intercambios necesarios para que ese candidato sea un ganador) es un problema NP-hard [2] por reducción de la cobertura exacta por 3 conjuntos (X3C). [3]

Dado un entero k y una elección, es NP-completo determinar si un candidato puede convertirse en un ganador de Condorcet con menos de k intercambios.

Referencias

  1. ^ Ratliff, Thomas C. (1 de enero de 2001). "Una comparación del método de Dodgson y la regla de Kemeny". Elección social y bienestar . 18 (1): 79–89. doi :10.1007/s003550000060. ISSN  1432-217X.
  2. ^ Bartholdi, J.; Tovey, CA; Trick, MA (abril de 1989). "Esquemas de votación en los que puede resultar difícil determinar quién ganó la elección". Elección social y bienestar . 6 (2): 157–165. doi :10.1007/BF00303169. S2CID  154114517.El artículo sólo prueba directamente la dureza NP, pero está claro que el problema de decisión está en NP ya que dado un candidato y una lista de k intercambios, se puede saber si ese candidato es un ganador de Condorcet en tiempo polinomial.
  3. ^ Garey, Michael R.; Johnson, David S. (1979). Computadoras e intratabilidad . WH Freeman Co., San Francisco. ISBN 9780716710455.