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ơiSửa đổi

Giới thiệu trò chơiSửa đổ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à   . 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à  ,   . 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   , George thực hiện chiến lược    và Newman thực hiện chiến lược   . Dựa vào xác suất cơ bản ta suy ra rằng:

 ,  ,   với mọi  

 , , 

Các định nghĩaSửa đổi

Kỳ vọngSửa đổi

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à  ,    đượ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  ,   .

Chiến lược hỗn hợp tối ưuSửa đổi

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   .

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

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

 

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

 

Cân bằng NashSửa đổi

Các vector chiến lược hỗn hợp  ,    được xem là giải trò chơi (solve the game) nếu  ,   . Chúng ta gọi  ,    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àngSửa đổi

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ì 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à:

 ,   

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ằngSửa đổi

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ự    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    đạ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    đạ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    phải bằng 1. Từ đó ta có   nên cân bằng Nash là  .

Ý nghĩa của cân bằng NashSửa đổi

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ý NashSửa đổi

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

Chứng minh định lý NashSửa đổi

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    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  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  ,    sao cho  ,   . Điều này chứng tỏ  ,    là một cân bằng Nash.

Chú thíchSửa đổi

  1. ^ Collin Adams, Robert Franzosa, Introduction to Topology, Pure and Applied, Pearson, 2008, trang 347.

Tham khảoSửa đổi