Método de Dodgson

El método de Dodgson es un sistema electoral propuesto por el autor, matemático y lógico Charles Dodgson, más conocido como Lewis Carroll. El método consiste en ampliar el método Condorcet intercambiando candidatos hasta encontrar un ganador Condorcet. El ganador es el candidato que requiere el número mínimo de intercambios. Dodgson propuso este esquema de votación en su obra de 1876 "Un método para votar sobre más de dos temas". Dado un entero k y una elección, es NP-completo determinar si un candidato puede convertirse en ganador de Condorcet con menos de k intercambios.

Descripción

En el método de Dodgson, cada votante presenta una lista ordenada de todos los candidatos según su propia preferencia (de mejor a peor). El ganador se define como el candidato para el que necesitamos realizar el número mínimo de intercambios por pares en cada boleta (agregado sobre todos los candidatos) antes de que se convierta en un ganador de Condorcet. En particular, si ya hay un ganador de Condorcet, gana la elección.

En resumen, debemos encontrar el perfil de votación con distancia mínima de Kendall tau de la entrada, de modo que tenga un ganador de Condorcet; luego, el ganador de Condorcet es declarado vencedor. Calcular el ganador o incluso el puntaje Dodgson de un candidato (la cantidad de intercambios necesarios para que ese candidato sea ganador) es un problema NP-difícil por reducción de Cobertura Exacta por 3-Sets (X3C).