슐제법

정치 시리즈의 일부
선거 제도
1인승/메이저리스트 복수 First-Past-The-Post 복수 일반 투표(복수 블록 투표) 일반 티켓(정당 블록 투표) 복수 투표 투 라운드 완전 투표 예비 선거 비당파적 통일된 톱4 과반수 (2라운드 블록 투표) 순위/우대 시스템 즉석 결선투표(대안투표) 예비투표 쿰스법 콘도르세트 방법(코프랜드, 도그슨, 케메니-)Young, Minimax, Nanson's, 랭킹 페어, Schulze, Alternative Smith) 포지션 투표(Borda count, Nauru/Dowdall 방식) 버클린 투표 오클라호마 프라이머리 선거 제도 우선 블록 투표 기본/등급제 스코어 투표 승인 투표 통합승인투표 통합 프라이머리 통상적인 판단 만족도 승인 투표 다수결 스타 투표
비례대표 파티 리스트 선거인 명부 공개 리스트 클로즈드 로컬 리스트 최고 평균법 돈트 생트 라구에 헌팅턴힐 최대 잔량 토끼 드롭 임페리얼리 하겐바흐비쇼프 민족 잔재 순위 파티 리스트 PR 예비투표 순위 투표의 비례 형식 단일 양도 가능 투표 그레고리 장인 슐제 장인 기수 투표의 비례 형식 비례승인투표 순차비례승인투표 균등분배법 프라그먼의 투표 규칙 2회전 배치 공정한 다수결 가중 투표 직접 표현 대화식 표현 액체 민주주의
혼합 시스템 표현 유형별 혼성 다수파 혼성비례 비보상 혼합 시스템 병렬 투표 과반수 보너스 보상 혼합 시스템 추가회원제 혼합단일투표(긍정표 전송) Skorporo(부정표 전송) 혼합 투표용지 양도 가능 투표 대체 투표 플러스 2인 비례제 농촌-도시 비례
기타 시스템 및 관련 이론 반비례 표현 단일 양도 불가 투표 제한 투표 누적 투표 이항 투표 기타 시스템 다중 양도 불가 투표 이중 동시 투표 대리투표 위임 투표 간접 STV 액체 민주주의 무작위 선택(구분, 무작위 투표) 사회적 선택 이론 애로우의 정리 지바르-새터트웨이트 정리 공공선택론 투표 제도 나라별 선거 제도 선거 제도 비교
정치 포털
v t

슐제 방식(/ˈʃlts//)은 1997년 마르쿠스 슐제에 의해 개발된 선거 시스템으로, 선호도를 나타내는 표를 사용하여 단일 승자를 선출한다.이 방법을 사용하여 당첨자 목록을 정렬할 수도 있습니다.Schulze 방식은 또한 Schwartz Sequential Dropping(SSD), 복제 방지 Schwartz Sequential Dropping(CSS), 비트패스 방식, 비트패스 방식, 경로 투표 및 경로 승자로 알려져 있습니다.

Schulze 방법은 Condorcet 방법이며, 이는 쌍 비교에서 다른 모든 후보보다 과반수에 의해 선호되는 후보가 있는 경우 Schulze 방법이 적용되었을 때 이 후보가 승자가 된다는 것을 의미한다.

Schulze 방법(아래 정의)의 출력은 후보의 순서를 나타냅니다.따라서 여러 자리가 비어 있는 경우, k개의 최상위 후보가 k개의 가용 의석을 획득하도록 함으로써 수정 없이 이 방법을 사용할 수 있다.게다가, 비례대표 선거의 경우, 단일 양도 가능한 투표 변형이 제안되었다.

슐제 방식은 Wikimedia, Debian, Ubuntu, Gentoo, Pirate Party 정당 등 여러 조직에서 사용되고 있습니다.

방법에 대한 설명

투표용지

슐제 방법에 대한 입력은 다른 순위 1위 선거 시스템과 같다: 각 유권자는 동점이 허용되는 후보(엄격한 약한 순서)^[1]에 대해 순서 있는 선호 목록을 제공해야 한다.

유권자들이 투표용지에 자신의 선호도를 명시하는 전형적인 방법 중 하나는 다음과 같다.각 투표용지는 모든 후보를 나열하며, 각 투표자는 숫자를 사용하여 선호도 순으로 이 목록을 순위를 매깁니다. 투표자는 가장 선호하는 후보 옆에 '1'을, 두 번째로 선호도가 높은 후보 옆에 '2'를 배치하는 식입니다.각 유권자는 선택적으로 다음을 수행할 수 있습니다.

• 한 명 이상의 후보자에게 동일한 선호도를 부여합니다.이는 이 유권자들이 이 후보들 사이에 무관심하다는 것을 보여준다.
• 연속되지 않은 숫자를 사용하여 기본 설정을 나타냅니다.이는 선거 결과에 영향을 미치지 않는다. 왜냐하면 후보자의 선호도가 절대적인 숫자가 아니라 투표자에 의해 순위가 매겨지는 순서이기 때문이다.
• 후보자의 순위를 떨어뜨리다유권자가 모든 후보자의 순위를 매기지 않는 경우, 이는 ①순위가 낮은 모든 후보보다 모든 순위를 엄격히 선호하고 ②순위가 낮은 모든 후보자에 대해 무관심한 것으로 해석된다.

계산

$d{\displaystyle }$${\displaystyle }$[${\displaystyle V}$ , $]$ { $displaystyle$d [$V$ , $W$$$} be$$ $、$ 후보 W$candidate$ candidate candidate $candidateV{\displaystyle }$ { $displaystyle$ V$$}를$$ 선호하는 유권자의 수를 $지정$합니다.

$후보{\displaystyle }$ X$(\displaystyle$ X$)$에서 $후보{\displaystyle }$Y(\$displaystyle$ Y$)$로의 경로는 다음 $속성$을 ${\displaystyle \mathrm{가진}}$ $후보$C($1),$ C$(n)$의 시퀀스입니다.

1. ${\displaystyle C}$(${\displaystyle 1}$)${\displaystyle =}$ {$displaystyle C$(1)=$X}$ $및$ C${\displaystyle (n)}$ $=$$$ {$displaystyle$ C$(n$)=$Y$ 。
2. $모든$ i , (n -) :d [ ( )、 ( +) [(+ ) (i ) ]、 [$displaystyle$i=1, \ $cdots$, ( $n$- 1 ) ] >$D$[ C ( $+ 1$

즉, 쌍별 비교에서는 경로 내의 각 후보가 다음 후보를 앞섭니다.

$X{\displaystyle }$후보에서$$ Y$후보$로의 경로 $강도{\displaystyle }$ p$($$디스플레이$ $스타일)$는 비교$$ 순서에서 최소 유권자 수이다.

${\displaystyle \mathrm{모든}}$ i ${\displaystyle =}$ ${\displaystyle 1、}$ ${\displaystyle ,}$、 （${\displaystyle n}$ -${\displaystyle 1）}$ :${\displaystyle d}$[ ${\displaystyle C}$ ( ${\displaystyle i}$ )${\displaystyle }$、${\displaystyle C}$ ( i +${\displaystyle 1}$ )${\displaystyle ]}$ ${\displaystyle p}$p \ $display$i$$= 1, \ $cdots$, ( $n$- 1 ) :$d$[ $C$( i ,$C$ ($i$ + 1$)$ ] \ $geq$ p$$}

적어도 하나의 패스로 연결된 $후보 A$와$$B의 $쌍$에 $대해$ 최강의 $패스{\displaystyle }$ p$](\displaystyle$ p$[A, B])$의 강도는 이들을 연결하는 패스의 최대 강도다.$A$에서 $후보{\displaystyle }$ B$(표시$ 스타일 B)로의 ${\displaystyle \mathrm{경로}}$가 전혀 없는 ${\displaystyle \mathrm{경우}}$ p${\displaystyle }$[A${\displaystyle ,}$ B$=$ $(표시 스타일$ p$[A,$B]=$0$입니다.

$후보{\displaystyle }$ D$(\displaystyle$ D$)$가 $후보{\displaystyle }$E(\$displaystyle$ E$)$ 나은 것은p [ >p [ E , $](\displaystyle$ p$[D,$ E] ] > p [ $E,$D$]$ 인 경우 뿐입니다.

$후보{\displaystyle }$D(\$displaystyle$ D$)$는 다른 $후보{\displaystyle }$E(\$displaystyle$ E$)$에 대해${\displaystyle }$p${\displaystyle }$[${\displaystyle D,E],}$ D$$[\$displaystyle$ p$[D, E]\geq$ p$[E, D]}$가 될 경우에만 $잠재적{\displaystyle }$ 승자가 됩니다.

그것은 p을[X, Y]안[Y, X]{\displaystyle p[X,Y]>, p[Y,X]}과 동업-[Y, Z]<>를 사용하여 안 내려 함께 함축한 동업-안[Z, X]{\displaystyle p[X,Z]>, p[Z,X]}.[1]:§4.1 따라서[X, Z]을{\displaystyle p[Y,Z]>, p[Z,Y]}[Z, Y],(1)을 보장한다.는"더 나은"의 위의 정의 정말 정확을 정의합니다 증명될 수 있Ransitive 관계와(2)기hat 다른 모든 $후보{\displaystyle }$E에 대해 p${\displaystyle }$[${\displaystyle D,E]\ge p}$ [ ${\displaystyle E}$ , D$]$ \ $display$ p [ D ,$E$]\$geq$p [ E , $D$]를 가진 $후보$$D{\displaystyle }$ { \ $displaystyle$$$D $\}$가 항상1개 이상 $존재$합니다.

예

다음 예에서는 45명의 유권자가 5명의 후보자에게 순위를 매긴다.

${\displaystyle {begin{array}{\text{유권자수}}&{\text{선호순서}}\hline5&ACBED\5&ADECB\8&BEDAC\3&CABED\\7&CAEBD\\2&CBADE\\7&DCEBA\8&EBADC\end{array}}$

먼저 쌍별 기본 설정을 계산해야 합니다.예를 들어 A와 B를 쌍으로 비교하면 B보다 A를 선호하는 유권자는 5+5+3+7=20명, A보다 B를 선호하는 유권자는 8+2+7+8=25명이다.$d{\displaystyle }$ [${\displaystyle A}$, ${\displaystyle B}$]$=$ ${\displaystyle 20}$ {$displaystyle d$[ A , B ]= $20$$$} ${\displaystyle 、}$ ${\displaystyle d}$[ B${\displaystyle }$, A ]= ${\displaystyle 25}$ { \ $displaystyle d$ [ $B$ , A $]= 25$} 。전체 쌍별 기본 설정 집합은 다음과 같습니다.

쌍방향 기본 설정 d[*, *] 레이블이 지정된 방향 그래프

쌍별 선호도 행렬

	$\displaystyle d[*,A]}$	$\displaystyle d[*,B]}$	$\displaystyle d[*,C]}$	$\displaystyle d[*,D]}$	$\displaystyle d[*,E]}$
$\displaystyle d[A,*]$		20	26	30	22
$\displaystyle d[B,*]$	25		16	33	18
$\displaystyle d[C,*]$	19	29		17	24
$\displaystyle d[D,*]$	15	12	28		14
$\displaystyle d[E,*]$	23	27	21	31

d[X, Y]의 셀은 d[X, Y]> d[Y, X]의 경우 배경이 연두색이며, 그렇지 않은 경우 배경은 연두색입니다.여기서 단지 쌍으로 보는 것만으로 의심할 여지가 없는 승자는 없다.

이제 가장 강력한 경로를 찾아야 합니다.가장 강력한 경로를 시각화할 수 있도록 오른쪽 다이어그램에 쌍별 기본 설정 세트가 방향 그래프 형식으로 표시됩니다.후보 X를 나타내는 노드에서 후보 Y를 나타내는 노드까지의 화살표는 d[X, Y]로 라벨링된다.그림이 흐트러지지 않도록 d[X, Y]> d[Y, X](즉, 밝은 녹색 배경의 표 셀)에서만 X에서 Y로 화살표가 그려지고 반대 방향의 표 셀(밝은 빨간색 배경의 표 셀)은 생략됩니다.

가장 강한 경로 강도를 계산하는 하나의 예는 p[B, D] = 33이다. B에서 D로의 가장 강한 경로는 강도 33을 갖는 직접 경로(B, D)이다.그러나 p[A, C]를 계산할 때 A에서 C로 가는 가장 강한 경로는 강도 26의 직접 경로(A, C)가 아니라 강도 min(30, 28) = 28인 간접 경로(A, D, C)이다.경로의 강도는 가장 약한 고리의 강도다.

다음 표는 후보 X와 후보 Y의 각 쌍에 대해 후보 X에서 후보 Y로의 가장 강한 경로를 빨간색으로 나타내고 가장 약한 링크에 밑줄이 그어져 있습니다.

최강의 패스

로. 부터	A	B	C	D	E
A	—	A-(30)-D-(28)-C-(29)-B	A-(30)-D-(28)-C	A-(30)-D	A-(30)-D-(28)-C-(24)-E	A
B	B-(25)-A	—	B-(33)-D-(28)-C	B-(33)-D	B-(33)-D-(28)-C-(24)-E	B
C	C-(29)-B-(25)-A	C-(29)-B	—	C-(29)-B-(33)-D	C-(24)-E	C
D	D-(28)-C-(29)-B-(25)-A	D-(28)-C-(29)-B	D-(28)-C	—	D-(28)-C-(24)-E	D
E	E-(31)-D-(28)-C-(29)-B-(25)-A	E-(31)-D-(28)-C-(29)-B	E-(31)-D-(28)-C	E-(31)-D	—	E
	A	B	C	D	E	부터 로.

가장 강력한 경로의 장점

	${\displaystyle p[*,A]}$	${\displaystyle p[*,B]}$	${\displaystyle p[*,C]}$	${\displaystyle p[*,D]}$	${\displaystyle p[*,E]}$
${\displaystyle p[A,*]}$		28	28	30	24
${\displaystyle p[B,*]}$	25		28	33	24
${\displaystyle p[C,*]}$	25	29		29	24
${\displaystyle p[D,*]}$	25	28	28		24
${\displaystyle p[E,*]}$	25	28	28	31

이제 슐제 방법의 출력을 결정할 수 있습니다.예를 들어 A와 B를 비교할 때는 ( ) [ , > [ , ( $=$ ){ $displaystyle (28$=) $p$[ A , $B ]$ >$p$ [ B , $A$] ( =$25$ ) p [ B , A ] ( 25 )가 후보 B보다 좋다. 다른 예로는 ( [, D] p[ , E ( 24 $)$ \ $displaystyle$ ( $31$= )$p$[ E , $D$] ( =$24$ ) > p [ D , $E$ (= )이 $있습니다$.이 결과 슐제 은 E> > > > （ $displaystyle$ E > $A$> $C > B$ 、 E가 승리합니다.즉, 다른 후보 X마다 p${\displaystyle }$[${\displaystyle E,X}$ ${\displaystyle ]}$[ p${\displaystyle }$[ ${\displaystyle X}$, E$$]{ $display p$[ E , X ]\$geq p$[ X , E $]$ }$이후$ E가 승리합니다.

실행

슐제 방법을 구현하기 위한 유일한 어려운 단계는 가장 강력한 경로 강도를 계산하는 것입니다.그러나 이것은 그래프 이론에서 가장 넓은 경로 문제라고도 불리는 잘 알려진 문제입니다.따라서 강도를 계산하는 한 가지 간단한 방법은 Floyd-Warshall 알고리즘의 변형입니다.다음 의사 코드는 알고리즘을 나타내고 있습니다.

# 입력: d[i,j] 후보 j보다 후보 i를 선호하는 유권자 수.# 출력: p[i,j] 후보 i에서 후보 j로의 최강의 경로 강도. i는 1부터 C까지j가 1에서 C까지일 경우i가 j이면d[i,j]> d[j,i]의 경우p[i,j] := d[i,j]또 다른p[i,j] : = 0 i는 1부터 C까지j가 1에서 C까지일 경우i가 j이면1에서 C까지의 k의 경우i kk와 j kk의 경우p[j,k] : = max (p[j,k], min (p[j,i], p[i,k])

이 알고리즘은 효율적이며 실행 시간 O(C³)가 있습니다.C는 후보 수입니다.

연계 및 대체 구현

사용자가 자신의 선호도에 연관성을 가질 수 있도록 허용할 때 슐제 방법의 결과는 자연스럽게 이러한 연관성이 d[*,*]의 정의에 어떻게 해석되는지에 따라 달라진다.d[A, B]는 A보다 B를 엄밀하게 선호하는 유권자의 수(A>B) 또는 (A>B를 가진 유권자)를 뺀 마진(B>A를 가진 유권자) 중 하나를 나타내는 자연스러운 선택입니다.그러나 ds가 어떻게 정의되든 슐제 랭킹은 주기가 없으며, ds가 고유하다고 가정할 때 ^[1]연관성이 없다.

슐제 랭킹에서 동점이 ^{[2][citation needed]}될 가능성은 낮지만 가능성은 있다.슐제의 원래^[1] 논문은 무작위로 뽑힌 투표자에 따라 동점을 깨고 필요에 따라 반복하는 것을 제안했다.

슐제 방법의 승자를 설명하는 다른 방법은 다음과 같습니다.^{[citation needed]}

1. 모든 후보와 후보 사이에 가능한 모든 모서리를 포함하는 완전한 방향 그래프를 그린다.
2. [a] Schwartz 세트에 포함되지 않은 모든 후보(즉, x에 도달하는 다른 모든 후보 x)를 반복적으로 삭제하고 [b] 가장 작은 값(마진, 최소 마진, 투표, 최소 투표)을 가진 그래프 에지를 삭제합니다.
3. 승자는 마지막 비승리 후보입니다.

슐제 방법의 승자를 증명할 수 있는 또 다른 방법이 있다.이 방법은 여기에 설명된 다른 방법과 동일하지만, 프레젠테이션은 계산을 위해가 아니라 인간이 통과할 때 시각적으로 명확하게 나타나는 단계의 중요성에 맞게 최적화된다.

1. 위의 예에서 사용된 것과 같이 "쌍별 선호 매트릭스"라고 하는 결과 표를 작성합니다.미가공 투표 총계가 아닌 마진을 사용하는 경우 전치된 표에서 마진을 뺍니다.그 후, 각 양의 숫자는 그 행의 후보가 쌍으로 승리(및 녹색으로 표시), 동점은 0, 손실은 마이너스(빨간색으로 표시)가 됩니다.후보자들의 탈락 기간을 기준으로 순위를 매겨라.
2. 빨간 줄이 없는 후보가 있으면 이깁니다.
3. 그렇지 않으면 왼쪽 위에 있는 Schwartz 세트 주위에 사각 상자를 그립니다.원외의 누구에게도 지지 않는 최소한의 승자 원이라고 할 수 있다.상자 오른쪽에는 빨간색이 없으며, 이는 우승자의 원임을 의미하며, 상자 내에서는 더 작은 우승자의 원을 생성할 수 있는 정렬이 불가능하다는 점에 유의하십시오.
4. 상자 밖에 있는 테이블의 모든 부분을 잘라내세요.
5. 만약 여전히 빨간색이 없는 후보가 없다면, 타협할 필요가 있다. 모든 후보들은 어느 정도 경선에서 졌고, 우리가 가장 잘 참는 것은 패배자가 가장 많은 표를 얻은 것이다.따라서 숫자가 가장 큰 빨간색 셀(여백으로 표시할 경우 가장 작은 음수)을 녹색(또는 빨간색 이외의 색상)으로 하고 2단계로 돌아갑니다.

위의 예에서 작성한 마진표를 다음에 나타냅니다.데모용으로 사용되는 순서 변경에 주의해 주세요.

첫 번째 하락(A가 E에게 1표 차로 패함)은 Schwartz 세트를 축소하는 데 도움이 되지 않습니다.

두 번째 드롭(E가 C에게 3표 차로 패)으로 직행하면 승자 E가 명확하게 표시됩니다.

또한 이 방법은 테이블이 행과 열의 후보 순서를 항상 같은 순서로 편리하고 안정적으로 재배치할 수 있도록 리메이크된 경우 결과를 계산할 때도 사용할 수 있습니다.

만족 및 불합격 기준

만족 기준

슐제 방법은 다음 기준을 충족한다.

실패한 기준

Schulze 방법은 Condorcet 기준을 충족하므로 다음 기준을 자동으로 충족하지 못한다.

• 참가^{[1]: §3.4}
• 일관성.
• 타협에 대한 무방비
• 매몰에 대한 무해성
• 후발 무해

마찬가지로 슐제 방식은 독재정권이 아니고 만장일치 표결에 동의하기 때문에 애로우의 정리는 기준에 어긋난다는 것을 암시한다.

• 무관한 대안의 독립성

Schulze 메서드도 실패합니다.

• 페이튼 영의 기준 무관한 대안들의 지역 독립성.

비교표

다음 표는 Schulze 방식과 다른 선호 단일 당선자 선출 방법을 비교한 것입니다.

슐제 방법과 순위 쌍 방법의 주된 차이는 이 예에서 확인할 수 있습니다.

후보 세트 X의 최소 최대 점수가 후보 A와 후보 B와 후보 X의 쌍으로 가장 강한 승리 강도라고 가정합니다.랭크 페어가 아닌 Schulze 메서드는 승자가 항상 최소 MinMax ^{[1]: §4.8} 점수를 가진 세트의 후보임을 보증합니다.그래서 어떤 의미에서 슐제 방식은 승자를 결정할 때 뒤집어야 하는 가장 큰 다수를 최소화한다.

한편, 랭크 페어에서는, 미니 플렉스·맥스(minlexmax)의 의미에서는,^{[citation needed][5]} 완료 순서를 결정하기 위해서 반전할 필요가 있는 대부분을 최소한으로 억제할 수 있습니다.즉, 순위 쌍과 슐제 방법이 서로 다른 결승 순서를 산출할 때, 두 결승 순서가 일치하지 않는 주요 순서의 경우 슐제 순서는 순위 쌍 순서보다 더 많은 순위를 역전시킵니다.

역사

Schulze 방법은 Markus Schulze에 의해 1997년에 개발되었습니다.그것은 1997-1998년과^{[6] [7]}2000년에 공공 우편물 목록에서 처음 논의되었다.그 후 슐제 메서드 사용자에는 Debian(2003),^[8] Gentoo(2005),^[9] Topcoder(2005),^[10] Wikimedia(2008),^[11] KDE(2008),^[12] 스웨덴 해적당(2009),^[13] 독일 해적당(2010)^[14] 등이 있습니다.프랑스어 위키피디아에서 슐제 방식은 2005년 ^[15]다수결로 승인된 두 가지 다중 후보 방식 중 하나였으며,^[16] 여러 번 사용되어 왔다.지난 2월 새로 결성된 미국민주사회당 아이다호주 보이시 지부는 2018년 ^[17]3월 치러진 첫 특별선거에서 이 방식을 택했다.

2011년 슐제는 이 방법을 학술지 사회선택과 복지(^[1]Social Choice and Happy)에 발표했다.

사용자

Wikimedia 이사회 선거 샘플 투표

슐제 방식은 모든 주민투표에 신라시가 사용한다.전기전자공학협회, 컴퓨터기계협회, USENIX가 HotCRP 의사결정 도구를 사용하여 사용합니다.슐제 방법은 토리노시와 산도나 디 피아브시와 런던 서드워크구가 WeGovNow 플랫폼을 사용하여 사용하며, LiquidFeedback 의사결정 도구를 사용합니다.현재 Schulze 방법을 사용하는 조직은 다음과 같습니다.

메모들

외부 링크

Wikimedia Commons에는 Schulze 메서드와 관련된 미디어가 있습니다.

• 마르쿠스 슐제의 슐제 투표법
• 휴버트 브레이의 슐제 방법
• Spieltherie (독일어) Bernhard Nebel 지음
• Rob Loring의 정확한 민주주의
• Christoph Börgers(2009), 사회적 선택의 수학: 투표, 보상, 분할, SIAM, ISBN 0-89871-695-0
• Nicolaus Tideman (2006), 집단 의사결정 및 투표: 공공 선택의 가능성, 벌링턴:애쉬게이트, ISBN 0-7546-4717-X
• Public Software Group에 의한 프리프트풀
• 콘도르세트 순위 투표용 아리조난스
• Schulze를 포함한 여러 Condorcet 메서드를 지원하는 Condorcet PHP 명령줄 애플리케이션 및 PHP 라이브러리.
• Java에서의 구현
• 루비에서의 실장
• Python 2에서의 구현
• Python 3에서의 구현