Bài 22: Bầu cử và các cách đếm phiếu – Nghịch lý Condorcet và định lý Arrow

Lớp bạn bình chọn nơi đi dã ngoại: biển, núi hay hồ. Bạn có tin rằng chỉ cần đổi cách đếm phiếu, kết quả có thể thay đổi – dù không ai đổi ý? Toán học về bầu cử cho thấy những điều rất bất ngờ.

Bài thứ hai mươi hai của chuyên mục "Thuật toán trong đời sống": các thuật toán đếm phiếu. Bài viết chỉ bàn về toán học, không bình luận về bất kỳ cuộc bầu cử chính trị nào.

1. Bốn cách đếm phiếu

Mỗi bạn xếp hạng 3 lựa chọn: A (biển), B (núi), C (hồ).

Cách đếm	Quy tắc
Đa số tương đối	Chỉ đếm lựa chọn số 1; ai nhiều phiếu nhất thắng
Borda	Hạng 1 được 2 điểm, hạng 2 được 1 điểm, hạng 3 được 0 điểm; cộng điểm
Đối đầu từng cặp (Condorcet)	So từng cặp: bao nhiêu người thích A hơn B…; ai thắng tất cả các cặp là người thắng Condorcet
Loại dần (IRV)	Đếm lựa chọn số 1; nếu chưa ai quá bán, loại người ít phiếu nhất và chuyển phiếu sang lựa chọn tiếp theo

Cách Borda do Jean-Charles de Borda trình bày trước Viện Hàn lâm Khoa học Pháp năm 1770. Cách loại dần đang được dùng thật: ví dụ bầu Hạ viện Úc (từ năm 1918), một số cuộc bầu cử ở bang Maine và các cuộc bầu cử sơ bộ ở thành phố New York (Mỹ).

2. Thử nghiệm: đổi cách đếm, đổi người thắng

Bốn cách đếm phiếu

#include <bits/stdc++.h>
using namespace std;
// Mỗi phiếu: thứ tự ưu tiên 3 phương án (0 = A biển, 1 = B núi, 2 = C hồ) và số người
struct Ballot { array<int,3> order; int k; };
int main(){
    vector<Ballot> b = {{{0,1,2},4}, {{1,2,0},3}, {{2,0,1},2}};
    const char* nm = "ABC";
    // Đối đầu từng cặp: x thắng y nếu nhiều người xếp x trên y hơn
    for(int x = 0; x < 3; x++) for(int y = x + 1; y < 3; y++){
        int nx = 0, ny = 0;
        for(auto& p : b){
            int px = find(p.order.begin(), p.order.end(), x) - p.order.begin();
            int py = find(p.order.begin(), p.order.end(), y) - p.order.begin();
            (px < py ? nx : ny) += p.k;
        }
        printf("%c vs %c: %d - %d -> %c thang\n", nm[x], nm[y], nx, ny, nx > ny ? nm[x] : nm[y]);
    }
}

from itertools import combinations
from collections import Counter

def plurality(ballots):
    c = Counter()
    for order, k in ballots: c[order[0]] += k          # chỉ đếm lựa chọn số 1
    return dict(c)

def borda(ballots):
    c = Counter()
    for order, k in ballots:                            # hạng 1: 2 điểm, hạng 2: 1 điểm, hạng 3: 0
        for i, o in enumerate(order): c[o] += k * (len(order) - 1 - i)
    return dict(c)

def pairwise(ballots, opts):
    res = {}
    for x, y in combinations(opts, 2):                  # đối đầu từng cặp
        nx = sum(k for order, k in ballots if order.index(x) < order.index(y))
        res[f"{x}-{y}"] = (nx, sum(k for _, k in ballots) - nx)
    return res

def instant_runoff(ballots, opts):
    alive = set(opts)
    while True:                                         # loại dần phương án ít phiếu nhất
        c = Counter({o: 0 for o in alive})
        for order, k in ballots: c[next(o for o in order if o in alive)] += k
        top, v = c.most_common(1)[0]
        if v * 2 > sum(c.values()): return top
        alive.remove(min(c, key=c.get))

opts = ["A", "B", "C"]                                  # A = biển, B = núi, C = hồ
vd1 = [(["A", "B", "C"], 4), (["B", "C", "A"], 3), (["C", "B", "A"], 2)]
vd2 = [(["A", "B", "C"], 4), (["B", "C", "A"], 3), (["C", "A", "B"], 2)]
for name, b in [("Vi du 1", vd1), ("Vi du 2", vd2)]:
    print(name)
    print("  Da so tuong doi:", plurality(b))
    print("  Borda:", borda(b))
    print("  Doi dau tung cap:", pairwise(b, opts))
    print("  Loai dan (IRV):", instant_runoff(b, opts))

Kết quả chạy (bản Python; bản C++ in phần đối đầu từng cặp của ví dụ 2):

Vi du 1
  Da so tuong doi: {'A': 4, 'B': 3, 'C': 2}
  Borda: {'A': 8, 'B': 12, 'C': 7}
  Doi dau tung cap: {'A-B': (4, 5), 'A-C': (4, 5), 'B-C': (7, 2)}
  Loai dan (IRV): B
Vi du 2
  Da so tuong doi: {'A': 4, 'B': 3, 'C': 2}
  Borda: {'A': 10, 'B': 10, 'C': 7}
  Doi dau tung cap: {'A-B': (6, 3), 'A-C': (4, 5), 'B-C': (7, 2)}
  Loai dan (IRV): A

Ví dụ 1: nếu chỉ đếm lựa chọn số 1, A (biển) thắng với 4 phiếu. Nhưng khi đối đầu từng cặp, đa số (5/9) thích B hơn A và cũng thích B hơn C. Borda và loại dần đều chọn B. Cách đếm đơn giản nhất lại chọn phương án mà đa số không thích bằng B!

3. Nghịch lý Condorcet

Ví dụ 2 còn kỳ lạ hơn: A thắng B (6–3), B thắng C (7–2), nhưng C lại thắng A (5–4). Sở thích của tập thể tạo thành vòng tròn A > B > C > A, dù sở thích của từng người đều rất "logic". Hiện tượng này được Hầu tước de Condorcet mô tả trong tác phẩm năm 1785, gọi là nghịch lý Condorcet.

Với đồ thị có hướng "X thắng Y", nghịch lý Condorcet chính là đồ thị có chu trình. Người thắng Condorcet tồn tại khi có một đỉnh có cạnh đi tới tất cả các đỉnh khác.

4. Định lý bất khả thi của Arrow

Năm 1951, nhà kinh tế học Kenneth Arrow chứng minh: khi có từ 3 lựa chọn trở lên, không tồn tại cách gộp xếp hạng nào đồng thời thỏa mãn một số điều kiện "công bằng" rất hợp lý (như không có "nhà độc tài" quyết định thay tất cả, và kết quả giữa hai phương án không bị ảnh hưởng bởi phương án thứ ba). Arrow nhận giải Nobel Kinh tế năm 1972 cho các đóng góp về lý thuyết cân bằng tổng quát và kinh tế học phúc lợi.

5. Bạn học được gì từ đây?

• Cùng một dữ liệu, thuật toán khác nhau cho kết quả khác nhau – hãy luôn hỏi "cách tính là gì?".
• Phát hiện chu trình, đếm và so sánh từng cặp là những kỹ thuật cơ bản trên đồ thị.
• Toán học có thể chứng minh một điều là không thể – và đó cũng là một kết quả quan trọng.

Bài tập luyện tập

• CSES – Round Trip II (tìm chu trình trong đồ thị có hướng)
• CSES – Course Schedule (sắp xếp tô-pô – khi nào xếp hạng được?)
• Viết chương trình nhận các lá phiếu và in ra có người thắng Condorcet hay không.

📖 ĐỌC TIẾP: THUẬT TOÁN TRONG ĐỜI SỐNG

Bài 23: Shazam nhận ra bài hát trong vài giây như thế nào? Dấu vân tay âm thanh và bảng băm

Đọc tiếp: Shazam & bảng băm →

← Bài trước: chia tiền nhómXem tất cả 27 bài →

Nguồn tham khảo

• Stanford Encyclopedia of Philosophy – Social Choice Theory (Condorcet, Arrow)
• NobelPrize.org – Kenneth J. Arrow, Facts (1972)
• Borda – Mémoire sur les Élections au Scrutin (bản dịch Pulskamp)
• Australian Electoral Commission – History of electoral reform
• Maine Secretary of State – Ranked-choice voting FAQ
• NYC Board of Elections – Ranked Choice Voting