Bầu cử chẳng phải trò đùa: định lý lũng đoạn

 

Định lý lũng đoạn (manipulation theorem), được Gibbard 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 = {D1, …, Dm}. Ví dụ như D1 là không làm gì cả, D2 là trả nợ nước ngoài, D3 là không trả nợ mà vay thêm, D4 là trả nợ một phần, v.v. Ta sẽ giả sử là số lựa chọn m \geq 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(D_1) = 3, u_1(D_2) = -2, u_1(D_3) = 5, thì cử tri thứ nhất thích D1, nhưng thích D3 hơn là D1, và ghét D2, vì D3 đem lại lợi lộc (hay sung sướng) cho cử tri đó, còn D1 đ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à \mathcal{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 \mathcal{U} 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: \mathcal{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 = (u_1,\hdots,u_n) \in \mathcal{U}, và một cử tri thứ i với một “hàm thỏa dụng giả vờ” u_i' \neq u_i, sao cho

u_i (f(u') > u_i(f(u))

trong đó u' = (u_i', u_{-i}) được tạo bởi u bằng cách thay u_i bằng u_i'

Bất đẳng thức u_i (f(u') > u_i(f(u)) đượ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', 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') 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(f(u)) = \sup \{u_i(D_1),\hdots,u_i(D_m) \} với mọi u = (u_1,\hdots,u_n) \in \mathcal{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 \mathcal{U} sao cho kết quả bầu cử trong tình huống đó là Dj: 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 \mathcal{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(D_j) \geq v_i(D_k) nếu u_i(D_j) \geq u_i(D_k). 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 \neq 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(f) giảm đi hoặc giữ nguyên chứ không tăng lên, tức là ta phải có u_1 (D_h) \leq u_1 (D_j). Theo giả thiết đơn điệu (điều kiện: v_i(D_j) \geq v_i(D_k) nếu u_i(D_j) \geq u_i(D_k)), ta cũng có v_1 (D_h) \leq v_1 (D_j). Vẫn theo giả thiết strategy-proof, việc thay v bằng latex u không làm tăng v_1(f), tức là ta phải có bất đẳng thức ngược lại v_1 (D_h) \geq v_1 (D_j). Có nghĩa là v_1 (D_h) = (D_j),f(v) = D_h = D_j = f(u)v_1 là đơn ánh.

 Bổ đề 2 (tối ưu Pareto): Giả sử f là strategy-proof và onto, và giả sử D_j \neq 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(D_j) > u_i(D_k) với mọi i. Khi đó f(u) \neq D_k.

Chứng minh bằng phản chứng. Giả sử f(u) = D_k. Theo tính chất onto, tồn tại v sao cho f(v) = 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(D_j) > w_i(D_k) > w_i(D_h) với mọi h \neq j,k. Khi đó theo tính đơn điệu (bổ đề 1) ta phải có f(w) = f(u) = D_k và cũng phải có f(w) = f(v) = 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 = (u_1,u_2) là một tình huống bầu thỏa mãn điều kiện

u_1(D_1) > u_1 (D_2) > u_1 (D_k)u_2 (D_2) > u_2 (D_1) > u_2 (D_k)

với mọi k \geq 3. Khi đó, theo tối ưu Pareto (bổ đề 2), ta có f(u) = D_1 hoặc f(u) = D_2. Ta sẽ giả sử f(u) = D_1.

Gọi v_2 là một hàm thỏa dụng sao cho

v_2(D_2) > v_2(D_k) > v_2(D_1)

với mọi k \geq 3. Khi đó, theo giả thiết strategy-proof ta có f(u_1,v_2) \neq D_2, và theo tối ưu Pareto ta có f(u_1,v_2) không thể bằng D_k với k \geq 3. Do vậy f(u_1,v_2) = D_1. 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(D_1) = \max_j w_1(D_j) ta cũng có f(w) = D_1. (tức là kết quả bầu cử luôn là D1 trong trường hợp người thứ nhất chọn D1 hàng đầu).

Thay vì lấy cặp lựa chọn (D_1,D_2), ta lấy tất cả các cặp lựa chọn (D_i,D_j) có thể (i\neq 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_2 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 D1 hàng đầu và cử tri thứ hai chọn D3 hàng đầu, thì kết quả bầu f(w) vừa là D1 vừa là D3, 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(D_2)> w_1(D_1) > w_1(D_k)u_2(D_1) > u_2 (D_2) > u_2(D_k)

với mọi k \geq 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 n: Giả sử là định lý đã được chứng minh khi có n= p \geq 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(u_1,u_2) = f(u_1,u_2,\hdots,u_2)

(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 ?!

 

Print Friendly
 

Leave a Reply

  

  

  

You can use these HTML tags

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Spam Protection by WP-SpamFree