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à formula_1. Tương tự cho George và Newman lần lượt là formula_2 và formula_3. 
Giả sử khi Elaine thực hiện chiến lược formula_4, George thực hiện chiến lược formula_5 và Newman thực hiện chiến lược formula_6 thì Elaine, George và Newman lần lượt nhận được kết quả là formula_7, formula_8 và formula_9. 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 formula_4 là formula_11, George thực hiện chiến lược formula_5 là formula_13 và Newman thực hiện chiến lược formula_6 là formula_15. Dựa vào xác suất cơ bản ta suy ra rằng:

formula_16, formula_17, formula_18 với mọi formula_19

và

formula_20,formula_21,formula_22

===Các định nghĩa===
====Kỳ vọng====
Các vector xác suất tương ứng là formula_23,formula_24, formula_25.

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

formula_29

formula_30

formula_31

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 formula_26, formula_27 và formula_28.

====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à formula_35. 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 formula_35 đã cho. Như vậy Elaine phải tìm chiến lược hỗn hợp formula_37 sao cho formula_38 với mọi chiến lược hỗn hơp formula_39. Do đó chúng ta có định nghĩa:

Cho formula_40 là họ tất cả những vector xác suất formula_37 thỏa mãn formula_38 với mọi chiến lược hỗn hợp formula_39. Ta gọi formula_40 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 formula_45 và formula_46.

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

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

formula_51

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

formula_53

====Cân bằng Nash====
Các vector chiến lược hỗn hợp formula_37, formula_45 và formula_46 được xem là "giải trò chơi" (solve the game) nếu formula_57, formula_58 và formula_59. Chúng ta gọi formula_37, formula_45 và formula_46 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à:

formula_63, formula_64 và formula_65

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: formula_66.Từ đó ta có thể tìm được giá trị kỳ vọng của kết quả đối với Elaine:

formula_67

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 formula_68 là chiến lược hỗn hợp của Elaine, trong đó formula_69 là xác suất mà Elaine chọn nhà hàng Happy Star Chinese, formula_70 là xác suất Eleine chọn nhà hàng New Yorker.

Tương tự formula_71 và formula_72 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à:

formula_73.

Do đó

formula_74

Tương tự,
formula_75

formula_76

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

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

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

Trường hợp 2: Nếu formula_93 thì formula_78 đạt giá trị lớn nhất khi formula_95. Vì formula_96, formula_97, kết hợp với formula_95 ta có formula_99, lý luận tương tự ta được formula_87 đạt giá trị lớn nhất khi formula_101 và formula_89 đạt giá trị lớn nhất khi formula_103. Vì formula_104 nên cân bằng Nash là formula_105.

Trường hợp 3: Nếu formula_106 thì formula_107 không phụ thuộc vào formula_69. Nếu formula_109, formula_110 đề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 formula_106 nên formula_109 và formula_79 phải bằng 1. Từ đó ta có formula_114 nên cân bằng Nash là formula_115.

===Ý nghĩa của cân bằng Nash===
Trong trò chơi gồm formula_116 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==
===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 formula_118 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 formula_119, một điểm bất động của formula_120 là một điểm formula_121 trong formula_122 sao cho formula_123.

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

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

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

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

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

==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.