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 con mayoría de votos ; si no se encuentra tal ganador, procede a encontrar al candidato que podría transformarse en un ganador de Condorcet con el menor número posible de modificaciones en la papeleta , donde una modificación en la papeleta intercambia dos candidatos adyacentes en la papeleta de un votante. ^{[ 1 ]}

Este sistema clásico consistente con Condorcet, aunque computacionalmente complejo, fue definido en el folleto de Dodgson titulado A Method of Taking Votes on More an Two Issues . Apareció en marzo de 1876, impreso por Clarendon Press, Oxford, con el encabezado «aún no publicado». ^{[ 2 ]}^{[ 3 ]}

Descripción

En el método de Dodgson, cada votante envía una lista ordenada de todos los candidatos según su preferencia (de mejor a peor). El ganador se define como el candidato para el cual 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 distancia tau de Kendall mínima desde la entrada, de modo que tenga un ganador de Condorcet; entonces, el ganador de Condorcet es declarado vencedor. Calcular el ganador o incluso la puntuación de Dodgson de un candidato (el número de intercambios necesarios para que ese candidato sea un ganador) es un problema NP-difícil ^{[ 4 ]} por reducción de la Cobertura Exacta por 3-Conjuntos (X3C). ^{[ 5 ]}

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

Referencias

↑ Ratliff, Thomas C. (2001-01-01). "Una comparación del método de Dodgson y la regla de Kemeny" . Social Choice and Welfare . 18 (1): 79– 89. doi : 10.1007/s003550000060 . ISSN 1432-217X .
↑ Mclean, Iain. "Votación" . El mundo matemático de Charles L. Dodgson (Lewis Carroll) . Capítulo 5.
↑ Caragiannis, Ioannis. "Regla de Dodgson y regla de Young" (PDF) . Manual de elección social computacional .
↑ Bartholdi, J.; Tovey, CA; Trick, MA (abril de 1989). "Esquemas de votación en los que puede ser difícil determinar quién ganó las elecciones". Social Choice and Welfare . 6 (2): 157– 165. doi : 10.1007/BF00303169 . S2CID 154114517 . El artículo solo demuestra directamente la NP-dificultad, pero está claro que el problema de decisión pertenece a NP, ya que, dado un candidato y una lista de k intercambios, se puede determinar si ese candidato es un ganador de Condorcet en tiempo polinomial.
↑ Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability . WH Freeman Co., San Francisco. ISBN 9780716710455.

[1] Ratliff, Thomas C. (2001-01-01). "Una comparación del método de Dodgson y la regla de Kemeny" . Social Choice and Welfare . 18 (1): 79– 89. doi : 10.1007/s003550000060 . ISSN 1432-217X .

[2] Mclean, Iain. "Votación" . El mundo matemático de Charles L. Dodgson (Lewis Carroll) . Capítulo 5.

[3] Caragiannis, Ioannis. "Regla de Dodgson y regla de Young" (PDF) . Manual de elección social computacional .

[btt-4] Bartholdi, J.; Tovey, CA; Trick, MA (abril de 1989). "Esquemas de votación en los que puede ser difícil determinar quién ganó las elecciones". Social Choice and Welfare . 6 (2): 157– 165. doi : 10.1007/BF00303169 . S2CID 154114517 . El artículo solo demuestra directamente la NP-dificultad, pero está claro que el problema de decisión pertenece a NP, ya que, dado un candidato y una lista de k intercambios, se puede determinar si ese candidato es un ganador de Condorcet en tiempo polinomial.

[gj1979-5] Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability . WH Freeman Co., San Francisco. ISBN 9780716710455.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]