도그손의 방법

Dodgson's method

도드슨의 방법루이스 캐롤로 더 잘 알려진 작가, 수학자, 논리학자 찰스 도드슨이 제안한 선거제도다.콘도르셋 당첨자가 나올 때까지 후보지를 교환해 콘도르셋 방식을 연장하는 방식이다.승자는 최소한의 스왑 인원을 필요로 하는 후보자다.도드슨 의원은 1876년 저서 '두 가지 이상의 쟁점에 대해 표를 얻는 방법'에서 이 투표 방식을 제안했다.정수 k와 선거를 부여하면 후보가 k 스와프 이하로 콘도르셋 우승자가 될 수 있는지 여부를 결정하는 것은 NP완전이다.

설명

도드슨 방식에서는 각 유권자가 각자의 선호도(최악에서 최악까지)에 따라 모든 후보의 순서 목록을 제출한다.승자는 각 투표용지(모든 후보자 위에 추가)가 콘도르셋 당첨자가 되기 전에 최소 수의 쌍끌이 스왑을 수행해야 하는 후보자로 정의된다.특히 콘도르케트 승자가 이미 있으면 당선된다.

간단히 말해서, 우리는 콘도르셋 승자가 있을 수 있도록 입력으로부터 최소 Kendall tau 거리를 두고 투표 프로파일을 찾아야 한다. 그리고 나서 콘도르셋 승자는 승자로 선언된다.후보의 승자 또는 도드슨 점수(그 후보를 승자로 만드는 데 필요한 스왑 수)를 계산하는 것은 정확한 커버(X3C)를 3세트 줄임으로써 NP-하드 문제다[1].[2]

참조

  1. ^ 바르톨디, J., 토비, CA;트릭, M.A.(1989년 4월)."계획 투표에 누가 선거에서 이겼다 말하기는 힘들 수 있".사회적 선택과 복지. 6(2):157–165. doi:10.1007/BF00303169.그 물품은 직접, 하지만 그 결정 문제 NP에 이어후보자이고, k스와프 거래 목록을 마련한다면, 당신은 다항식 시간에 그 후보는 꽁도르세 우승자 말할 수도 있다. NP-hardness을 증명한다.
  2. ^ Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability. W.H. Freeman Co., San Francisco.