Toán học và Cuộc sống: "Cân bằng Nash" và "nghịch lý Braess"

Toán học và Cuộc sống: "Cân bằng Nash" và "nghịch lý Braess"

Tôi vừa đăng bài của bác , trong đó bác viết một đoạn có thể khó hiểu với nhiều người nên tôi viết thêm bài này để diễn giải. Bác Chu viết: "Dietrich Braess đã dẫn ra thí dụ cụ thể cho trường hợp 4.000 xe đi từ A đến D theo hai tuyến đường: tuyến 1 đi qua B: A-B-D và tuyến 2 đi qua C: A-C-D. Sau đó là mở thêm tuyến đường mới nối B-C. Dietrich Braess giả thiết thời gian đi đoạn đường rộng A-B và C-D mất 45 phút. Còn thời gian đi đoạn đường hẹp B-D và A-C cần X/100 phút, với X là số lượng xe đi trên đoạn đường này.

Braess đã chứng minh rằng tồn tại ‘Cân bằng Nash’ thứ nhất: Mọi tài xế đều mất 65 phút để đi từ A-D, mỗi tuyến có 2000 xe. Không ai có thể đơn phương đổi ngả để đi nhanh hơn, vì nếu tự ý chuyển sang ngả kia, ngả đó sẽ lên 2 001 xe và thời gian của họ sẽ tăng thành 65,01 phút. Khi mở thêm tuyến đường mới B-C thì tồn tại ‘Cân bằng Nash’ thứ hai: thời gian đi từ A-D mất 80 phút. Mô hình toán học trực quan của Braess đã chứng minh mở thêm tuyến đường mới B-C đã phá vỡ ‘Cân bằng Nash’ cũ (65 phú) và đẩy hệ thống vào một ‘Cân bằng Nash’ mới tệ hơn (80 phút).

Nghịch lý Braess nổi tiếng vì nó đi ngược trực giác: thêm một con đường nhưng tất cả mọi người lại đi chậm hơn. Tôi sẽ giải thích từng bước dựa theo hình ảnh dưới đây

1. Trước khi mở đường B-C

Ta có mạng lưới như hình bên trái, trong đó có các giả thiết sau:
A-B luôn mất 45 phút, bất kể có bao nhiêu xe.
C-D cũng luôn 45 phút.
A-C mất X/100 phút, X là số xe đi trên đoạn này.
B-D cũng mất X/100 phút.

Bác Chu giả sử có 4.000 xe từ A đến D. Mỗi xe chỉ có hai lựa chọn:
Tuyến 1: A → B → D
Tuyến 2: A → C → D
Nếu chia đều 2.000 xe đi theo tuyến A-B-D và 2.000 xe đi theo tuyến A-C-D

Khi đó đi tuyến A-B-D sẽ mất: A-B = 45 phút và B-D = 2000/100 = 20 phút. Tổng 45 + 20 = 65 phút

Theo chiều ngược lại, đi theo tuyến A-C-D, A-C = 20 phút và C-D =45 phút. Tổng 20 +45 = 65 phút. Như vậy thời gian đi theo hai tuyến bằng nhau.

2. Tại sao đây là Cân bằng Nash?

Giả sử một tài xế nghĩ: "Mình thử chuyển sang tuyến kia xem có nhanh hơn không.". Rồi anh ta làm thật. Khi đó tuyến kia sẽ có 2001 xe. Thời gian đi sẽ là 2001/100 = 20,01 phút.

Ví dụ anh ta chuyển sang tuyến A-C-D. Thời gian đi sẽ là 20,01 +45 = 65,01 phút

Kết quả là anh ta đi chậm hơn. Vì không ai muốn đi chậm hơn, nên không ai đổi tuyến. Trạng thái ổn định này gọi là Cân bằng Nash.

3. Sau khi mở đường B-C

Bây giờ xuất hiện một đường mới, hình bên phải. Bác Chu giả sử đường B-C rất ngắn, gần như 0 phút. Lúc này có thêm nhiều lựa chọn. Ví dụ theo tuyến A → B → C → D hoặc A → C → B → D

Điều gì xảy ra trong đầu các tài xế?

Nếu đi A-B-C-D: Mất 45 + 0 + 45 = 90 phút (Quá tệ, không ai đi).

Nếu đi A-C-B-D: Đoạn A-C và B-D phụ thuộc lượng xe (X/100), nhưng đoạn C-B là miễn phí (0 phút).

Vì tổng số xe chỉ là 4.000, nên thời gian tối đa của đoạn X/100 chỉ là 40 phút. Tài xế nào cũng tính toán: "Thà đi qua 2 đoạn đường hẹp nhưng hy vọng vắng vẻ còn hơn phải đi qua đoạn đường cố định 45 phút". Thế là, tâm lý ích kỷ khiến tất cả đều muốn né đoạn 45 phút và dồn vào đường tắt.

Nếu nhiều người tính toán ích kỷ, họ sẽ chọn những đoạn đường mà tại thời điểm họ quyết định có vẻ ít xe hơn. Kết quả là dần dần mọi người đều phát hiện một chiến lược có vẻ "khôn": đi qua cả hai đoạn đường phụ thuộc lưu lượng.

4. Kết cục

Cuối cùng, toàn bộ 4.000 xe đều chen chúc đi theo một lộ trình duy nhất: A → C → B → D. Lúc này:Đoạn A-C gánh 4.000 xe: mất 4000/100 = 40 phút.
Đoạn C-B (đường tắt): mất 0 phút.
Đoạn B-D gánh 4.000 xe: mất 4000/100 = 40 phút.

Tổng thời gian mỗi người phải chịu là: 40 + 0 + 40 = 80 phút. (Chậm hơn 15 phút so với trước khi có đường tắt!).

5. Tại sao không ai quay lại đường cũ?

Đây là điều nhiều người thắc mắc nhất. Giả sử bạn đang kẹt trong lộ trình 80 phút và nghĩ: "Hay mình quay lại đường cũ A-B-D?".

Nếu bạn quay lại A-B-D: A-B mất 45 phút. Đoạn B-D vẫn đang gánh 4.000 xe (mất 40 phút). Tổng: 45 + 40 = 85 phút (Chậm hơn!).

Nếu bạn đổi sang A-C-D: A-C vẫn 4.000 xe (mất ~40 phút). C-D mất 45 phút. Tổng: 40 + 45 = 85 phút (Cũng chậm hơn!).

Do đó, dù biết 80 phút là tệ, nhưng đổi sang đường nào cũng tệ hơn (85 hoặc 90 phút). Không ai muốn đổi. Đây lại là một Cân bằng Nash mới, nhưng là một trạng thái cân bằng tồi tệ.

6. Trực giác của nghịch lý

Điều quan trọng là trong cuộc sống, mỗi người đều tìm cách tối ưu cho bản thân chứ không ai quan tâm tới tối ưu cho toàn hệ thống.

Xét theo quan điểm hệ thống, nếu tất cả cùng hợp tác, họ có thể quay về phương án chia đều 2.000–2.000 xe và mỗi người chỉ mất 65 phút.

Nhưng vì ai cũng nghĩ "Tôi chỉ cần chọn đường có vẻ nhanh nhất cho tôi", nên cuối cùng tất cả cùng chậm lại. Đó chính là nghịch lý Braess.

7. Một ví dụ đời thường

Hãy tưởng tượng có hai quầy thanh toán ở siêu thị, mỗi quầy phục vụ như nhau. Khách tự chia đều nên mỗi người chờ khoảng 5 phút.

Bây giờ siêu thị mở thêm một lối đi nhỏ để khách có thể chuyển từ hàng này sang hàng kia ngay trước quầy.

Ai cũng nghĩ: "Bên kia có vẻ nhích nhanh hơn, mình đi lối tắt sang bên kia". Kết quả là lối đi tắt bị tắc nghẽn do quá nhiều người cố chen sang, đồng thời 2 hàng chính cũng bị rối loạn vì dòng người cứ nhảy qua nhảy lại. Cuối cùng, thời gian chờ trung bình của tất cả mọi người đều tăng lên. Đặc biệt là không ai muốn quay lại hàng cũ vì lúc họ nhìn thì hàng cũ cũng không ngắn hơn.

Đó chính là tinh thần của nghịch lý Braess: Thêm lựa chọn (thêm tài nguyên) không nhất thiết làm hệ thống hiệu quả hơn khi mỗi cá nhân chỉ hành động vì lợi ích riêng của mình.