Toán ứng dụng và Tính toán

Lý thuyết lựa chọn xã hội

Nghiên cứu cách các sở thích cá nhân kết hợp thành quyết định tập thể, bao gồm hệ thống bầu cử.

Trực giácBa người bạn, ba nhà hàng yêu thích, và không có cách nào công bằng để chọn một

Ánh thích sushi hơn pizza hơn taco. Bình thích pizza hơn taco hơn sushi. Cúc thích taco hơn sushi hơn pizza. Hỏi cả nhóm ba người thích nhà hàng nào hơn, bằng cách so sánh từng cặp qua biểu quyết đa số: đa số (Ánh và Cúc) thích sushi hơn pizza; đa số (Ánh và Bình) thích pizza hơn taco; nhưng đa số (Bình và Cúc) lại thích taco hơn sushi. Sở thích của nhóm tạo thành một chu trình — sushi thắng pizza thắng taco thắng sushi — dù mỗi cá nhân đều có một thứ tự sở thích hoàn toàn nhất quán. Lý thuyết lựa chọn xã hội nghiên cứu đúng khoảng cách này giữa sở thích duy lý của cá nhân và quyết định duy lý của tập thể, và hỏi khoảng cách đó có thể được thu hẹp đến đâu.

Ba cử tri, ba ứng viên: mỗi cử tri (bên trái) được nối với mọi ứng viên (bên phải), vì mỗi cử tri phải xếp hạng tất cả các ứng viên. Ngay cả với chỉ

3

cử tri và

3

ứng viên, đã có tới

(3!)^3 = 216

tổ hợp thứ tự xếp hạng cá nhân có thể mà một quy tắc lựa chọn xã hội phải xử lý nhất quán.

Một cách hình thức, mỗi cử tri $i$ báo cáo một thứ tự sở thích — một cách xếp hạng các phương án từ ưa thích nhất đến ít ưa thích nhất. Một hàm phúc lợi xã hội $F$ nhận toàn bộ hồ sơ các thứ tự xếp hạng cá nhân và trả ra một thứ tự xã hội duy nhất; một hàm lựa chọn xã hội nhận hồ sơ đó và trả ra một người thắng duy nhất. Cả hai loại quy tắc đều phải xử lý mọi hồ sơ khả dĩ về mặt logic, không chỉ những hồ sơ thuận tiện, và đó chính xác là điều khiến ví dụ nhà hàng ở trên trở thành một vấn đề thật sự chứ không phải một sự tình cờ.

Đại họcQuy tắc tổng hợp và bốn điều kiện của Arrow

Định nghĩa: Hàm phúc lợi xã hội và quan hệ đa số

Một hàm phúc lợi xã hội $F$ ánh xạ mọi hồ sơ các thứ tự sở thích cá nhân $(\succ_1, \dots, \succ_n)$ tới một thứ tự sở thích xã hội duy nhất $\succ$ . Quan hệ đa số là ứng viên tự nhiên: khẳng định $a \succ b$ về mặt xã hội đúng khi đa số cử tri xếp $a$ trên $b$ . Như ví dụ nhà hàng đã cho thấy, quan hệ đa số có thể không bắc cầu — nó có thể tạo thành chu trình thay vì xếp hạng các phương án từ tốt nhất đến tệ nhất.

a \succ b \iff \#\{i : a \succ_i b\} > \#\{i : b \succ_i a\}

Arrow đặt câu hỏi: có bất kỳ quy tắc nào, đa số hay khác, luôn cho ra một thứ tự xã hội bắc cầu trong khi thỏa mãn một danh sách ngắn các điều kiện công bằng tối thiểu hay không? Miền không hạn chế: quy tắc phải hoạt động với mọi hồ sơ xếp hạng cá nhân khả dĩ. Pareto yếu: nếu mọi cử tri xếp $a$ trên $b$ , xã hội cũng phải làm vậy. Độc lập với phương án không liên quan (IIA): thứ tự xã hội giữa $a$ và $b$ chỉ phụ thuộc vào cách các cá nhân xếp $a$ so với $b$ , không phụ thuộc vào vị trí của một phương án thứ ba $c$ nào đó. Không độc tài: không có sở thích của một cử tri duy nhất nào luôn quyết định thứ tự xã hội bất kể mọi người khác.

Ba quy tắc bầu cử, và mỗi quy tắc gặp rắc rối ở đâu
Quy tắc	Cách chọn người thắng	Luôn chọn người thắng Condorcet?	Chống thao túng?
Đa số tương đối (nhiều phiếu hạng nhất nhất)	Mỗi cử tri chọn một ứng viên yêu thích; nhiều phiếu nhất thắng	Không	Không
Đếm Borda	Xếp hạng trong $n$ phương án cho $n-1, n-2, \dots, 0$ điểm; tổng cao nhất thắng	Không	Không
Đa số theo cặp (phương pháp Condorcet)	So sánh mọi cặp trực tiếp bằng biểu quyết đa số	Có, khi tồn tại	Không

\text{Borda}(a) = \sum_{i=1}^{n} \big(m - \text{rank}_i(a)\big)

Nâng caoHai định lý bất khả

Định lý: Định lý bất khả của Arrow

Nếu có ít nhất $3$ phương án, hàm phúc lợi xã hội duy nhất thỏa mãn Miền không hạn chế, Pareto yếu, và Độc lập với phương án không liên quan là một chế độ độc tài: tồn tại một cử tri duy nhất $i$ sao cho thứ tự xã hội luôn bằng đúng thứ tự của cử tri $i$ .

Vì sao đúng?

Pareto và IIA nghe có vẻ khiêm tốn — chắc chắn phải có một quy tắc thông minh, không độc tài nào thỏa mãn cả hai mà vẫn cho ra một thứ tự nhất quán. Định lý của Arrow cho thấy trực giác này sai: bất cứ khi nào có từ $3$ phương án trở lên, hai điều kiện đó cùng nhau đã dồn toàn bộ sức mạnh tổng hợp vào một cử tri duy nhất, một khi tính bắc cầu cũng được yêu cầu.

Chứng minh

Phác thảo (lập luận cử tri then chốt). Cố định ba phương án $a, b, c$ . Gọi $a$ là "cực đoan" trong một hồ sơ nếu mọi cử tri xếp $a$ ở vị trí trên cùng hoặc dưới cùng trong danh sách của riêng họ, với thứ tự tùy ý giữa các phương án còn lại. Một lập luận ngắn dùng Pareto yếu và IIA — di chuyển từng phương án khác qua $a$ và kiểm tra rằng việc đó không thể bị chặn mà không vi phạm Pareto hay để thứ tự phụ thuộc vào vị trí của $a$ — cho thấy rằng bất cứ khi nào $a$ là cực đoan với mọi cử tri, xã hội cũng phải xếp $a$ ở vị trí trên cùng hoặc dưới cùng trong thứ tự của chính mình.

Bắt đầu từ hồ sơ mà mọi cử tri xếp $a$ ở dưới cùng; theo Pareto yếu, xã hội cũng xếp $a$ ở dưới cùng. Bây giờ cho các cử tri lần lượt chuyển sang xếp $a$ ở trên cùng, theo một thứ tự cố định, giữ cho $a$ luôn cực đoan ở mỗi bước. Theo sự kiện cực đoan ở trên, ở mỗi bước thứ tự xã hội của $a$ vẫn là trên cùng hoặc dưới cùng, và Pareto buộc nó phải là trên cùng khi mọi người đã chuyển xong. Vậy có một cử tri đầu tiên, gọi là $n^\ast$ , mà sự chuyển đổi của họ lật thứ tự xã hội của $a$ từ dưới cùng lên trên cùng — cử tri then chốt đối với $a$ .

Tiếp theo, chứng minh $n^\ast$ cũng có tính quyết định giữa $b$ và $c$ — không chỉ về $a$ . Xây một hồ sơ mới trong đó $n^\ast$ xếp $b$ trên $a$ trên $c$ , những cử tri đứng trước $n^\ast$ trong thứ tự chuyển đổi xếp $a$ ở trên cùng (nên thứ tự tương đối của họ giữa $b, c$ có thể đặt tự do), và những người còn lại xếp $a$ ở dưới cùng. So sánh hồ sơ này với hai hồ sơ dùng để định nghĩa tính then chốt, IIA suy ra xã hội xếp $b$ trên $a$ (từ phía $a$ -trên-cùng) và $a$ trên $c$ (từ phía $a$ -dưới-cùng), do đó $b$ trên $c$ theo tính bắc cầu — khớp đúng với thứ tự riêng của $n^\ast$ giữa $b$ và $c$ , bất kể người khác xếp chúng thế nào.

Lặp lại lập luận này cho mọi cặp phương án cho thấy sở thích của $n^\ast$ luôn quyết định sở thích của xã hội: $n^\ast$ là một nhà độc tài. Điều này mâu thuẫn với Không độc tài, nên không quy tắc nào có thể thỏa mãn đồng thời Miền không hạn chế, Pareto yếu, và IIA mà không đồng thời độc tài.

Định lý: Định lý Gibbard–Satterthwaite

Xét một hàm lựa chọn xã hội chọn ra đúng một người thắng từ ít nhất $3$ phương án, với mọi hồ sơ xếp hạng cử tri khả dĩ, sao cho mọi phương án đều thực sự có thể thắng ở một hồ sơ nào đó (toàn ánh). Nếu hàm đó chống thao túng — không cử tri nào có thể đạt kết quả tốt hơn (theo thứ tự thật của họ) bằng cách báo cáo một thứ tự sai — thì nó phải là một chế độ độc tài: lựa chọn hàng đầu của một cử tri nào đó luôn là người thắng.

Vì sao đúng?

Các hệ thống bầu cử theo thứ tự thường được quảng cáo là chống được bỏ phiếu chiến lược. Gibbard–Satterthwaite cho thấy điều ngược lại gần như không thể tránh khỏi: ngay khi một quy tắc chọn ra đúng một người thắng từ $3$ phương án trở lên, được định nghĩa cho mọi hồ sơ, cho phép mọi phương án đôi khi thắng, và không phải chế độ độc tài, thì chắc chắn có một tình huống nào đó mà một cử tri hưởng lợi từ việc nói dối về sở thích của mình.

Chứng minh

Phác thảo (quy về định lý Arrow). Trước tiên, một bổ đề đơn điệu: nếu phương án $a$ thắng ở một hồ sơ nào đó, và hồ sơ chỉ thay đổi bởi việc một số cử tri nâng $a$ lên cao hơn trong thứ tự riêng của họ (không sắp xếp lại các phương án khác theo cách khác), $a$ vẫn phải thắng. Nếu không, một cử tri có thứ tự thật là hồ sơ "trước" có thể báo cáo sai thành hồ sơ "sau" để đẩy $a$ từ thua sang thắng, hoặc ngược lại — dù theo cách nào cũng mâu thuẫn với tính chống thao túng đối với ai đó.

Tiếp theo, dùng hàm lựa chọn để xây một thứ tự xã hội suy ra cho mỗi hồ sơ: khẳng định $a$ trên $b$ trong thứ tự suy ra đúng khi $a$ vẫn thắng sau khi mọi phương án khác ngoài $a$ và $b$ bị xóa khỏi lá phiếu của mọi cử tri, chỉ còn lại một cuộc đua trực tiếp hai bên. Tính toàn ánh và tính chống thao túng của hàm lựa chọn gốc, cùng với bổ đề đơn điệu, có thể được dùng để kiểm tra rằng thứ tự suy ra này thỏa mãn Miền không hạn chế, Pareto yếu, và Độc lập với phương án không liên quan với tư cách một hàm phúc lợi xã hội.

Theo Định lý bất khả của Arrow, vì có ít nhất $3$ phương án, thứ tự xã hội suy ra này phải độc tài: thứ tự của một cử tri $i$ nào đó luôn bằng thứ tự xã hội suy ra.

Cuối cùng, kiểm tra rằng lựa chọn hàng đầu của chính cử tri $i$ này luôn là người thắng của hàm lựa chọn xã hội gốc: vì thứ tự suy ra đặt phương án yêu thích của $i$ trên mọi phương án khác, và thứ tự suy ra theo dõi ai thắng trong so sánh từng cặp, lựa chọn yêu thích của $i$ phải là người thắng chung ở mọi hồ sơ. Vậy hàm lựa chọn xã hội chống thao túng, toàn ánh ban đầu bị chi phối bởi cử tri $i$ .

Nâng caoỨng dụng thực tiễn và Ví dụ minh họa

Lý thuyết lựa chọn xã hội định hình các thể chế thật: ủy ban bầu cử quốc gia chọn giữa hệ thống đa số tương đối, bầu cử theo thứ tự, và hệ thống tỷ lệ trong khi biết rõ mỗi hệ thống chấp nhận rủi ro thao túng và nghịch lý nào; các ủy ban hay hội đồng giám khảo xếp hạng ứng viên hoặc đề xuất bằng đếm Borda hay so sánh từng cặp cũng thừa hưởng cùng những đánh đổi đó; và các hệ thống gợi ý cũng như các nhà nghiên cứu căn chỉnh AI nay coi việc kết hợp sở thích của nhiều người dùng hay nhiều bộ đánh giá AI thành một xếp hạng duy nhất là một bài toán lựa chọn xã hội trá hình, thừa hưởng luôn cả những cảnh báo của Arrow và Gibbard–Satterthwaite.

Ví dụ: Tìm người thắng theo đếm Borda

Ba cử tri xếp hạng ba ứng viên $X, Y, Z$ như sau. Cử tri 1: $X \succ Y \succ Z$ . Cử tri 2: $Y \succ Z \succ X$ . Cử tri 3: $Y \succ X \succ Z$ . Với $m = 3$ ứng viên, hạng nhất được $2$ điểm, hạng nhì được $1$ điểm, và hạng chót được $0$ điểm. Ai thắng theo đếm Borda?

Lời giải

Tính điểm của $X$ : Cử tri 1 xếp $X$ hạng nhất ( $2$ điểm), Cử tri 2 xếp $X$ hạng chót ( $0$ điểm), Cử tri 3 xếp $X$ hạng nhì ( $1$ điểm). Tổng: $2 + 0 + 1 = 3$ .

Tính điểm của $Y$ : Cử tri 1 xếp $Y$ hạng nhì ( $1$ điểm), Cử tri 2 xếp $Y$ hạng nhất ( $2$ điểm), Cử tri 3 xếp $Y$ hạng nhất ( $2$ điểm). Tổng: $1 + 2 + 2 = 5$ .

Tính điểm của $Z$ : Cử tri 1 xếp $Z$ hạng chót ( $0$ điểm), Cử tri 2 xếp $Z$ hạng nhì ( $1$ điểm), Cử tri 3 xếp $Z$ hạng chót ( $0$ điểm). Tổng: $0 + 1 + 0 = 1$ .

$Y$ có tổng cao nhất, $5$ điểm, nên $Y$ thắng theo đếm Borda — dù $Y$ không phải lựa chọn hàng đầu tuyệt đối của bất kỳ ai, nó luôn được mọi người xếp gần vị trí cao.

Ví dụ: Một cử tri hưởng lợi từ việc nói dối, theo quy tắc đa số tương đối

Theo quy tắc đa số tương đối (mỗi cử tri chọn một ứng viên yêu thích; nhiều phiếu nhất thắng), giả sử $45$ cử tri thực sự thích $A \succ B \succ C$ , $40$ cử tri thực sự thích $B \succ C \succ A$ , và $15$ cử tri thực sự thích $C \succ B \succ A$ . Nếu ai cũng bỏ phiếu cho ứng viên yêu thích thật của mình, ai thắng, và liệu có cử tri nào trong nhóm $15$ người cuối có thể đạt kết quả tốt hơn bằng cách bỏ phiếu cho người khác ngoài ứng viên yêu thích thật $C$ của họ không?

Lời giải

Nếu mọi người bỏ phiếu trung thực: $A$ được $45$ phiếu, $B$ được $40$ phiếu, $C$ được $15$ phiếu. $A$ có nhiều phiếu nhất và thắng.

Nhưng $15$ cử tri thực sự thích $C \succ B \succ A$ lại xếp $A$ ở hạng chót. Theo quan điểm của họ, $A$ thắng là kết quả tệ nhất có thể.

Giả sử thay vào đó $15$ cử tri này bỏ phiếu không trung thực cho $B$ , lựa chọn thứ hai của họ, thay vì $C$ . Kết quả kiểm phiếu trở thành $A$ : $45$ , $B$ : $40 + 15 = 55$ , $C$ : $0$ . Bây giờ $B$ thắng.

Vì $15$ cử tri này thực sự xếp $B$ trên $A$ ( $B \succ_i A$ với mỗi người trong họ), việc chuyển phiếu từ ứng viên yêu thích thật $C$ sang $B$ đã thay đổi kết quả từ lựa chọn tệ nhất của họ ( $A$ ) sang một lựa chọn tốt hơn ( $B$ ) — đúng kiểu khai báo sai có lợi mà Gibbard–Satterthwaite đảm bảo phải tồn tại đối với bất kỳ quy tắc không độc tài nào có từ $3$ phương án trở lên.

Lỗi hay gặp. Một ngộ nhận thường gặp là chuyển từ đa số tương đối sang một hệ thống xếp hạng khác — bầu vòng loại tức thời, đếm Borda, hay bất kỳ sơ đồ khéo léo nào khác — cuối cùng sẽ tạo ra một quy tắc bầu cử miễn nhiễm với bỏ phiếu chiến lược. Gibbard–Satterthwaite loại trừ điều này nói chung: miễn là một quy tắc chọn một người thắng từ

3

phương án trở lên, được định nghĩa cho mọi hồ sơ, cho phép mọi phương án thắng ở một hồ sơ nào đó, và không phải chế độ độc tài, thì tồn tại một hồ sơ nào đó mà một cử tri nào đó hưởng lợi từ việc khai báo sai sở thích của mình. Câu hỏi thiết kế thực sự không phải là liệu thao túng có khả thi hay không, mà là nó hiếm đến mức nào, khó phát hiện ra sao, và tốn kém thế nào trong thực tế.

Ghi chú lịch sử

Các nghịch lý bỏ phiếu đơn lẻ có từ Condorcet năm 1785, nhưng phong cách tiên đề hóa hiện đại của lý thuyết lựa chọn xã hội chịu ảnh hưởng lớn từ cuốn sách năm 1944 Theory of Games and Economic Behavior của John von Neumann và Oskar Morgenstern, cho thấy sở thích duy lý trước các kết quả bất định có thể được nắm bắt bằng một tập nhỏ các tiên đề dẫn tới một hàm hữu dụng bằng số. Kenneth Arrow đã áp dụng đúng phong cách tiên đề hóa này — một danh sách ngắn các điều kiện tưởng chừng hợp lý, được xem xét về hệ quả chung của chúng — vào việc tổng hợp sở thích giữa người với người thay vì giữa các kết quả bất định, công bố định lý bất khả của ông năm 1951.

John von Neumann

Hiện trạng nghiên cứu tính đến năm 2026

Tính đến năm 2026, lý thuyết lựa chọn xã hội tính toán là một trong những nhánh hoạt động sôi nổi nhất của lĩnh vực này: thay vì hỏi liệu thao túng có khả thi về nguyên tắc hay không, các nhà nghiên cứu nghiên cứu xem nó khó về mặt tính toán đến mức nào, dựa trên quan sát năm 1989 của Bartholdi, Tovey và Trick rằng một số quy tắc bầu cử khiến việc tìm ra một cách thao túng có lợi trở thành NP-khó theo số ứng viên, để tính chống thao túng có thể được đánh đổi bằng tính khó thao túng ngay cả khi Gibbard–Satterthwaite cấm điều trước. Một hướng hoạt động thứ hai nghiên cứu các định dạng đầu vào phong phú hơn xếp hạng chặt chẽ — bỏ phiếu chấp thuận, bầu theo thứ tự có hòa, và bỏ phiếu bậc hai — hỏi kết quả bất khả nào còn đứng vững và kết quả nào được nới lỏng khi cử tri có thể diễn đạt cường độ, không chỉ thứ tự. Một hướng thứ ba, được thúc đẩy bởi các ứng dụng vào AI, coi việc căn chỉnh mô hình ngôn ngữ với sở thích của nhiều người đánh giá (như trong học tăng cường từ phản hồi con người) là một bài toán lựa chọn xã hội trá hình, nhập khẩu các tiên đề kiểu Arrow và hỏi phương pháp tổng hợp nào chống chịu tốt nhất trước thao túng và sự bất nhất quán mà lý thuyết lựa chọn xã hội cổ điển dự báo. Các câu hỏi mở gồm việc mô tả chính xác những miền sở thích bị hạn chế nào (ngoài trường hợp đơn đỉnh cổ điển) thoát khỏi định lý Arrow, và tìm các quy tắc tổng hợp có "độ méo" trường hợp xấu nhất chứng minh được là nhỏ so với sở thích định lượng không quan sát được.

Ba cử tri xếp hạng các ứng viên $P, Q$ : Cử tri 1: $P \succ Q$ . Cử tri 2: $P \succ Q$ . Cử tri 3: $Q \succ P$ . Theo quan hệ đa số, thứ tự xã hội giữa $P$ và $Q$ là gì?

Với $4$ ứng viên, một phiếu hạng nhất đáng bao nhiêu điểm Borda, theo quy ước hạng chót đáng $0$ điểm?

Định lý bất khả của Arrow cho thấy, với $3$ phương án trở lên, không hàm phúc lợi xã hội nào có thể thỏa mãn đồng thời Miền không hạn chế, Pareto yếu, Độc lập với phương án không liên quan, VÀ:

Theo định lý Gibbard–Satterthwaite, quy tắc bầu cử nào (chọn một người thắng từ $3$ ứng viên trở lên, được định nghĩa cho mọi hồ sơ, cho phép mọi ứng viên đôi khi thắng) có thể đảm bảo rằng KHÔNG cử tri nào từng hưởng lợi từ việc bỏ phiếu không trung thực?

Tài liệu tham khảo

Kenneth J. Arrow (1950). A Difficulty in the Concept of Social Welfare · DOI:10.1086/256963
Allan Gibbard (1973). Manipulation of Voting Schemes: A General Result · DOI:10.2307/1914083
Amartya Sen (1970). Collective Choice and Social Welfare