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 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 = {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 . (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 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 , 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à 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ạ: . 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 , và một cử tri thứ i với một “hàm thỏa dụng giả vờ” , sao cho

trong đó được tạo bởi bằng cách thay bằng

Bất đẳng thức được hiểu là: bằng cách không bầu theo đúng hàm thỏa dụng thực của mình mà bầu theo một hàm thỏa dụng “đánh lừa” khác , 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 bằng ) 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

với mọi ,

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 tồn tại tình huống sao cho kết quả bầu cử trong tình huống đó là Dj:

Đị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,  sao cho và với mọi cử tri thứ i và lựa chọn thứ k ta đều có nếu . Khi đó .

Chứng minh: Ta sẽ chứng minh khẳng định trên cho thỏa mãn với mọi (từ đó theo qui nạp sẽ suy ra khẳng định với mọi khác thỏa mãn điều kiện của bổ đề). Đặt . Khi thay bằng , thì theo giả thiết strategy-proof, điều này phải làm cho giảm đi hoặc giữ nguyên chứ không tăng lên, tức là ta phải có Theo giả thiết đơn điệu (điều kiện: nếu ), ta cũng có Vẫn theo giả thiết strategy-proof, việc thay bằng latex không làm tăng , tức là ta phải có bất đẳng thức ngược lại Có nghĩa là và vì là đơn ánh.

 Bổ đề 2 (tối ưu Pareto): Giả sử f là strategy-proof và onto, và giả sử là hai lựa chọn khác nhau, và là một tình huống bầu, sao cho với mọi . Khi đó

Chứng minh bằng phản chứng. Giả sử Theo tính chất onto, tồn tại sao cho Lấy một tình huống bầu bất kỳ thỏa mãn tính chất sau: với mọi Khi đó theo tính đơn điệu (bổ đề 1) ta phải có và cũng phải có , 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 là một tình huống bầu thỏa mãn điều kiện

và

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

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

với mọi . Khi đó, theo giả thiết strategy-proof ta có 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 sao cho ta cũng có (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 ta lấy tất cả các cặp lựa chọn có thể (), và làm như trên, ta được hai tập hợp con của tập các lựa chọn : các lựa chọn trong 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ó theo các giả sử phía trên. Tập không thể chứa phần tử nào ngoài vì chằng hạn nếu , thì trong tình huống bầu 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 vừa là D1 vừa là D3, mâu thuẫn. Trong hai tình huống có ít nhất một tình huống thuộc hoặc , và như vậy nó thuộc , và 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à là tập rỗng. Gọi là một tình huống bầu sao cho

và

với mọi . Theo các lý luận tương tự như trên, ta suy ra hoặc , nhưng rỗng nên Tương tự như vậy, mọi phần tử của $D$ đều thuộc , 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ó cử tri. Ta sẽ chứng minh nó cũng đúng khi số cử tri là . Gọi g là nguyên tắc bầu cử với 2 cử tri định nghĩa như sau:

(với lặp lại 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ó 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 ?!