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 extender el método Condorcet intercambiando candidatos hasta que se encuentre un ganador de Condorcet. El ganador es el candidato que requiere el número mínimo de intercambios. Dodgson propuso este esquema de votación en su trabajo de 1876 "Un método para votar en más de dos cuestiones". 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.
Descripción
En el método de Dodgson, cada votante presenta una lista ordenada de todos los candidatos de acuerdo con sus propias preferencias (de mejor a peor). El ganador se define como el candidato por el que necesitamos realizar el número mínimo de intercambios por pares en cada boleta (sumado a todos los candidatos) antes de que se conviertan en un ganador de Condorcet . En particular, si ya hay un ganador de Condorcet , ganan las elecciones.
En definitiva, debemos encontrar el perfil de voto con una distancia mínima de Kendall tau de la entrada, de manera que tenga un ganador Condorcet; luego, el ganador de Condorcet es declarado vencedor. Computar el ganador o igualar el marcador Dodgson de un candidato (el número de permutas necesarias para hacer que el candidato ganador) es una NP-difícil problema [1] mediante la reducción de Exact cubierta por 3-Sets (X3c). [2]
Referencias
- ↑ Bartholdi, J .; Tovey, CA; Trick, MA (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 . El artículo solo 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, puede saber si ese candidato es un ganador de Condorcet en tiempo polinomial.
- ^ Garey, Michael R .; Johnson, David S. (1979). Ordenadores e intratabilidad . WH Freeman Co., San Francisco.