Định lý Nash

Định lý điểm bất động là một định lý nổi tiếng và quan trọng trong lĩnh vực topo, một chuyên ngành của toán học. Định lý này mang tên nhà toán học Kakutani có tên gọi là định lý điểm bất động Kakutani. Nó được ứng dụng rộng rãi trong nhiều lĩnh vực toán học khác nhau. Đặc biệt, trong lý thuyết trò chơi có một định lý nổi tiếng là định lý cân bằng Nash đặt theo John Forbes Nash,do ông là người đã đề xướng ra. Ứng dụng của định lý điểm bất động Kakutani để chứng minh định lý cân bằng Nash về sự tồn tại một cân bằng cho trò chơi gồm n người và nó được áp dụng rất thành công trong lý thuyết trò chơi.

Các thành phần dẫn đến định lý Nash

Trong trò chơi gồm $\ n$ 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 mà không biết chiến lược của người khác.

Liên quan đến 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 kết hợp 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.

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ể liên quan đến chiến lược hỗn hợp của các người chơi khác.

Điểm bất động

Định nghĩa

Cho hàm tập hợp $\ f:X\to _{s}Y$, một điểm bất động của $\ f$ là một điểm $\ x^{*}$ trong $\ X$ sao cho $\ x^{*}\in f(x^{*})$

Định lý điểm bất động Kakutani

Cho $\ X$ là một đa diện trong không gian $\ R^{n}$ và $\ f:X\to _{s}Y$ là hàm tập hợp thỏa mãn $\ f(x)$ lồi trong $\ X$ với mọi $\ x\in X$. Nếu đồ thị của $\ f$ đóng trong $\ X\times X$ thì tồn tại $\ x^{*}\in X$ sao cho $\ x^{*}\in f(x^{*})$

Định lý Nash

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

Ví dụ

Chúng ta xét ví dụ minh họa về sự hợp tác của hai người chơi (Prisoner’s dilemma).

Giả sử, George và Newman bị cảnh sát bắt vì bị tình nghi là tội phạm. Cảnh sát không có đủ chứng cứ để kết án họ, và nhốt họ ở hai phòng giam riêng biệt. George và Newman sẽ được giảm án nếu chịu khai báo về người kia. Họ có thể chọn im lặng hoặc khai báo.

Nếu cả hai đều im lặng thì cảnh sát phạt mỗi người 6 tháng tù. Nếu cả hai cùng khai báo thì mỗi người sẽ bị phạt 24 tháng tù bởi vì họ chịu hợp tác. Nếu một người khai báo còn người kia im lặng thì người im lặng sẽ nhận đủ 72 tháng tù và người khai báo chỉ nhận 3 tháng tù.

Bằng lý luận tương tự như những phần trước ta có tìm được trò chơi này chỉ có một cân bằng Nash duy nhất khi cả hai người chơi cùng khai báo. Tuy nhiên đây không phải là kết quả tốt nhất cho hai người lựa chọn vì nếu cả khai cùng khai báo thì bản án tù giam cả hai nhận được là 24 tháng. Nếu George và Newman cùng im lặng thì họ chỉ nhận 6 tháng tù giam. Như vậy đây là kết quả tốt hơn lựa chon trong trường hợp cân bằng Nash. Vì vậy để kết quả tốt nhất thì hai người chơi phải có sự hợp tác với nhau.