슐츠 방법

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

슐츠 방법(Schulze method)은 1997년 마커스 슐츠가 개발한 선거 제도이다. 이 방법으로 승자들의 정렬된 목록을 만들어낼 수 있다.

예시[편집]

후보자가 5명(A, B, C, D, E)이고 투표자가 45명인 예시를 살펴보자.

선호순서 투표자수
ACBED 5
ADECB 5
BEDAC 8
CABED 3
CAEBD 7
CBADE 2
DCEBA 7
EBADC 8
45
짝 대결 행렬
d[*,A] d[*,B] d[*,C] d[*,D] d[*,E]
d[A,*] 20 26 30 22
d[B,*] 25 16 33 18
d[C,*] 19 29 17 24
d[D,*] 15 12 28 14
d[E,*] 23 27 21 31
짝 대결 그래프
Schulze method example1.svg

경로의 강도(strength)는 가장 약한 고리(=노드)의 강도를 말한다. 다음 표는 후보자 각 쌍에 대해 한 후보자 X에서 다른 후보자 Y로 가는 최강 경로를 보여준다. 이들 최강경로에서 가장 약한 고리는 밑줄로 표시되어 있다.

최강경로
→ A → B → C → D → E
A →
Schulze method example1 AB.svg
A-(30)-D-(28)-C-(29)-B
Schulze method example1 AC.svg
A-(30)-D-(28)-C
Schulze method example1 AD.svg
A-(30)-D
Schulze method example1 AE.svg
A-(30)-D-(28)-C-(24)-E
B →
Schulze method example1 BA.svg
B-(25)-A
Schulze method example1 BC.svg
B-(33)-D-(28)-C
Schulze method example1 BD.svg
B-(33)-D
Schulze method example1 BE.svg
B-(33)-D-(28)-C-(24)-E
C →
Schulze method example1 CA.svg
C-(29)-B-(25)-A
Schulze method example1 CB.svg
C-(29)-B
Schulze method example1 CD.svg
C-(29)-B-(33)-D
Schulze method example1 CE.svg
C-(24)-E
D →
Schulze method example1 DA.svg
D-(28)-C-(29)-B-(25)-A
Schulze method example1 DB.svg
D-(28)-C-(29)-B
Schulze method example1 DC.svg
D-(28)-C
Schulze method example1 DE.svg
D-(28)-C-(24)-E
E →
Schulze method example1 EA.svg
E-(31)-D-(28)-C-(29)-B-(25)-A
Schulze method example1 EB.svg
E-(31)-D-(28)-C-(29)-B
Schulze method example1 EC.svg
E-(31)-D-(28)-C
Schulze method example1 ED.svg
E-(31)-D
p[*,A] p[*,B] p[*,C] p[*,D] p[*,E]
p[A,*] 28 28 30 24
p[B,*] 25 28 33 24
p[C,*] 25 29 29 24
p[D,*] 25 28 28 24
p[E,*] 25 28 28 31
최강경로의 강도

E 후보자는, 모든 다른 후보자 X에 대하여 p[E,X] ≥ p[X,E]이므로 잠재적 승자이다.

  • 25 = p[E,A] > p[A,E] = 24이므로 후보자 E는 후보자 A보다 선호된다.
  • 28 = p[E,B] > p[B,E] = 24이므로 후보자 E는 후보자 B보다 선호된다.
  • 28 = p[E,C] > p[C,E] = 24이므로 후보자 E는 후보자 C보다 선호된다.
  • 31 = p[E,D] > p[D,E] = 24이므로 후보자 E는 후보자 D보다 선호된다.
  • 28 = p[A,B] > p[B,A] = 25이므로 후보자 A는 후보자 B보다 선호된다.
  • 28 = p[A,C] > p[C,A] = 25이므로 후보자 A는 후보자 C보다 선호된다.
  • 30 = p[A,D] > p[D,A] = 25이므로 후보자 A는 후보자 D보다 선호된다.
  • 29 = p[C,B] > p[B,C] = 28이므로 후보자 C는 후보자 B보다 선호된다.
  • 29 = p[C,D] > p[D,C] = 28이므로 후보자 C는 후보자 D보다 선호된다.
  • 33 = p[B,D] > p[D,B] = 28이므로 후보자 B는 후보자 D보다 선호된다.

그러므로 슐츠 순위는 E > A > C > B > D 순이다.

구현[편집]

후보자 수를 C라고 하자. 그러면 플로이드-워셜 알고리듬으로 가장 강력한 경로의 강도를 계산할 수 있다. 아래의 파스칼 유사코드는 그러한 경로 판단을 나타낸 것이다.

  • 입력: d[i,j]는 i후보를 j후보보다 강력하게 선호하는 투표자 수이다.
  • 출력: p[i,j]는 i후보에서 j후보로 가는 가장 강력한 경로의 강도이다.
  1. for i : = 1 to C
    
  2. begin
    
  3.    for j : = 1 to C
    
  4.    begin
    
  5.       if ( i ≠ j ) then
    
  6.       begin
    
  7.          if ( d[i,j] > d[j,i] ) then
    
  8.          begin
    
  9.             p[i,j] : = d[i,j]
    
  10.          end
    
  11.          else
    
  12.          begin
    
  13.             p[i,j] : = 0
    
  14.          end
    
  15.       end
    
  16.    end
    
  17. end
    
  18.  
    
  19. for i : = 1 to C
    
  20. begin
    
  21.    for j : = 1 to C
    
  22.    begin
    
  23.       if ( i ≠ j ) then
    
  24.       begin
    
  25.          for k : = 1 to C
    
  26.          begin
    
  27.             if ( i ≠ k ) then
    
  28.             begin   
    
  29.                if ( j ≠ k ) then
    
  30.                begin
    
  31.                   p[j,k] : = max ( p[j,k], min ( p[j,i], p[i,k] ) )
    
  32.                end
    
  33.             end
    
  34.          end
    
  35.       end
    
  36.    end
    
  37. end