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à $\ 1,2,...,n_{E}$. Tương tự cho George và Newman lần lượt là $\ 1,2,...,n_{G}$ và $\ 1,2,...,n_{N}$. Giả sử khi Elaine thực hiện chiến lược $\ i$, George thực hiện chiến lược $\ j$ và Newman thực hiện chiến lược $\ k$ thì Elaine, George và Newman lần lượt nhận được kết quả là $\ E_{ijk}$, $\ G_{ijk}$ và $\ N_{ijk}$. 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 $\ i$ là $\ p_{i}$, George thực hiện chiến lược $\ j$ là $\ q_{j}$ và Newman thực hiện chiến lược $\ k$ là $\ r_{k}$. Dựa vào xác suất cơ bản ta suy ra rằng:

$\ p_{i}\geq 0$, $\ q_{j}\geq 0$, $\ r_{k}\geq 0$ với mọi $\ i,j,k$

và

$\sum _{i}p_{i}=1$,$\sum _{j}q_{j}=1$,$\sum _{k}r_{k}=1$

Các định nghĩa

Kỳ vọng

Các vector xác suất tương ứng là $\ p=(p_{1},p_{2},...,p_{n_{E}})$,$\ q=(q_{1},q_{2},...,q_{n_{G}})$, $\ r=(r_{1},r_{2},...,r_{n_{N}})$.

Ta gọi kỳ vọng của kết quả đối với Elaine, George và Newman lần lượt là $\ E(p,q,r)$, $\ N(p,q,r)$ và $\ G(p,q,r)$ được viết bởi các công thức:

$\ E(p,q,r)=\sum _{i,j,k}E_{ijk}p_{i}q_{j}r_{k}$

$\ G(p,q,r)=\sum _{i,j,k}G_{ijk}p_{i}q_{j}r_{k}$

$\ N(p,q,r)=\sum _{i,j,k}N_{ijk}p_{i}q_{j}r_{k}$

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 $\ E(p,q,r)$, $\ N(p,q,r)$ và $\ G(p,q,r)$.

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à $\ q,r$. 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 $\ q,r$ đã cho. Như vậy Elaine phải tìm chiến lược hỗn hợp $\ p$ sao cho $\ E(p,q,r)\geq E(p^{'},q,r)$ với mọi chiến lược hỗn hơp $\ p^{'}$. Do đó chúng ta có định nghĩa:

Cho $\ P(q,r)$ là họ tất cả những vector xác suất $\ p$ thỏa mãn $\ E(p,q,r)\geq E(p^{'},q,r)$ với mọi chiến lược hỗn hợp $\ p^{'}$. Ta gọi $\ P(q,r)$ 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 $\ q$ và $\ r$.

Tương tự, $\ Q(p,r)$ và $\ R(p,q)$ cũng được định nghĩa tương tự.

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

$\ E(p,q,r)=\sum _{i,j,k}E_{ijk}p_{i}q_{j}r_{k}=\sum _{i}(\sum _{j,k}E_{ijk}q_{j}r_{k})p_{i}$

Đặt $\ a_{i}=\sum _{j,k}E_{ijk}q_{j}r_{k}$, chúng ta viết lại phương trình trên như sau:

$\ E(p,q,r)=a_{1}p_{1}+a_{2}p_{2}+...+a_{n_{E}}p_{n_{E}}$

Cân bằng Nash

Các vector chiến lược hỗn hợp $\ p$, $\ q$ và $\ r$ được xem là giải trò chơi (solve the game) nếu $\ p\in P(q,r)$, $\ q\in Q(p,r)$ và $\ r\in R(p,q)$. Chúng ta gọi $\ p$, $\ q$ và $\ r$ 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ì 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à:

$\ E_{122}=E_{211}=-20$, $\ E_{111}=E_{222}=0$ và $\ E_{121}=E_{112}=E_{212}=E_{221}=10$

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: $\ p=q=r=({\frac {1}{2}},{\frac {1}{2}})$.Từ đó ta có thể tìm được giá trị kỳ vọng của kết quả đối với Elaine:

$\ E(p,q,r)=-20{\frac {1}{4}}+0{\frac {1}{4}}+10{\frac {1}{2}}=0.$

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

Tương tự $\ q=(b,1-b)$ và $\ r=(c,1-c)$ 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à:

$\ E=10[ab(1-c)+a(1-b)c+(1-a)(1-b)c+(1-a)b(1-c)]-20[a(1-b)(1-c)+(1-a)bc]$.

Do đó

$\ E=10[2a(b+c-1)+c+b-3cb]$

Tương tự,

$\ G=10[2b(a+c-1)+a+c-3ac]$

$\ N=10[2c(a+b-1)+a+b-3ab]$

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

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

Trường hợp 1: Nếu $\ b+c>1$ thì $\ E$ đạt giá trị lớn nhất khi $\ a=1$. Hiển nhiên $\ b>0$, $\ c>0$, kết hợp với $\ a=1$ ta có $\ a+c>1,a+b>1$, lý luận tương tự ta được $\ G$ đạt giá trị lớn nhất khi $\ b=1$ và $\ N$ đạt giá trị lớn nhất khi $\ c=1$. Vì $\ a=b=c=1$ nên cân bằng Nash là $\ p=q=r=(1,0)$.

Trường hợp 2: Nếu $\ b+c<1$ thì $\ E$ đạt giá trị lớn nhất khi $\ a=0$. Vì $\ b<1$, $\ c<1$, kết hợp với $\ a=0$ ta có $\ a+c<1,a+b<1$, lý luận tương tự ta được $\ G$ đạt giá trị lớn nhất khi $\ b=0$ và $\ N$ đạt giá trị lớn nhất khi $\ c=0$. Vì $\ a=b=c=0$ nên cân bằng Nash là $\ p=q=r=(0,1)$.

Trường hợp 3: Nếu $\ b+c=1$ thì $\ E=10(1-3cb)$ không phụ thuộc vào $\ a$. Nếu $\ a+b$, $\ a+c$ đề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 $\ b+c=1$ nên $\ a+b$ và $\ b+c$ phải bằng 1. Từ đó ta có $\ a=b=c={\frac {1}{2}}$ nên cân bằng Nash là $\ p=q=r=({\frac {1}{2}},{\frac {1}{2}})$.

Ý nghĩa của cân bằng 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. Ứ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 $\ n$ 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 $\ p^{*},q^{*},r^{*}$ 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 $\ 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)$ tập lồi trong $\ X$ với mọi $\ x\in X$. Nếu đồ thị của $\ f$ là tập đóng trong $\ X\times X$ thì tồn tại $\ x^{*}\in X$ sao cho $\ x^{*}\in f(x^{*})$.

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

• Xây dựng đa diện $\ X$ trong không gian $\ R^{m}$. Bằng cách đặt $\ m=n_{E}+n_{G}+n_{N}$, các vector $\ w$ trong $\ R^{m}$ được định nghĩa: $\ w=(p,q,r)=(p_{1},p_{2},...,p_{N_{E}},q_{1},q_{2},...,q_{n_{G}},r_{1},r_{2},...,r_{n_{N}})$
• Định nghĩa hàm tập $\ F$ trên $\ X$ như sau:

$\ F(p,q,r)=\{(p^{'},q^{'},r^{'})|p^{'}\in P(q,r),q^{'}\in Q(p,r),r^{'}\in R(p,q)\}$. Chứng minh $\ F(p,q,r)$ là tập lồi.

• Chứng minh đồ thị $\ G_{F}$ là tập con đóng trong $\ R^{2m}$.

Khi đó theo định lý điểm bất động Kakutani tồn tại một điểm bất động của $\ F$, nghĩa là ta tìm được một điểm $\ w^{*}$ sao cho $\ w^{*}\in F(w^{*})$ và định lý đã được chứng minh vì $\ w^{*}=(p^{*},q^{*},r^{*})$ được tạo thành từ 3 vector $\ p^{*}$, $\ q^{*}$ và $\ r^{*}$ sao cho $\ p^{*}\in P(q,r)$, $\ q^{*}\in Q(p,r)$ và $\ r^{*}\in R(p,q)$. Điều này chứng tỏ $\ p^{*}$, $\ q^{*}$ và $\ r^{*}$ 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.
• Border (1985), Fixed Point Theorems with Applications to Economics and Game Theory, Cambridge University Press
• Von Neumann, Morgenstern (1944), Theory of Games and Economics Behavier, Princeton University Press