Định lý lũng đoạn (
manipulation theorem), được Gibbard và Satterthwaite thiết lập vào thập kỷ 1970, là một trong những định lý thú vị nhất về lý thuyết bầu cử. Nói một cách nôm na, định lý này nói rằng mọi hệ thống bầu cử dân chủ đều có thể bị lũng đoạn ! Định lý này và
"định lý không thể" của Arrow khá gần nhau về triết lý, và có cách tiếp cận định lý lũng đoạn từ định lý Arrow. Nhưng ở đây tôi sẽ thử trình bầy định lý lũng đoạn một cách trực tiếp, không qua định lý Arrow, dựa theo một bài báo năm 2000 của ông
Lars-Gunnar Svensson, GS kinh tế đai học Lund (Thụy Điển): The Proof of the Gibbard-Satterthwaite Theorem Revisited (2000), và một bài báo của Barberá và Peleg: Strategy-proof Voting Schemes with Coninuous Preferences, Social Choice and Welfare, 7:31–38 (1990).
Để phát biểu trên trở thành định lý mang tính toán học với chứng minh chặt chẽ, đầu tiên ta cần có phát biểu rõ ràng, và định nghĩa rõ ràng thế nào là lũng đoạn trong bầu cử được xét đến ở đây.
Hình dung là ta có $1$ tập $n$ cử tri $N = {1,2,…,n}$, cần bầu chọn ra một (và chỉ một) trong số $m $các lựa chọn $D = {D_1, …, D_m}$. Ví dụ như $D_1$ là không làm gì cả, $D_2$ là trả nợ nước ngoài, $D_3$ là không trả nợ mà vay thêm, $D_4$ là trả nợ một phần, v.v... Ta sẽ giả sử là số lựa chọn $m \ge 3$. (Trong trường hợp chỉ có 2 lựa chọn, thì có một nguyên tắc bầu đơn giản và hiệu quả là: lựa chọn nào có số phiếu nhiều hơn thì thắng).
Với mỗi cử tri thứ $i$, có một hàm ${u_i} : D \to \mathbb{R}$ gọi là hàm thỏa dụng của cử tri thứ $i$. Hàm đó mô tả mức độ thiệt/lợi hay thích/không thích của cử tri thứ $i$ đối với các lựa chọn. Nếu chẳng hạn ${u_1}\left( {{D_1}} \right) = 3,\,\,{u_1}\left( {{D_2}} \right) = - 2,\,\,{u_1}\left( {{D_3}} \right) = 5$, thì cử tri thứ nhất thích $D_1$, nhưng thích $D_3$ hơn là $D_1$, và ghét $D_2$, vì $D_3$ đem lại lợi lộc (hay sung sướng) cho cử tri đó, còn $D_1$ đem lại thiệt hại (hay đau buồn). Ta sẽ giả sử là các hàm thỏa dụng là đơn ánh, tức là không có hai lựa chọn nào được một cử tri nào đánh giá là tốt bằng nhau, mà cử tri luôn có đánh giá lựa chọn này tốt hơn lựa chọn kia. Ký hiệu $U$ là tập tất cả các hàm thỏa dụng có thể (tức là tập tất cả các đơn ánh từ $D$ vào tập các số thực), và $U = {U^n}$ là tập tất cảc bộ $n$ hàm thỏa dụng đồng thời của $n$ cử tri. Mỗi phần tử của gọi là một
tình huống bầu (preference profile).
Một hệ thống (nguyên tắc) bầu cử là một ánh xạ: $f:U \to D$. Hiểu nó là, dựa trên sự đánh giá độ thỏa dụng của toàn bộ các cử tri đối với các lựa chọn, mà xã hội bầu ra 1 lựa chọn. Nguyên tắc bầu cử $f$ được gọi là
có thể bị lũng đoạn (manipulable), nếu như tồn tại một tình huống $u = \left( {{u_1},...,{u_n}} \right) \in U$, và một cử tri thứ $i$ với một "hàm thỏa dụng giả vờ" ${u_i}^\prime \ne {u_i}$, sao cho ${u_i}\left( {f\left( {u'} \right)} \right) > {u_i}\left( {f\left( u \right)} \right)$ trong đó $u' = \left( {{u_i}^\prime ,{u_{ - i}}} \right)$ được tạo bởi $u$ bằng cách thay ${u_i}$ bằng ${u_i}^\prime $
Bất đẳng thức ${u_i}\left( {f\left( {u'} \right)} \right) > {u_i}\left( {f\left( u \right)} \right)$ được hiểu là: bằng cách không bầu theo đúng hàm thỏa dụng thực ${u_i}$ của mình mà bầu theo một hàm thỏa dụng "đánh lừa" khác ${u_i}^\prime $, cử tri thứ $i$ có thể tác động vào kết quả bầu cử để làm tăng độ thỏa dụng của mình lên. Việc bầu trái với nguyện vọng thật của mình (thay ${u_i}$ bằng ${u_i}^\prime$) nhằm đạt kết quả bầu cử có lợi hơn theo nguyện vọng thật của mình gọi là một sự lũng đoạn bầu cử, hay có cách gọi dùng mỹ từ là
strategic voting (bầu có chiến lược). Một nguyên tắc bầu cử mà trong đó không có cơ hội lũng đoạn như vậy, thì được gọi là
strategy-proof.Một nguyên tắc bầu cử $f$ được gọi là có
độc tài, nếu như tồn tại một cử tri thứ $i$ (kẻ độc tài) sao cho ${u_i}\left( {f\left( u \right)} \right) = \sup \left\{ {{u_i}\left( {{D_1}} \right),...,{u_i}\left( {{D_m}} \right)} \right\}$ với mọi $u = \left( {{u_1},...,{u_n}} \right) \in U$, có nghĩa là lựa chọn của kẻ độc tài luôn được lấy làm lựa chọn chung, bất kể những người khác nghĩ ra sao.
Một nguyên tắc bầu cử $f$ được gọi là
onto, hay nói một cách dễ hiểu hơn là mọi ứng cử viên đều có thể được bầu, nếu như với mọi lựa chọn ${D_j} \in D$ tồn tại tình huống $u \in U$ sao cho kết quả bầu cử trong tình huống đó là ${D_j}:f(u)={D_j}$
Định lý Gibbard-Satterthwaite: Mọi nguyên tắc bầu cử $f$ bất kỳ có tính onto và với tập các lựa chọn gồm ít nhất $3$ phần tử, thì hoặc là có độc tài hoặc là có thể bị lũng đoạn.Sơ lược chứng minh định lý:
Bổ đề 1 (tính đơn điệu): Giả sử $f$ là strategy-proof, $u,v \in U$ sao cho $f(u) = {D_j}$ và với mọi cử tri thứ $i$ và lựa chọn thứ $k$ ta đều có ${v_i}\left( {{D_j}} \right) \ge {v_i}\left( {{D_k}} \right)$ nếu ${u_i}\left( {{D_j}} \right) \ge {u_i}\left( {{D_k}} \right)$. Khi đó $f(v) = f(u)$.
Chứng minh: Ta sẽ chứng minh khẳng định trên cho $v$ thỏa mãn ${v_i} = {u_i}$ với mọi $i \ne 1$ (từ đó theo qui nạp sẽ suy ra khẳng định với mọi $v$ khác thỏa mãn điều kiện của bổ đề). Đặt $f(v) = {D_h}$. Khi thay $u$ bằng $v$, thì theo giả thiết strategy-proof, điều này phải làm cho ${u_1}\left( f \right)$ giảm đi hoặc giữ nguyên chứ không tăng lên, tức là ta phải có ${u_1}\left( {{D_j}} \right) \ge {u_1}\left( {{D_h}} \right)$. Theo giả thiết đơn điệu (điều kiện: ${v_i}\left( {{D_j}} \right) \ge {v_i}\left( {{D_k}} \right)$ nếu ${u_i}\left( {{D_j}} \right) \ge {u_i}\left( {{D_k}} \right)$), ta cũng có ${v_1}\left( {{D_j}} \right) \ge {v_1}\left( {{D_h}} \right)$. Vẫn theo giả thiết strategy-proof, việc thay $v$ bằng $u$ không làm tăng ${v_1}\left( f \right)$, tức là ta phải có bất đẳng thức ngược lại ${v_1}\left( {{D_h}} \right) \ge {v_1}\left( {{D_j}} \right)$. Có nghĩa là ${v_1}\left( {{D_h}} \right) = {v_1}\left( {{D_j}} \right)$ và $f\left( v \right) = {D_h} = {D_j} = f\left( u \right)$ vì ${v_1}$ là đơn ánh.
Bổ đề 2 (tối ưu Pareto): Giả sử $f$ là strategy-proof và onto, và giả sử ${D_j} \ne {D_k}$ là hai lựa chọn khác nhau, và $u$ là một tình huống bầu, sao cho ${u_i}\left( {{D_j}} \right) > {u_i}\left( {{D_k}} \right)$ với mọi $i$. Khi đó $f\left( u \right) \ne {D_k}$
Chứng minh bằng phản chứng. Giả sử $f\left( u \right) = {D_k}$. Theo tính chất onto, tồn tại $v$ sao cho $f\left( v \right) = {D_j}$. Lấy một tình huống bầu $w$ bất kỳ thỏa mãn tính chất sau: ${w_i}\left( {{D_j}} \right) > {w_i}\left( {{D_k}} \right) > {w_i}\left( {{D_h}} \right)$ với mọi $h \ne j,k$. Khi đó theo tính đơn điệu (bổ đề 1) ta phải có $f\left( w \right) = f\left( u \right) = {D_k}$ và cũng phải có $f\left( w \right) = f\left( v \right) = {D_j}$, là điều mâu thuẫn.
Chứng minh định lý trong trường hợp $n=2$ (hai cử tri): Giả sử $f$ là strategy-proof và onto. Ta sẽ chứng minh là nó có độc tài. Gọi $u = \left( {{u_1},{u_2}} \right)$ là một tình huống bầu thỏa mãn điều kiện ${u_1}\left( {{D_1}} \right) > {u_1}\left( {{D_2}} \right) > {u_1}\left( {{D_k}} \right)$ và ${u_2}\left( {{D_2}} \right) > {u_2}\left( {{D_1}} \right) > {u_2}\left( {{D_k}} \right)$ với mọi $k \ge 3$. Khi đó, theo tối ưu Pareto (bổ đề 2), ta có $f\left( u \right) = {D_1}$ hoặc $f\left( u \right) = {D_2}$. Ta sẽ giả sử $f\left( u \right) = {D_1}$.
Gọi ${v_2}$ là một hàm thỏa dụng sao cho ${v_2}\left( {{D_2}} \right) > {v_2}\left( {{D_k}} \right) > {v_2}\left( {{D_1}} \right)$ với mọi $k \ge 3$. Khi đó, theo giả thiết strategy-proof ta có $f\left( {{u_1},{v_2}} \right) \ne {D_2}$, và theo tối ưu Pareto ta có không thể bằng với . Do vậy Từ đó suy ra theo tính đơn điệu (bổ đề 1) là với mọi tình huống bầu $w$ sao cho ${w_1}\left( {{D_1}} \right) = {\max _j}{w_1}\left( {{D_j}} \right)$ ta cũng có $f\left( w \right) = {D_1}$. (tức là kết quả bầu cử luôn là ${D_1}$ trong trường hợp người thứ nhất chọn ${D_1}$ hàng đầu).
Thay vì lấy cặp lựa chọn $\left( {{D_1},{D_2}} \right)$, ta lấy tất cả các cặp lựa chọn $\left( {{D_i},{D_j}} \right)$ có thể $i \ne j$, và làm như trên, ta được hai tập hợp con ${Z_1},{Z_2}$ của tập các lựa chọn $D$: các lựa chọn trong ${Z_i}$ là các lựa chọn mà nếu cử tri thứ $i$ chọn nó hàng đầu thì kết quả bầu cử sẽ là nó. Ta có ${D_1} \in {Z_1}$ theo các giả sử phía trên. Tập ${Z_i}$ không thể chứa phần tử nào ngoài ${D_1}$ vì chằng hạn nếu ${D_3} \in {Z_2}$, thì trong tình huống bầu $w$ mà cử tri thứ nhất chọn $D_1$ hàng đầu và cử tri thứ hai chọn $D_3$ hàng đầu, thì kết quả bầu $f\left( w \right)$ vừa là $D_1$ vừa là $D_3$, mâu thuẫn. Trong hai tình huống ${D_2},{D_3}$ có ít nhất một tình huống thuộc ${Z_1}$ hoặc ${Z_2}$, và như vậy nó thuộc ${Z_1}$, và ${Z_2}$ cũng không thể chứa tình huống nào khác tình huống đó theo lý luận tương tự như trên. Suy ra là ${Z_2}$ là tập rỗng. Gọi $w$ là một tình huống bầu sao cho ${w_1}\left( {{D_2}} \right) > {w_1}\left( {{D_1}} \right) > {w_1}\left( {{D_k}} \right)$ và ${u_2}\left( {{D_1}} \right) > {u_2}\left( {{D_2}} \right) > {u_2}\left( {{D_k}} \right)$ với mọi $k \ge 3$. Theo các lý luận tương tự như trên, ta suy ra ${D_2} \in {Z_1}$ hoặc ${D_1} \in {Z_2}$, nhưng ${Z_2}$ rỗng nên ${D_2} \in {Z_1}$. Tương tự như vậy, mọi phần tử của $D$ đều thuộc ${Z_1}$, chứng tỏ cử tri thứ nhất là độc tài.
Quy nạp theo $\mathbf{n}$: Giả sử là định lý đã được chứng minh khi có $n = p \ge 2$ cử tri. Ta sẽ chứng minh nó cũng đúng khi số cử tri là $n=p+1$. Gọi $g$ là nguyên tắc bầu cử với $2$ cử tri định nghĩa như sau: $g\left( {{u_1},{u_2}} \right) = f\left( {{u_1},{u_2},...,{u_2}} \right)$ (với ${u_2}$ lặp lại $p$ lần). Với giả sử là $f$ là onto và strategy-proof, dễ thấy là $g$ cũng có các tính chất onto (dựa theo bổ đề 2) và strategy-proof. Như vậy $g$ có độc tài. Nếu độc tài của $g$ là cử tri thứ nhất, thì dễ thấy cử tri thứ nhất cũng là độc tài của $f$, còn nếu là cử tri thứ hai, thì cử tri thứ nhất của $f$ "không đọ lại được với nhóm còn lại", và có thể chuyển về trường hợp chỉ có $p$ cử tri bằng cách cố định là phiếu của cử tri thứ nhất để tìm ra độc tài của $f$. (Cần lý luân thêm một chút ở đây, việc này dành cho bạn đọc làm bài tập).
Ghi chú: Nếu luật bầu cử cho phép hòa (tức là kết quả có thể là vài phương án đều cùng được bầu là tốt nhất, sau đó có thể bắt thăm ngẫu nhiên xem chọn cái nào), thì định lý Gibbard-Satterthwaite không còn đúng?!
