Sự cân bằng Nash

Sự cân bằng Nash là một định lý trong lý thuyết trò chơi, một lĩnh vực của toán học ứng dụng. Định lý này được đặt theo tên của John Forbes Nash, người đã phát triển khái niệm này. Nó được sử dụng để phân tích các chiến lược nhằm xác định lựa chọn tối ưu.

Lý thuyết trò chơi

Giới thiệu về trò chơi

Xem xét một trò chơi có ba người chơi: Elaine, George và Newman. Mỗi người chơi có một số lượng hữu hạn các chiến lược. Cụ thể, các chiến lược của Elaine được đánh số từ $1,2,...,n_E$. Tương tự, các chiến lược của George và Newman lần lượt được đánh số từ $1,2,...,n_G$ và $1,2,...,n_N$. Giả sử Elaine chọn chiến lược $i$, George chọn chiến lược $j$ và Newman chọn chiến lược $k$, thì Elaine, George và Newman lần lượt nhận được các kết quả là $E_{ijk}$, $G_{ijk}$ và $N_{ijk}$. Những kết quả này thể hiện sự trả thưởng của từng người chơi, dựa trên chiến lược mà họ chọn và kết quả của trò chơi. Ta ký hiệu xác suất mà Elaine chọn chiến lược $i$ là $p_i$, George chọn chiến lược $j$ với xác suất là $q_j$ và Newman chọn chiến lược $k$ với xác suất là $r_k$. Từ những xác suất này, ta có thể suy ra các kết quả dựa trên tỷ lệ phần trăm mà các chiến lược được chọn.

$p_i\ge <!--\; \ge \; -->0$, $q_j\ge <!--\; \ge \; -->0$, $r_k\ge <!--\; \ge \; -->0$ đối với mọi $i,j,k$

và

$\underset{i}{\sum <!--\; \sum \; -->}{p}_i=1$, $\underset{j}{\sum <!--\; \sum \; -->}{q}_j=1$, $\underset{k}{\sum <!--\; \sum \; -->}{r}_k=1$

Các định nghĩa cơ bản

Các vector xác suất tương ứng được biểu diễn như sau: $p=(p_1,p_2,...,p_{n_E})$, $q=(q_1,q_2,...,q_{n_G})$, $r=(r_1,r_2,...,r_{n_N})$.

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

$E(p,q,r)=\underset{i,j,k}{\sum <!--\; \sum \; -->}{E}_{ijk}{p}_i{q}_j{r}_k$

$G(p,q,r)=\underset{i,j,k}{\sum <!--\; \sum \; -->\; <div\; class="min-w-[250px]\; max-w-[94vw]\; md:max-w-[770px]">\; <ins\; class="adsbygoogle"\; style="display:block;\; text-align:center;"\; data-ad-layout="in-article"\; data-ad-format="fluid"\; data-ad-client="ca-pub-9247024304160346"\; data-ad-slot="4115752014"></ins>\; </div>}{G}_{ijk}{p}_i{q}_j{r}_k$

$N(p,q,r)=\underset{i,j,k}{\sum <!--\; \sum \; -->}{N}_{ijk}{p}_i{q}_j{r}_k$

Giá trị kỳ vọng được tính bằng cách lấy tổng tất cả các kết quả và nhân với xác suất mà mỗi kết quả xảy ra. Nếu Elaine, George và Newman có đủ thời gian để chơi trò chơi của mình, thì giá trị trung bình của kết quả đối với mỗi người sẽ gần bằng $E(p,q,r)$, $N(p,q,r)$ và $G(p,q,r)$.

Giả sử rằng trong một trò chơi đặc biệt, Elaine biết rằng George và Newman đang sử dụng hai chiến lược hỗn hợp lần lượt là $q,r$. Elaine muốn đạt được kết quả tối ưu có thể, nghĩa là, cô ấy muốn giá trị kỳ vọng là cao nhất với $q,r$ đã cho. Để làm điều đó, Elaine cần tìm chiến lược hỗn hợp $p$ sao cho $E(p,q,r)\ge <!--\; \ge \; -->E(p^{{}^{\prime }},q,r)$ đối với mọi chiến lược hỗn hợp $p^{{}^{\prime }}$. Điều này dẫn đến định nghĩa sau đây:

Cho $P(q,r)$ đại diện cho tất cả các vector xác suất $p$ thỏa mãn điều kiện $E(p,q,r)\ge <!--\; \ge \; -->E(p^{{}^{\prime }},q,r)$ đối với mọi chiến lược hỗn hợp $p^{{}^{\prime }}$. Ta gọi $P(q,r)$ là tập hợp tất cả 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ự.

Giả sử hai chiến lược hỗn hợp là $q$ và $r$. Ta có:

$E(p,q,r)=\underset{i,j,k}{\sum <!--\; \sum \; -->}{E}_{ijk}{p}_i{q}_j{r}_k=\underset{i}{\sum <!--\; \sum \; -->}\left(\underset{j,k}{\sum <!--\; \sum \; -->}{E}_{ijk}{q}_j{r}_k\right)p_i$

Đặt $a_i=\underset{j,k}{\sum <!--\; \sum \; -->}{E}_{ijk}{q}_j{r}_k$, chúng ta có thể 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ác vector chiến lược hỗn hợp $p$, $q$ và $r$ được coi là giải trò chơi (solve the game) khi $p\in <!--\; \in \; -->P(q,r)$, $q\in <!--\; \in \; -->Q(p,r)$ và $r\in <!--\; \in \; -->R(p,q)$. Khi đó, $p$, $q$ và $r$ được gọi là một cân bằng Nash.

Trong luận án tiến sĩ của mình tại Princeton vào 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. Phát hiện này đã làm thay đổi toàn diện lĩnh vực lý thuyết trò chơi và có ảnh hưởng sâu rộng đến kinh tế học cũng như các ngành khoa học xã hội khác. Do đó, năm 1994, giải Nobel kinh tế đã được trao cho ông để vinh danh những cống hiến to lớn của ông.

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

Giả sử Elaine, George và Newman quyết định đi ăn tối. Họ có hai lựa chọn nhà hàng: Happy Star Chinese hoặc New Yorker. Vì không thể thống nhất ý kiến, họ quyết định thực hiện trò chơi để chọn nhà hàng: ba người sẽ bốc thăm để chọn cho mình một nhà hàng. Nếu có hai người chọn cùng một nhà hàng và người còn lại chọn nhà hàng khác, hai người cùng chọn sẽ đến nhà hàng đó, còn người còn lại sẽ phải trả cho mỗi người 10 đô la. Nếu tất cả ba người đều chọn cùng một nhà hàng, họ sẽ cùng đến nhà hàng đó và mỗi người tự thanh toán cho bữa ăn của mình.

Nếu chúng ta gán số 1 cho việc chọn nhà hàng Happy Star Chinese và số 2 cho việc chọn nhà hàng New Yorker, kết quả xảy ra đối với Elaine sẽ là:

Các giá trị kỳ vọng cho các kết quả chiến lược hỗn hợp như sau: $E_{122}=E_{211}=-<!--\; -\; -->20$, $E_{111}=E_{222}=0$ và $E_{121}=E_{112}=E_{212}=E_{221}=10$.

Tương tự như vậy, chúng ta cũng có thể tính được kết quả đối với George và Newman.

Giả sử Elaine, George và Newman đều có sự yêu thích như nhau đối với hai nhà hàng. Khi đó, các chiến lược hỗn hợp của họ sẽ đồng nhất như sau: $p=q=r=(\frac{1}{2},\frac{1}{2})$. Từ đó, chúng ta có thể tính giá trị kỳ vọng cho Elaine là:

Giá trị kỳ vọng cho Elaine là: $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 cho George và Newman cũng đều là 0.

Chúng ta sẽ xác định các điểm cân bằng trong trò chơi nhà hàng từ ví dụ đã nêu.

Giả sử $p=(a,1-<!--\; -\; -->a)$ là chiến lược hỗn hợp của Elaine, với $a$ là xác suất để Elaine chọn nhà hàng Happy Star Chinese, và $1-<!--\; -\; -->a$ là xác suất để Elaine chọn nhà hàng New Yorker.

Tương tự, $q=(b,1-<!--\; -\; -->b)$ và $r=(c,1-<!--\; -\; -->c)$ là các chiến lược hỗn hợp của George và Newman.

Với các chiến lược trên, giá trị kỳ vọng của Elaine được tính như sau:

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]

Với b, c đã được cố định, ta cần xác định giá trị lớn nhất của E.

Xét ba trường hợp của tổng b + c.

Trường hợp 1: Nếu b + c > 1, thì E đạt giá trị cao nhất khi a = 1. Hiển nhiên, với b > 0 và c > 0, kết hợp với a = 1, ta có a + c > 1 và a + b > 1. Từ đó, G đạt giá trị lớn nhất khi b = 1 và N đạt giá trị lớn nhất khi c = 1. Do 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ị cao nhất khi a = 0. Vì b < 1 và c < 1, kết hợp với a = 0, ta có a + c < 1 và a + b < 1. Từ đó, G đạt giá trị lớn nhất khi b = 0 và N đạt giá trị lớn nhất khi c = 0. Do 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 và a + c đều khác 1, xác suất của ba người chơi sẽ bằng 0 hoặc 1, mâu thuẫn với giả thiết b + c = 1. Do đó, a + b và b + c phải bằng 1. Từ đó suy ra a = b = c = 1/2, và cân bằng Nash là p = q = r = (1/2, 1/2).

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

Trong một trò chơi có n người chơi, mỗi người sẽ chọn chiến lược riêng. Với mỗi người chơi, sẽ có một mức chi trả cho các kết quả có thể xảy ra tùy thuộc vào các lựa chọn chiến lược của những người chơi khác. Mỗi người chơi có thể chọn chiến lược hỗn hợp và dựa vào sự kết hợp chiến lược của người chơi khác để xác định kết quả trung bình hoặc giá trị kỳ vọng cho mình.

Định lý Nash khẳng định rằng mỗi người chơi có một tập hợp chiến lược hỗn hợp tối ưu khi biết chiến lược của những người chơi khác. Chiến lược hỗn hợp tối ưu này mang lại giá trị kỳ vọng lớn nhất có thể cho mỗi người khi biết chiến lược của đối thủ. Một cân bằng Nash là lựa chọn chiến lược mà kết quả cho mỗi người chơi là giá trị kỳ vọng cao nhất có thể dựa trên các chiến lược của ngườ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 sẽ chỉ chứng minh cho trò chơi với 3 người: Elaine, George và Neumann. Trường hợp tổng quát được chứng minh tương tự.

Ta sẽ chứng minh sự tồn tại của 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 sử dụng Định lý điểm bất động Kakutani.

Cho hàm f: X → Y, một điểm bất động của f là điểm x* trong X sao cho x* ∈ 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 → Y là một hàm tập hợp thỏa mãn f(x) là tập lồi trong X với mọi x ∈ X. Nếu đồ thị của f là tập đóng trong X × X, thì tồn tại x* ∈ X sao cho x* ∈ f(x*).

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

Xây dựng đa diện X trong không gian R^m. Với 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}). Sau đó, định nghĩa hàm tập F trên X như sau:

$F(p,q,r)=\left\{\right(p^{{}^{\prime }},q^{{}^{\prime }},r^{{}^{\prime }})|p^{{}^{\prime }}\in <!--\; \in \; -->P(q,r),q^{{}^{\prime }}\in <!--\; \in \; -->Q(p,r),r^{{}^{\prime }}\in <!--\; \in \; -->R(p,q\left)\right\}$. Chứng minh rằng $F(p,q,r)$ là một tập lồi.

• Chứng minh rằng đồ thị của $G_F$ là một tập con đóng trong $R^{2m}$.

Theo định lý điểm bất động Kakutani, tồn tại một điểm bất động của $F$, tức là có một điểm $w^{\ast <!--\; \ast \; -->}$ sao cho $w^{\ast <!--\; \ast \; -->}\in <!--\; \in \; -->F\left(w^{\ast <!--\; \ast \; -->}\right)$ và điều này chứng tỏ rằng định lý đã được chứng minh vì $w^{\ast <!--\; \ast \; -->}=(p^{\ast <!--\; \ast \; -->},q^{\ast <!--\; \ast \; -->},r^{\ast <!--\; \ast \; -->})$ bao gồm ba vector $p^{\ast <!--\; \ast \; -->}$, $q^{\ast <!--\; \ast \; -->}$ và $r^{\ast <!--\; \ast \; -->}$ sao cho $p^{\ast <!--\; \ast \; -->}\in <!--\; \in \; -->P(q,r)$, $q^{\ast <!--\; \ast \; -->}\in <!--\; \in \; -->Q(p,r)$ và $r^{\ast <!--\; \ast \; -->}\in <!--\; \in \; -->R(p,q)$. Điều này chứng minh rằng $p^{\ast <!--\; \ast \; -->}$, $q^{\ast <!--\; \ast \; -->}$ và $r^{\ast <!--\; \ast \; -->}$ là một điểm cân bằng Nash.

Chú thích

• Nash, John (1950) 'Các điểm cân bằng trong trò chơi nhiều người' Biên niên của Viện Hàn lâm Khoa học Quốc gia 36(1):48-49.
• Nash, John (1951) 'Trò chơi không hợp tác' Các Tạp chí Toán học 54(2):286-295.
• Border (1985), Các định lý điểm cố định với ứng dụng trong kinh tế học và lý thuyết trò chơi, Nhà xuất bản Đại học Cambridge
• Von Neumann, Morgenstern (1944), Lý thuyết trò chơi và hành vi kinh tế, Nhà xuất bản Đại học Princeton