Cân bằng Nash - Nash Equilibrium - Phạm Duy Tùng Machine Learning Blog

Cân bằng Nash: Khái niệm và ứng dụng

1. Cân bằng Nash là gì?

Cân bằng Nash (Nash Equilibrium) là một khái niệm trong lý thuyết trò chơi (game theory), được đặt theo tên của nhà toán học John Nash, người đã chứng minh sự tồn tại của cân bằng này trong các trò chơi không hợp tác (non-cooperative games). Cân bằng Nash mô tả một trạng thái mà mỗi người chơi trong trò chơi đều chọn chiến lược tối ưu nhất cho mình, dựa trên giả định rằng các đối thủ sẽ không thay đổi chiến lược của họ.

Định nghĩa chính xác: Một tập hợp các chiến lược của tất cả người chơi được gọi là cân bằng Nash nếu không có bất kỳ người chơi nào có thể cải thiện kết quả của mình bằng cách đơn phương thay đổi chiến lược của riêng mình.

2. Đặc điểm của cân bằng Nash

Tính ổn định: Trong trạng thái cân bằng Nash, không ai có động lực để thay đổi hành vi của mình vì họ đã đạt được lợi ích tốt nhất có thể.
Không phải luôn tối ưu Pareto: Cân bằng Nash không nhất thiết phải là giải pháp tốt nhất cho tất cả mọi người. Đôi khi, nó có thể dẫn đến “kết cục bi kịch” (tragedy of the commons) hoặc “hiệu ứng tù nhân” (Prisoner’s Dilemma).
Sự tồn tại: Theo định lý của Nash, mọi trò chơi hữu hạn với số lượng người chơi và chiến lược hữu hạn đều có ít nhất một cân bằng Nash (có thể ở dạng hỗn hợp, tức là sử dụng chiến lược ngẫu nhiên).

3. Ví dụ về cân bằng Nash

Ví dụ 1: Trò chơi “Chicken Game” (Trò chơi Gà con)

Hai tài xế lái xe lao thẳng vào nhau. Nếu cả hai từ chối nhường đường, họ sẽ đâm nhau và thiệt hại nặng nề. Nếu một người nhường đường (chạy thoát), người kia sẽ thắng cuộc.

Bảng trả thưởng:

	Người B nhường	Người B không nhường
Người A nhường	(0, 0)	(-1, +1)
Người A không nhường	(+1, -1)	(-10, -10)

Nếu cả hai chọn “không nhường”, họ rơi vào tình huống tệ nhất (-10, -10). Đây không phải là cân bằng Nash.
Nếu một người chọn “nhường” và người kia chọn “không nhường”, thì người không nhường sẽ có lợi (+1). Tuy nhiên, đây cũng không phải là cân bằng Nash vì người nhường có thể thay đổi chiến lược để tránh thiệt hại.
Cân bằng Nash xảy ra khi một người nhường và người kia không nhường, ví dụ: (Người A nhường, Người B không nhường) hoặc ngược lại.

Ví dụ 2: Trò chơi “Prisoner’s Dilemma” (Dilemma của Tù nhân)

Hai tù nhân bị bắt giữ và bị thẩm vấn riêng biệt. Họ có hai lựa chọn: “hợp tác” (giữ im lặng) hoặc “phản bội” (tố cáo người kia).

Bảng trả thưởng:

	Người B hợp tác	Người B phản bội
Người A hợp tác	(-1, -1)	(-10, 0)
Người A phản bội	(0, -10)	(-5, -5)

Nếu cả hai hợp tác, họ nhận án nhẹ (-1, -1).
Nếu một người phản bội và người kia hợp tác, người phản bội được tự do (0) còn người hợp tác chịu án nặng (-10).
Cân bằng Nash xảy ra khi cả hai phản bội (-5, -5), vì dù bên kia làm gì, phản bội vẫn là chiến lược tối ưu cá nhân.

4. Ứng dụng của cân bằng Nash

Cân bằng Nash có nhiều ứng dụng trong các lĩnh vực khác nhau, bao gồm:

4.1. Kinh tế học

Đấu giá và cạnh tranh thị trường: Các công ty trong thị trường cạnh tranh thường tìm cách đạt được cân bằng Nash bằng cách đưa ra mức giá và sản lượng tối ưu để tối đa hóa lợi nhuận.
Chiến lược định giá: Các công ty lớn như Amazon, Walmart, hay các hãng hàng không thường sử dụng cân bằng Nash để dự đoán hành vi của đối thủ và điều chỉnh chiến lược của mình.

4.2. Chính trị và quan hệ quốc tế

Đàm phán và xung đột: Cân bằng Nash giúp phân tích các tình huống đàm phán giữa các quốc gia hoặc các bên trong xung đột, ví dụ như thỏa thuận cắt giảm vũ khí hạt nhân.
Chiến tranh lạnh: Cân bằng Nash giải thích tại sao các siêu cường như Mỹ và Liên Xô duy trì trạng thái “cân bằng khủng bố” (Mutually Assured Destruction - MAD), nơi không bên nào dám tấn công trước.

4.3. Sinh học tiến hóa

Hành vi của động vật: Cân bằng Nash được sử dụng để giải thích các hành vi tiến hóa của động vật, chẳng hạn như việc chọn bạn đời hoặc phân bổ nguồn lực trong môi trường sống.

4.4. Công nghệ và mạng máy tính

Giao thông mạng: Cân bằng Nash giúp tối ưu hóa lưu lượng mạng, đảm bảo rằng các luồng dữ liệu được phân phối hiệu quả và tránh tắc nghẽn.
Blockchain: Trong các giao dịch tiền điện tử, cân bằng Nash được áp dụng để đảm bảo rằng các nút mạng hoạt động trung thực và không phá vỡ hệ thống.

4.5. Tâm lý học và xã hội học

Quyết định cá nhân: Cân bằng Nash cung cấp một khung lý thuyết để hiểu cách con người đưa ra quyết định trong các tình huống tương tác xã hội phức tạp.

5. Hạn chế của cân bằng Nash

Không duy nhất: Một trò chơi có thể có nhiều cân bằng Nash, khiến việc dự đoán kết quả trở nên khó khăn.
Không phải luôn công bằng: Cân bằng Nash đôi khi dẫn đến kết quả không mong muốn hoặc không hiệu quả về mặt xã hội (ví dụ: Prisoner’s Dilemma).
Giả định lý tính: Cân bằng Nash giả định rằng tất cả người chơi đều hành động hợp lý và biết rõ chiến lược của đối thủ, điều này không phải lúc nào cũng đúng trong thực tế.

Ứng dụng chia thưởng cho nhân viên

Chúng ta sẽ phân tích một tình huống cụ thể trong doanh nghiệp, nơi trưởng phòng cần quyết định cách chia thưởng giữa các nhân viên dựa trên hiệu suất làm việc. Điều này liên quan đến lý thuyết trò chơi và cân bằng Nash khi các nhân viên có thể điều chỉnh hành vi của mình để tối đa hóa lợi ích cá nhân.

Tình huống

Một trưởng phòng quản lý hai nhân viên (A và B). Trưởng phòng có một khoản tiền thưởng cố định là 10 triệu đồng để chia cho hai nhân viên dựa trên mức độ đóng góp của họ vào dự án. Tuy nhiên, trưởng phòng không thể giám sát hoàn toàn năng suất thực tế của từng người, mà chỉ có thể đánh giá qua kết quả báo cáo của họ.

Chiến lược của nhân viên:
- Làm việc chăm chỉ (C): Đòi hỏi nỗ lực cao nhưng có khả năng đạt kết quả tốt.
- Làm việc lười biếng (L): Tiết kiệm công sức nhưng kết quả kém hơn.
Quy tắc chia thưởng:
- Nếu cả hai cùng làm việc chăm chỉ (C, C), mỗi người nhận được 5 triệu đồng.
- Nếu một người làm việc chăm chỉ và người kia lười biếng (C, L hoặc L, C), người làm việc chăm chỉ nhận 3 triệu đồng, người lười biếng nhận 7 triệu đồng (do người lười biếng “lợi dụng” kết quả của người khác).
- Nếu cả hai đều lười biếng (L, L), mỗi người chỉ nhận được 2 triệu đồng (do kết quả dự án kém).

Ma trận trả thưởng

Bảng trả thưởng (đơn vị: triệu đồng):

	Nhân viên B: Chăm chỉ (C)	Nhân viên B: Lười biếng (L)
Nhân viên A: Chăm chỉ (C)	(5, 5)	(3, 7)
Nhân viên A: Lười biếng (L)	(7, 3)	(2, 2)

Phân tích cân bằng Nash

Chúng ta sẽ xác định chiến lược tối ưu cho từng nhân viên:

Nếu nhân viên B chọn “Chăm chỉ (C)”:
- Nếu A chọn “Chăm chỉ (C)”, A nhận 5 triệu.
- Nếu A chọn “Lười biếng (L)”, A nhận 7 triệu. => A sẽ chọn “Lười biếng (L)” vì 7 > 5.
Nếu nhân viên B chọn “Lười biếng (L)”:
- Nếu A chọn “Chăm chỉ (C)”, A nhận 3 triệu.
- Nếu A chọn “Lười biếng (L)”, A nhận 2 triệu. => A sẽ chọn “Lười biếng (L)” vì 2 < 3.

Kết luận: Dù B chọn gì, A luôn có động lực chọn “Lười biếng (L)”. Tương tự, nếu phân tích ngược lại từ góc độ của B, B cũng sẽ chọn “Lười biếng (L)”.

=> Cân bằng Nash xảy ra khi cả A và B đều chọn “Lười biếng (L)”, dẫn đến mỗi người nhận 2 triệu đồng.

Ý nghĩa trong doanh nghiệp

Hiệu quả thấp: Mặc dù cả hai nhân viên đều có thể nhận được 5 triệu đồng nếu cùng làm việc chăm chỉ, họ lại rơi vào trạng thái cân bằng Nash với kết quả tệ hơn (2 triệu đồng mỗi người). Đây là một ví dụ điển hình của “Dilemma của Tù nhân” (Prisoner’s Dilemma).
Nguyên nhân: Do thiếu sự phối hợp và lòng tin giữa các nhân viên, mỗi người chỉ nghĩ đến lợi ích cá nhân thay vì lợi ích tập thể.
Giải pháp: Trưởng phòng có thể áp dụng các biện pháp như:
- Xây dựng hệ thống giám sát: Đảm bảo rằng năng suất thực tế của nhân viên được đo lường chính xác.
- Khuyến khích tinh thần đồng đội: Tạo môi trường làm việc khuyến khích hợp tác và chia sẻ lợi ích.
- Thưởng theo nhóm: Thay vì chia thưởng cá nhân, trưởng phòng có thể thưởng dựa trên kết quả chung của cả nhóm, giảm động cơ lười biếng cá nhân.

Bài viết dưới góc nhìn của một con IT quèn, thằng IT lỏ, viết về một vấn đề kinh tế, bà con chuyên ngành thấy sai thì hoan hỉ còm mên nhẹ nhàng, đừng buôn lời cay đắng.

Cảm ơn bạn đã theo dõi bài viết, hẹn gặp lại ở các bài viết tiếp theo

Nguồn tham khảo

gõ từ khoá Nash Equilibrium

Nash, John F. (1950). “Equilibrium Points in N-Person Games.” Proceedings of the National Academy of Sciences . -> Bài báo của John Nash, giới thiệu khái niệm cân bằng Nash.

Myerson, Roger B. (1997). Game Theory: Analysis of Conflict. Harvard University Press. Sách giáo khoa

Osborne, Martin J., & Rubinstein, Ariel. (1994). A Course in Game Theory. MIT Press. Sách giáo khoa

Gibbons, Robert. (1992). A Primer in Game Theory. Pearson Education. - Sách về lý thuyết trò chơi, với nhiều ví dụ thực tế, thích hợp cho người mới tìm hiểu .

Cân Bằng Nash - Nash Equilibrium