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]
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 .
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.