Cân bằng Nash

Cân bằng Nash là một định lý trong lý thuyết trò chơi - một nhánh của toán học ứng dụng. Định lý này được đặt tên theo John Forbes Nash, do ông là người đã đề xướng ra. Nó được dùng để nghiên cứu các chiến thuật sao cho sự lựa chọn là tối ưu.

Lý thuyết trò chơi

Giới thiệu trò chơi

Để đơn giản ta xét trò chơi gồm 3 người là Elaine, George và Newman. Mỗi người chơi có hữu hạn các chiến lược cho mình. Cho Elaine, các chiến lược được đánh số là . Tương tự cho George và Newman lần lượt là  và . 
Giả sử khi Elaine thực hiện chiến lược , George thực hiện chiến lược  và Newman thực hiện chiến lược  thì Elaine, George và Newman lần lượt nhận được kết quả là ,  và . Các kết quả này là sự chi trả của người chơi phụ thuộc vào lượt chơi của người đó thắng hoặc thua.
Ta ký hiệu xác suất mà Elaine thực hiện chiến lược  là , George thực hiện chiến lược  là  và Newman thực hiện chiến lược  là . Dựa vào xác suất cơ bản ta suy ra rằng:

, ,  với mọi 

và

,,

Các định nghĩa

Kỳ vọng

Các vector xác suất tương ứng là ,, .

Ta gọi kỳ vọng của kết quả đối với Elaine, George và Newman lần lượt là ,  và  được viết bởi các công thức:

Các giá trị kỳ vọng này bằng tổng tất cả các kết quả nhân với xác suất mà kết quả đó xuất hiện. Nếu Elaine, George và Newman có đủ thời gian chơi trò chơi của họ thì ta thấy rằng giá trị trung bình của các kết quả đối với mỗi người xấp xỉ gần bằng ,  và .

Chiến lược hỗn hợp tối ưu

Bây giờ, giả sử rằng trong một trò chơi đặc biệt nào đó, Elaine biết George và Newman sử dụng hai chiến lược hỗn hợp lần lượt là . Elaine muốn nhận được kết quả tối ưu có thể được, nghĩa là Elaine muốn kỳ vọng của kết quả là lớn nhất với  đã cho. Như vậy Elaine phải tìm chiến lược hỗn hợp  sao cho  với mọi chiến lược hỗn hơp . Do đó chúng ta có định nghĩa:

Cho  là họ tất cả những vector xác suất  thỏa mãn  với mọi chiến lược hỗn hợp . Ta gọi  là tập các chiến lược hỗn hợp tối ưu đối với hai chiến lược hỗn hợp  và .

Tương tự,  và  cũng được định nghĩa tương tự.

Cố định hai chiến lược hỗn hợp  và . Ta có:

Đặt , chúng ta viết lại phương trình trên như sau:

Cân bằng Nash

Các vector chiến lược hỗn hợp ,  và  được xem là giải trò chơi (solve the game) nếu ,  và . Chúng ta gọi ,  và  là một cân bằng Nash.

Trong luận án tiến sĩ của mình tại Princeton năm 1950, John Nash đã chứng minh rằng mọi trò chơi đều có ít nhất một điểm cân bằng. Kết quả này đã cách mạng hóa lĩnh vực lý thuyết trò chơi và có ảnh hưởng rất lớn trong kinh tế học cũng như khoa học xã hội sau này. Vì vậy năm 1994, giải Nobel kinh tế được trao cho nhà toán học này để vinh danh những đóng góp của ông.

Ví dụ: Trò chơi nhà hàng 

Giả sử Elaine, George và Newman quyết định đi ăn tối. Họ có thể chọn một trong hai nhà hàng là Happy Star Chinese hoặc New Yorker. Do không thể quyết định được nên họ thực hiện trò chơi như sau: ba người cùng bốc thăm chọn cho mình một nhà hàng. Nếu hai trong số họ cùng chọn một nhà hàng còn người kia thì không, thì tất cả bọn họ sẽ đến nhà hàng mà hai người cùng chọn để ăn tối, đồng thời người còn lại phải trả cho hai người kia mỗi người 10 dollars cho bữa ăn tối. Nếu ba người cùng chọn giống nhau thì cả ba cùng đến nhà hàng đã chọn và mỗi người tự trả cho bữa ăn của mình.

Nếu đánh số chiến lược chọn nhả hàng Happy Star Chinese là 1, chiến lược chọn nhà hàng New Yorker là 2 thì ta có kết quả xảy ra đối với Elaine là:

,  và 

Tương tự, ta cũng có kết quả đối với George và Newman.

Giả sử Elaine, George và Newman đều thích cả hai nhà hàng như nhau. Khi đó các chiến lược hỗn hợp của họ là như nhau: .Từ đó ta có thể tìm được giá trị kỳ vọng của kết quả đối với Elaine:

Tương tự các giá trị kỳ vọng của kết quả đối với George và Newman cũng bằng 0.

Điểm cân bằng 
Ta tìm những điểm cân bằng trong trò chơi nhà hàng ở ví dụ trên.

Đặt  là chiến lược hỗn hợp của Elaine, trong đó  là xác suất mà Elaine chọn nhà hàng Happy Star Chinese,  là xác suất Eleine chọn nhà hàng New Yorker.

Tương tự  và  các chiến lược hỗn hợp của George và Newman.

Khi đó giá trị kỳ vọng kết quả của Elaine là:

.

Do đó

Tương tự,
 

Cố định , cần tìm giá trị lớn nhất của .

Ta xét ba trường hợp khác nhau của 

Trường hợp 1: Nếu  thì  đạt giá trị lớn nhất khi . Hiển nhiên , , kết hợp với  ta có , lý luận tương tự ta được  đạt giá trị lớn nhất khi  và  đạt giá trị lớn nhất khi . Vì  nên cân bằng Nash là .

Trường hợp 2: Nếu  thì  đạt giá trị lớn nhất khi . Vì , , kết hợp với  ta có , lý luận tương tự ta được  đạt giá trị lớn nhất khi  và  đạt giá trị lớn nhất khi . Vì  nên cân bằng Nash là .

Trường hợp 3: Nếu  thì  không phụ thuộc vào . Nếu ,  đều khác 1 thì xác suất của ba người chơi bằng 0 hoặc bằng 1, mâu thuẫn với giả thiết  nên  và  phải bằng 1. Từ đó ta có  nên cân bằng Nash là .

Ý nghĩa của cân bằng Nash

Trong trò chơi gồm  người chơi, mỗi người chơi có sự lựa chọn các chiến lược để thực hiện. Ứng với mỗi người chơi là một sự chi trả của người chơi cho tất cả các kết quả có thể xảy ra tương ứng với sự lựa chọn chiến lược của các người chơi. 
Mỗi người chơi có thể lựa chon một chiến lược hỗn hợp và kết hợp các lựa chọn các chiến lược hỗn hợp của những người chơi khác xác định kết quả trung bình hoặc giá trị kỳ vọng cho mỗi người chơi.

Định lý Nash nói rằng mỗi người chơi có một tập các chiến lược hỗn hợp tối ưu khi biết sự lựa chọn chiến lược hỗn hợp của các người chơi khác. Mỗi chiến lược hỗn hợp tối ưu đưa đến kết quả trong giá trị kỳ vọng lớn nhất có thể cho người chơi khi biết chiến lược hỗn hợp của các người chơi khác. 
Một cân bằng Nash là một sự lựa chọn của chiến lược hỗn hợp mà kết quả cho mỗi người chơi là các giá trị kỳ vọng lớn nhất có thể ứng với chiến lược hỗn hợp của các người chơi khác.

Định lý Nash

Tồn tại một cân bằng Nash cho mọi trò chơi gồm  người chơi.

Chứng minh định lý Nash
Ta chỉ chứng minh cho trò chơi gồm 3 người gồm Elaine, George và Neumann, trường hợp tổng quát được chứng minh tương tự.

Ta sẽ chứng minh tồn tại chiến lược hỗn hợp  là cân bằng Nash của trò chơi.

Chứng minh này dùng Định lý điểm bất động Kakutani.

Cho hàm tập hợp , một điểm bất động của  là một điểm  trong  sao cho .

 Định lý điểm bất động Kakutani: Cho  là một đa diện trong không gian  và  là hàm tập hợp thỏa mãn   tập lồi trong  với mọi . Nếu đồ thị của  là tập đóng trong  thì tồn tại  sao cho .

Hướng chứng minh định lý Nash:

 Xây dựng đa diện  trong không gian . Bằng cách đặt , các vector  trong  được định nghĩa: 
 Định nghĩa hàm tập  trên  như sau:

.
Chứng minh  là tập lồi.

 Chứng minh đồ thị  là tập con đóng trong .

Khi đó theo định lý điểm bất động Kakutani tồn tại một điểm bất động của , nghĩa là ta tìm được một điểm  sao cho  và định lý đã được chứng minh vì  được tạo thành từ 3 vector ,  và  sao cho ,  và . Điều này chứng tỏ ,  và  là một cân bằng Nash.

Chú thích

Tham khảo

 Nash, John (1950) "Equilibrium points in n-person games" Proceedings of the National Academy of Sciences 36(1):48-49.
 Nash, John (1951) "Non-Cooperative Games" The Annals of Mathematics 54(2):286-295.
 
 

Toán học ứng dụng
Lý thuyết quyết định
Lý thuyết trò chơi
Kinh tế năm 1951