Phương pháp Schulze

Phương pháp Schulze (phát âm [ˈʃʊl.t͡sə]) là một phương pháp đầu phiếu xếp hạng chỉ có một người thắng cuộc do nhà nghiên cứu người Đức Markus Schulze phát triển. Phương pháp này được một số tổ chức như Debian, Ubuntu, Gentoo, Đảng Cướp biển, v.v. sử dụng. Thêm vào đó, Wikimedia từng sử dụng phương pháp này trước khi áp dụng hình thức đầu phiếu chấm điểm.

Miêu tả

Phương pháp Schulze sử dụng hệ thống đầu phiếu xếp hạng cho phép cử tri xếp hạng giống nhau cho nhiều ứng cử viên khác nhau. Phương pháp Schulze có thể được mô tả theo hai cách tương đương nhau như sau:

Hướng mô tả "chuỗi đánh bại"

Theo phương pháp Schulze, nếu Alice đánh bại Bob và Bob đánh bại Charlie thì ta có thể suy ra là Alice đã "gián tiếp" đánh bại Charlie. Tập hợp các chiến thắng trên được gọi là một "chuỗi đánh bại".

Mỗi một chuỗi đánh bại có một độ mạnh xác định: độ mạnh của một chuỗi đánh bại đơn (chẳng hạn như giữa Alice và Bob) chính là số cử tri xếp hạng Alice cao hơn Bob. Độ mạnh của một chuỗi đánh bại đa bước với nhiều chiến thắng là độ mạnh của chiến thắng có độ mạnh thấp nhất trong số các chiến thắng thành phần (tức là chiến thắng với số lượng cử tri thấp nhất).

Ta có thể nói Alice chiến thắng Bob "dựa trên chuỗi đánh bại" nếu như chuỗi đánh bại Bob mạnh nhất của Alice có độ mạnh lớn hơn tất cả các chuỗi đánh bại Alice mạnh nhất của Bob. Ứng cử viên chiến thắng trong cuộc bầu cử là người chiến thắng tất cả các ứng cử viên còn lại dựa trên chuỗi đánh bại.

Markus Schulze đã chứng minh được rằng "chiến thắng dựa trên chuỗi đánh bại" có tính chất bắc cầu, tức là nếu Alice chiến thắng Bob dựa trên chuỗi đánh bại, và Bob chiến thắng Charlie dựa trên chuỗi đánh bại, thì Alice chiến thắng Charlie dựa trên chuỗi đánh bại.^[1]^:§4.1 Do đó, phương pháp Schulze cũng là một phương pháp đầu phiếu kiểu Condorcet và mở rộng trọn vẹn quy tắc đa số đối với tất cả cuộc bầu cử kiểu Condorcet.

Hướng mô tả lặp

Vẽ một đồ thị có hướng với các nút là các ứng viên và đặt tên cho các mũi tên theo số lượng cử tri ủng hộ người thắng cuộc
Nếu như chưa chọn được ứng cử viên chiến thắng:
- Kiểm tra xem có ứng cử viên nào hòa không (nếu có các ứng cử viên hòa, hãy quyết định người chiến thắng bằng cách bỏ phiếu ngẫu nhiên)
- Loại bỏ tất cả các ứng cử viên không thuộc tập hợp được đa số ưa thích
- Xóa mũi tên có độ mạnh gần với độ mạnh hòa nhất

Người duy nhất trụ lại sau quy trình trên là người chiến thắng trong cuộc bầu cử.

Ví dụ

Trong cuộc bầu cử sau, có 45 cử tri và 5 ứng cử viên.

Số lượng cử tri	Thứ tự ưa thích
5	ACBED
5	ADECB
8	BEDAC
3	CABED
7	CAEBD
2	CBADE
7	DCEBA
8	EBADC

Trước hết, ta cần tính độ ưa thích cặp đôi. Chẳng hạn, khi so sánh cặp A và B, ta thấy có $5+5+3+7=20$ cử tri thích $A$ hơn $B$ và $8+2+7+8=25$ cử tri thích $B$ hơn $A$ . Vì thế $d[A,B]=20$ và $d[B,A]=25$ . Sau đây là bảng thể hiện độ ưa thích cặp đôi của tất cả các cặp.

Ma trận độ ưa thích cặp đôi
	$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

Ô $d[X,Y]$ có màu xanh lá cây khi $d[X,Y]>d[Y,X]$ và có màu đỏ khi $d[X,Y]<d[Y,X]$ . Dựa trên bảng này, ta chưa thể xác định được người thắng cuộc tuyệt đối.

Bây giờ ta xác định chuỗi đánh bại có độ lớn mạnh nhất. Để trực quan hóa chuỗi đánh bại này, ta vẽ một sơ đồ có dạng đồ thị có hướng như hình bên dựa trên ma trận độ ưa thích cặp đôi. Mũi tên kéo từ điểm X tới điểm Y được gán độ mạnh $d[X,Y]$ . Trong sơ đồ bên, ta chỉ vẽ mũi tên từ điểm X tới điểm Y khi $d[X,Y]>d[Y,X]$ (độ mạnh trong ô màu xanh lá cây) để tránh trình bày quá nhiều số liệu.

Sau đây là một ví dụ về việc tính chuỗi đánh bại mạnh nhất. Theo đồ thị , ta thấy $d[B,D]=33$ : mũi tên có độ mạnh lớn nhất từ B đến D là mũi tên từ B đến D, có độ mạnh là 33. Tuy nhiên, chuỗi đánh bại mạnh nhất của A đối với C không phải là mũi tên thẳng từ A đến C với độ mạnh 26, nhưng lại là chuỗi gián tiếp (A, D, C) với độ mạnh bằng $min(30,28)=28$ . Như ta đã trình bày ở trên, độ mạnh của một chuỗi đánh bại chính bằng độ mạnh của chiến thắng thành phần có độ mạnh nhỏ nhất.

Với mỗi một cặp ứng cử viên X và Y, bảng sau thể hiện chuỗi đánh bại mạnh nhất của X đối với Y được in đậm với nét màu đỏ và chiến thắng thành phần với độ mạnh nhỏ nhất được gạch chân.

Chuỗi đánh bại mạnh nhất
Đến Từ	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	From To

Độ mạnh chuỗi đánh bại mạnh nhất
	$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

Tiếp theo ta sẽ xác định kết quả của phương pháp Schulze. Chẳng hạn, khi so sánh hai ứng cử viên $A$ và $B$ , ta thấy ứng cử viên $A$ tốt hơn hơn ứng cử viên $B$ vì $(28=)p[A,B]>p[B,A](=25)$ . Trong một ví dụ khác, ứng cử viên $E$ tốt hơn hơn ứng cử viên $D$ vì $(31=)p[E,D]>p[D,E](=24)$ . Tiếp tục lặp lại việc so sánh, ta kết luận rằng thứ hạng được tính toán theo phương pháp Schulze là $E>A>C>B>D$ và người chiến thắng là ứng cử viên $E$ . Nói cách khác, ứng cử viên $E$ chiến thắng vì $p[E,X]>p[X,E]$ với mọi ứng cử viên X.