Bỏ qua

Chương 58: Lý thuyết trò chơi cơ bản

Câu hỏi mở đầu

Khi kết quả không chỉ phụ thuộc may rủi mà còn vào lựa chọn của người khác, những người cũng đang tính toán như ta, thì "tối ưu" còn có nghĩa gì?

Khi cột của bảng là một người đang suy tính

Trong bảng quyết định của Chương 57, cột được chọn bởi thế giới, với những xác suất đã biết. Giờ hãy để cột được chọn bởi một người khác, cũng đang suy tính như ta. Không còn xác suất nào để thay vào: người ấy làm gì phụ thuộc vào việc họ đoán ta làm gì, và ta làm gì lại phụ thuộc vào việc ta đoán họ làm gì. "Tôi đoán anh ta sẽ làm thế này, nên tôi làm thế kia; nhưng anh ta cũng đoán được điều đó..." Vòng suy luận ấy có vẻ không có điểm dừng.

Một ví dụ nổi tiếng (số liệu giả định). Hai nghi phạm bị giam riêng, không liên lạc được với nhau. Mỗi người chọn im lặng hay khai. Nếu cả hai im lặng, mỗi người chịu 1 năm tù; nếu cả hai khai, mỗi người 5 năm; nếu một người khai còn người kia im lặng, người khai được tha và người im lặng chịu 10 năm. Người A suy nghĩ: nếu B im lặng, mình khai thì được tha thay vì chịu 1 năm; nếu B khai, mình khai thì chịu 5 năm thay vì 10 năm. Dù B làm gì, khai vẫn tốt hơn. B cũng suy nghĩ đúng như vậy. Cả hai khai và mỗi người chịu 5 năm, trong khi nếu cả hai im lặng thì mỗi người chỉ chịu 1 năm. Mỗi người lựa chọn hợp lý cho riêng mình, và cả hai cùng thiệt.

Ở ví dụ này, vòng suy luận dừng ngay, vì một lựa chọn tốt hơn bất kể người kia làm gì. Thường thì không may như vậy. Hai người lái xe ngược chiều trên một con đường hẹp: đi bên phải hay bên trái đều được, miễn là cả hai cùng chọn một phía. Lựa chọn tốt nhất của mỗi người phụ thuộc hoàn toàn vào người kia. Khi đó, một dự đoán hợp lý về cách mọi người sẽ hành xử phải có một tính chất: nếu ai cũng tin vào nó, không ai muốn một mình làm khác đi. Một dự đoán thiếu tính chất ấy tự phá hủy nó, vì sẽ có người được lợi khi làm trái. Những tình huống cân bằng như thế gọi theo tên John Nash, người định nghĩa và nghiên cứu chúng năm 1950. Mỗi người chọn phản ứng tốt nhất (best response), tức lựa chọn có lợi nhất cho mình, với lựa chọn của những người khác, và lựa chọn của những người khác cũng là phản ứng tốt nhất: đó là một điểm bất động theo nghĩa của Chương 24.

Vì sao cấu trúc này phải xuất hiện, dù chưa ai đặt tên cho nó? Vì ở đâu có nhiều người cùng tối ưu cho riêng mình mà kết quả phụ thuộc lẫn nhau, thì mọi khuôn mẫu hành xử bền vững, một luật đi đường ai cũng theo, một mức giá tồn tại lâu trên thị trường, một thói quen trong một nhóm, đều phải là một khuôn mẫu mà không ai được lợi khi một mình đổi khác. Nếu có người được lợi, sớm muộn họ sẽ đổi, và khuôn mẫu không còn bền. Đòi hỏi tự nhất quán ấy tự nó ép ra khái niệm cân bằng, dù người trong cuộc có biết tên nó hay không.

Ký hiệu

Lý thuyết trò chơi (game theory) nghiên cứu những tình huống mà kết quả của mỗi người phụ thuộc vào lựa chọn của nhiều người; "trò chơi" ở đây chỉ mọi tình huống như thế, không riêng trò chơi giải trí. Một trò chơi gồm những người chơi, các lựa chọn của từng người, gọi là chiến lược (strategy), và lợi ích mà mỗi người nhận được ứng với mỗi tổ hợp chiến lược. Với hai người A và B, ta xếp các lợi ích thành bảng lợi ích (payoff matrix): mỗi hàng là một chiến lược của A, mỗi cột là một chiến lược của B, mỗi ô ghi cặp (lợi ích của A; lợi ích của B).

  • Phản ứng tốt nhất của A với một chiến lược của B là chiến lược cho A lợi ích lớn nhất khi B chơi chiến lược ấy. Trên bảng, với mỗi cột, đánh dấu số lớn nhất của A trong cột; với mỗi hàng, đánh dấu số lớn nhất của B trong hàng.
  • Một chiến lược của A là chiến lược trội nghiêm ngặt (strictly dominant strategy) nếu nó cho A lợi ích lớn hơn hẳn mọi chiến lược khác của A, dù B làm gì. Ngược lại, một chiến lược là chiến lược bị trội (dominated strategy) nếu có một chiến lược khác của cùng người chơi cho lợi ích lớn hơn hẳn nó, dù đối thủ làm gì; người chơi hợp lý không bao giờ dùng nó, nên có thể gạch nó khỏi bảng, rồi lặp lại trên bảng nhỏ hơn.
  • Một cặp chiến lược là một cân bằng Nash (Nash equilibrium) nếu mỗi chiến lược là phản ứng tốt nhất với chiến lược kia: không ai được lợi khi một mình đổi chiến lược. Trên bảng, đó là những ô có cả hai số đều được đánh dấu.
  • Chọn hẳn một chiến lược gọi là chơi một chiến lược thuần (pure strategy). Chọn ngẫu nhiên giữa các chiến lược theo những xác suất cố định gọi là chơi một chiến lược hỗn hợp (mixed strategy); khi ấy lợi ích được tính bằng kỳ vọng (Chương 44).
  • Một trò chơi hai người mà ở mọi ô tổng hai lợi ích bằng 0 gọi là trò chơi tổng bằng không (zero-sum game): cái một người được chính là cái người kia mất.

Làm bằng tay

Ví dụ 1 (hai nghi phạm). Ghi lợi ích là số năm tù với dấu trừ. Với cột "B im lặng", A được \(-1\) nếu im lặng và 0 nếu khai: đánh dấu 0. Với cột "B khai", A được \(-10\) hay \(-5\): đánh dấu \(-5\). Làm tương tự cho B theo từng hàng. Chỉ có ô (khai; khai) có cả hai số được đánh dấu: đó là cân bằng Nash duy nhất, với lợi ích \((-5; -5)\), tệ hơn \((-1; -1)\) của ô (im lặng; im lặng) cho cả hai người. Tình huống này gọi là song đề tù nhân (prisoner's dilemma). Khai là chiến lược trội nghiêm ngặt của mỗi người; điều đó đủ để kết luận (Định lý 3).

Bảng lợi ích song đề tù nhân với ô khai và khai được tô
Song đề tù nhân (số năm tù, ghi với dấu trừ). Số của A (trái trong mỗi ô) được gạch dưới màu cam khi là phản ứng tốt nhất với cột ấy, số của B (phải) gạch dưới màu xanh khi là phản ứng tốt nhất với hàng ấy. Ô tô màu, có cả hai gạch, là cân bằng Nash.

Ví dụ 2 (cạnh tranh giá). Hai hãng (số liệu giả định) cùng chọn đặt giá cao, vừa hay thấp; lợi nhuận tính bằng tỉ đồng như trong hình. Với hãng A, "vừa" cho \(11\), \(7\), \(3\) còn "cao" cho \(9\), \(4\), \(2\): giá cao bị trội nghiêm ngặt bởi giá vừa, dù B làm gì. Bảng đối xứng nên giá cao cũng bị trội với B. Gạch hai chiến lược ấy đi, còn bảng \(2 \times 2\). Đánh dấu phản ứng tốt nhất trên đó: với B chọn vừa, A chọn vừa (\(7 > 6\)); với B chọn thấp, A chọn thấp (\(4 > 3\)); B cũng vậy. Có hai cân bằng Nash, (vừa; vừa) với \((7; 7)\) và (thấp; thấp) với \((4; 4)\). Cả hai là cân bằng, nhưng một cân bằng tốt hơn hẳn cho cả hai hãng; lý thuyết không nói thị trường sẽ dừng ở cân bằng nào.

Bảng lợi ích ba mức giá với hàng và cột giá cao bị gạch, hai ô cân bằng được tô
Cạnh tranh giá giả định. Hàng và cột "cao" (xám) bị trội nghiêm ngặt bởi "vừa" nên bị gạch. Trên phần còn lại, hai ô (vừa; vừa) và (thấp; thấp) có cả hai số được đánh dấu: hai cân bằng Nash.

Ví dụ 3 (đi bên nào của đường). Hai người lái xe ngược chiều, mỗi người chọn đi bên phải hay bên trái. Lợi ích giả định:

B đi bên phải B đi bên trái
A đi bên phải \(1; 1\) \(-10; -10\)
A đi bên trái \(-10; -10\) \(1; 1\)

Có hai cân bằng Nash, (phải; phải) và (trái; trái), và chúng như nhau về mọi mặt. Một trò chơi như thế, nơi điều quan trọng là mọi người chọn giống nhau, gọi là trò chơi phối hợp (coordination game). Toán học chỉ ra cấu trúc: phải phối hợp, và có đúng hai cách phối hợp. Chọn cách nào là một quy ước, đúng theo nghĩa của Chương 1: Việt Nam đi bên phải, Anh và Nhật Bản đi bên trái, và không bên nào "đúng" hơn. Nhưng một khi quy ước đã được chọn, nó tự duy trì: không ai được lợi khi một mình đổi bên. Quy ước là tùy ý, còn việc quy ước ấy bền vững là cấu trúc.

Ví dụ 4 (đoán đồng xu và oẳn tù tì). Mỗi người giơ mặt sấp hay mặt ngửa của một đồng xu; nếu hai mặt giống nhau, A thắng 1 đồng của B, nếu khác nhau, B thắng 1 đồng của A.

B sấp B ngửa
A sấp \(1; -1\) \(-1; 1\)
A ngửa \(-1; 1\) \(1; -1\)

Đây là trò chơi tổng bằng không, và đánh dấu phản ứng tốt nhất cho thấy không ô nào có hai dấu: không có cân bằng thuần. Ai chơi theo một quy luật đoán được sẽ bị khai thác. Nhưng nếu mỗi người tung đồng xu để chọn, mỗi mặt với xác suất \(\frac12\), thì người kia chọn gì cũng được kỳ vọng 0: không ai được lợi khi đổi, nên đó là một cân bằng Nash hỗn hợp. Oẳn tù tì cũng vậy: nếu đối thủ ra búa, bao, kéo mỗi thứ với xác suất \(\frac13\), thì ta ra gì cũng thắng, hòa, thua mỗi thứ với xác suất \(\frac13\), kỳ vọng 0; và nếu đối thủ lệch khỏi \(\frac13\), chẳng hạn ra búa nhiều hơn, ta ra bao nhiều hơn và được lợi (bài B5).

Bàn tương tác: bản đồ các trò chơi hai người, hai lựa chọn

Bàn mở ra với song đề tù nhân của Ví dụ 1, trong đó hợp tác là im lặng và không hợp tác là khai, đổi sang thang điểm mà cùng hợp tác được 3 và cùng không hợp tác được 1; đổi thang điểm như thế không làm đổi phản ứng tốt nhất nào. Kéo \(T\) và \(S\) để đi khắp bản đồ. Trong mỗi vùng có bao nhiêu cân bằng Nash thuần, và có cân bằng hỗn hợp không? Khi nào cân bằng lại tệ cho cả hai người?

Bàn tương tác cần trình duyệt bật JavaScript.

Điều bạn vừa thấy

Chỉ hai phép so sánh quyết định mọi thứ, \(T\) với 3 và \(S\) với 1, nên các cân bằng không đổi trong mỗi vùng. Khi \(T > 3\) và \(S < 1\), không hợp tác là chiến lược trội nghiêm ngặt, và cân bằng duy nhất tệ hơn ô cùng hợp tác: song đề tù nhân. Khi \(T < 3\) và \(S > 1\), hợp tác trội, và cân bằng duy nhất là ô cùng hợp tác. Khi \(T < 3\) và \(S < 1\), mỗi người muốn làm giống người kia: một trò chơi phối hợp với hai cân bằng thuần, cùng hợp tác và cùng không hợp tác, cộng một cân bằng hỗn hợp. Khi \(T > 3\) và \(S > 1\), mỗi người muốn làm khác người kia: hai cân bằng thuần lệch nhau, một người hợp tác còn người kia không, cộng một cân bằng hỗn hợp. Cân bằng hỗn hợp chỉ xuất hiện khi không ai có chiến lược trội nghiêm ngặt.

Ví dụ 5 (đá phạt đền). Cầu thủ sút về góc trái hay phải; thủ môn đổ về trái hay phải (tính theo cùng một phía nhìn). Xác suất ghi bàn (giả định):

thủ môn đổ trái thủ môn đổ phải
sút trái \(0{,}6\) \(0{,}95\)
sút phải \(0{,}9\) \(0{,}7\)

Cầu thủ muốn xác suất ấy lớn, thủ môn muốn nó nhỏ. Không có cân bằng thuần: nếu cầu thủ luôn sút trái, thủ môn luôn đổ trái, khi đó cầu thủ lại muốn sút phải, và cứ thế. Gọi \(q\) là xác suất cầu thủ sút trái. Nếu thủ môn đổ trái, xác suất ghi bàn là \(0{,}6q + 0{,}9(1 - q)\); nếu đổ phải, là \(0{,}95q + 0{,}7(1 - q)\). Nếu hai số này khác nhau, thủ môn sẽ luôn đổ về phía có lợi hơn cho mình, và cầu thủ bị khai thác. Vậy trong cân bằng, \(q\) phải làm cho thủ môn bàng quan giữa hai hướng:

\[ 0{,}6q + 0{,}9(1 - q) = 0{,}95q + 0{,}7(1 - q) \iff 0{,}2 = 0{,}55q \iff q = \frac{4}{11}. \]

Tương tự, xác suất \(r\) thủ môn đổ trái phải làm cầu thủ bàng quan: \(0{,}6r + 0{,}95(1 - r) = 0{,}9r + 0{,}7(1 - r)\), tức \(r = \frac{5}{11}\). Xác suất ghi bàn ở cân bằng là \(0{,}6 \cdot \frac{5}{11} + 0{,}95 \cdot \frac{6}{11} = \frac{8{,}7}{11} \approx 0{,}79\). Cách tìm cân bằng hỗn hợp này, trộn sao cho đối thủ không còn gì để chọn, gọi là nguyên lý bàng quan (indifference principle). Có một điều bất ngờ: xác suất trộn của cầu thủ được quyết định bởi các con số của thủ môn chứ không phải của chính cầu thủ, vì nó được chọn để làm thủ môn bàng quan.

Xác suất ghi bàn theo xác suất sút trái, và hai đường phản ứng tốt nhất cắt nhau
Trái: xác suất ghi bàn theo xác suất sút trái \(q\), khi thủ môn đổ trái (cam) hay đổ phải (xanh); hai đường cắt nhau tại \(q = \frac{4}{11}\), nơi thủ môn bàng quan. Phải: phản ứng tốt nhất của mỗi người theo chiến lược của người kia; hai đường chỉ gặp nhau tại cân bằng \(\left(\frac{4}{11}; \frac{5}{11}\right)\).

Bàn tương tác: đá phạt đền và nguyên lý bàng quan

Bàn mở ra với bảng của Ví dụ 5, và cả hai người trộn nửa nửa. Kéo \(q\) của cầu thủ: ở đâu thủ môn không còn khai thác được gì? Kéo \(r\) của thủ môn: ở đâu cầu thủ không còn khai thác được gì? Rồi đổi ô "sút trái mà thủ môn đổ phải": khi cú sút ấy tốt hơn, ở cân bằng cầu thủ sút trái nhiều hơn hay ít hơn?

Bàn tương tác cần trình duyệt bật JavaScript.

Điều bạn vừa thấy

Với mỗi \(q\), thủ môn chọn hướng cho xác suất ghi bàn nhỏ hơn, nên cầu thủ chỉ chắc chắn đạt nét đậm, đường thấp hơn trong hai đường. Nét đậm cao nhất đúng chỗ hai đường cắt nhau, nơi thủ môn bàng quan: đó là \(q\) của cân bằng. Lệch khỏi chỗ ấy về phía nào, thủ môn cũng có một hướng đổ làm cầu thủ thiệt. Nhìn từ thủ môn cũng vậy, với đường cao hơn và chỗ thấp nhất của nó. Khi ô "sút trái mà thủ môn đổ phải" tăng, hai chỗ cắt nhau cùng dời đi: ở cân bằng, thủ môn đổ trái nhiều hơn, còn cầu thủ lại sút trái ít hơn.

Ví dụ 6 (ai đi trước). Không phải trò chơi nào cũng diễn ra cùng lúc. Một hãng mới (số liệu giả định, lợi nhuận tính bằng tỉ đồng) cân nhắc có vào một thị trường do một hãng cũ nắm giữ hay không; nếu hãng mới vào, hãng cũ chọn chia sẻ thị trường hay mở chiến tranh giá.

flowchart LR
  M{"hãng mới"} -->|"không vào"| K(("0; 10"))
  M -->|"vào"| C{"hãng cũ"}
  C -->|"chia sẻ"| S(("3; 5"))
  C -->|"chiến tranh giá"| W(("-2; 2"))

Một trò chơi như thế, nơi người chơi đi lần lượt và biết nước đi trước đó, gọi là trò chơi tuần tự (sequential game). Giải bằng quy nạp lùi của Chương 57: nếu hãng mới đã vào, hãng cũ chọn chia sẻ (\(5 > 2\)); biết vậy, hãng mới vào (\(3 > 0\)). Lời đe dọa "vào là tôi đánh giá" không đáng tin, vì khi hãng mới đã vào thì đánh giá chỉ làm hãng cũ thiệt thêm. Thứ tự nước đi cũng thay đổi kết quả: trong trò chơi đoán đồng xu, nếu B được nhìn mặt đồng xu của A rồi mới chọn, B luôn thắng. Đi sau có lợi ở đó, còn trong trò chơi phối hợp, người đi trước chọn được cân bằng mình thích.

Ví dụ 7 (khi chơi nhiều ván). Giả sử song đề tù nhân được chơi nhiều ván, và sau mỗi ván có xác suất \(\delta\) sẽ còn một ván nữa. Xét chiến lược: im lặng cho tới khi đối phương khai một lần, từ đó khai mãi mãi. Nếu cả hai theo chiến lược ấy, mỗi ván mỗi người chịu 1 năm, và tổng kỳ vọng là \(-(1 + \delta + \delta^2 + \dots) = -\frac{1}{1 - \delta}\) (cấp số nhân của Chương 31). Nếu một người khai ngay ván đầu, họ được 0 ở ván ấy nhưng sau đó mỗi ván chịu 5 năm: tổng kỳ vọng \(-\frac{5\delta}{1 - \delta}\). Giữ im lặng tốt hơn khi \(-\frac{1}{1 - \delta} \geq -\frac{5\delta}{1 - \delta}\), tức \(\delta \geq \frac15\). Với \(\delta = 0{,}9\), im lặng mãi cho \(-10\), còn khai sớm cho \(-45\). Khi tương lai đủ quan trọng, hợp tác trở thành hợp lý với từng người. Trong một trò chơi lặp lại (repeated game), một chiến lược rất đơn giản, ăn miếng trả miếng (tit for tat), tức ván đầu hợp tác rồi mỗi ván sau làm đúng như đối phương đã làm ở ván trước, đã thắng các cuộc thi đấu giữa những chương trình máy tính chơi song đề tù nhân do nhà khoa học chính trị Robert Axelrod tổ chức.

Ranh giới

Cân bằng Nash không nhất thiết tốt cho ai. Nó chỉ là một trạng thái không ai muốn một mình rời bỏ. Trong song đề tù nhân, cân bằng duy nhất tệ hơn một kết cục khác cho cả hai người; trong cạnh tranh giá, một cân bằng tệ hơn cân bằng kia cho cả hai hãng.

Có trò chơi không có cân bằng thuần. Đoán đồng xu, oẳn tù tì, đá phạt đền không có ô nào là cân bằng. Nhưng theo định lý Nash (Nash's theorem), mọi trò chơi với hữu hạn chiến lược đều có ít nhất một cân bằng nếu cho phép chiến lược hỗn hợp (Định lý 7).

Nhiều cân bằng thì lý thuyết không chọn giúp. Với trò chơi phối hợp, cân bằng nào xảy ra là do lịch sử, quy ước hay một tín hiệu chung quyết định, không phải do bảng lợi ích.

Chiến lược hỗn hợp không có nghĩa là chơi bừa. Xác suất trộn được xác định chính xác bởi nguyên lý bàng quan; trộn sai tỉ lệ thì bị khai thác.

Người thật không luôn tính toán như trong mô hình. Trong nhiều thí nghiệm, người ta hợp tác trong những song đề chỉ chơi một lần, và từ chối những lời đề nghị họ thấy bất công dù từ chối làm họ thiệt. Mô hình giả định mỗi người biết luật chơi, biết lợi ích của mọi người và chỉ quan tâm tới lợi ích của mình; khi những giả định ấy sai, kết luận cũng có thể sai. Lý thuyết trò chơi giúp suy nghĩ rõ ràng về tương tác, không phải một cỗ máy tiên đoán chính xác hành vi.

Phát biểu chặt chẽ

Định nghĩa 1. Một trò chơi hai người gồm hai tập chiến lược hữu hạn \(S_A\), \(S_B\) và hai hàm lợi ích \(u_A, u_B: S_A \times S_B \to \mathbb{R}\). Chiến lược \(s \in S_A\) là phản ứng tốt nhất với \(t \in S_B\) nếu \(u_A(s, t) \geq u_A(s', t)\) với mọi \(s' \in S_A\); tương tự cho B. Cặp \((s^*, t^*)\) là một cân bằng Nash thuần nếu \(s^*\) là phản ứng tốt nhất với \(t^*\) và \(t^*\) là phản ứng tốt nhất với \(s^*\).

Định nghĩa 2. Một chiến lược hỗn hợp của A là một phân phối xác suất \(p\) trên \(S_A\), và của B là một phân phối \(q\) trên \(S_B\). Khi A và B chọn độc lập, lợi ích kỳ vọng của A là \(U_A(p, q) = \sum_{s, t} p(s)\,q(t)\,u_A(s, t)\), tương tự cho B. Cặp \((p^*, q^*)\) là một cân bằng Nash hỗn hợp nếu \(U_A(p^*, q^*) \geq U_A(p, q^*)\) với mọi \(p\) và \(U_B(p^*, q^*) \geq U_B(p^*, q)\) với mọi \(q\).

Định lý 3 (chiến lược trội). Nếu A có một chiến lược trội nghiêm ngặt \(s^*\) và B có một chiến lược trội nghiêm ngặt \(t^*\), thì \((s^*, t^*)\) là cân bằng Nash thuần duy nhất.

Chứng minh. Vì \(s^*\) trội nghiêm ngặt, \(u_A(s^*, t) > u_A(s, t)\) với mọi \(s \neq s^*\) và mọi \(t\); nói riêng với \(t = t^*\), nên \(s^*\) là phản ứng tốt nhất (duy nhất) với \(t^*\). Tương tự \(t^*\) là phản ứng tốt nhất với \(s^*\), nên \((s^*, t^*)\) là cân bằng. Nếu \((s, t)\) là một cân bằng với \(s \neq s^*\), thì \(u_A(s^*, t) > u_A(s, t)\), nên \(s\) không phải phản ứng tốt nhất với \(t\): mâu thuẫn. Vậy mọi cân bằng có \(s = s^*\), và tương tự \(t = t^*\). \(\square\)

Mệnh đề 4 (cân bằng là điểm bất động). Giả sử mỗi chiến lược của đối thủ có đúng một phản ứng tốt nhất, và gọi \(\beta_A(t)\), \(\beta_B(s)\) là các phản ứng ấy. Khi đó \((s^*, t^*)\) là cân bằng Nash thuần khi và chỉ khi nó là điểm bất động của hàm \(F(s, t) = \big(\beta_A(t), \beta_B(s)\big)\).

Chứng minh. \(F(s^*, t^*) = (s^*, t^*)\) nghĩa là \(\beta_A(t^*) = s^*\) và \(\beta_B(s^*) = t^*\), tức mỗi chiến lược là phản ứng tốt nhất với chiến lược kia, đúng là Định nghĩa 1. \(\square\)

Mệnh đề 5 (nguyên lý bàng quan). Trong một cân bằng Nash hỗn hợp \((p^*, q^*)\), mọi chiến lược thuần \(s\) mà A dùng với xác suất \(p^*(s) > 0\) đều cho cùng một lợi ích kỳ vọng \(U_A(s, q^*)\), bằng \(U_A(p^*, q^*)\), và không chiến lược thuần nào cho A nhiều hơn thế. Điều tương tự đúng với B.

Chứng minh. Gọi \(M = \max_{s} U_A(s, q^*)\). Vì \(U_A(p^*, q^*) = \sum_s p^*(s)\,U_A(s, q^*)\) là trung bình có trọng số của các số \(U_A(s, q^*)\), nó không vượt quá \(M\). Nếu có một \(s\) với \(p^*(s) > 0\) và \(U_A(s, q^*) < M\), chuyển xác suất của \(s\) sang một chiến lược đạt \(M\) sẽ làm tăng lợi ích kỳ vọng, trái với việc \(p^*\) là phản ứng tốt nhất với \(q^*\). Vậy mọi chiến lược được dùng đều cho đúng \(M\), và \(U_A(p^*, q^*) = M\). \(\square\)

Mệnh đề 6 (hợp tác trong trò chơi lặp lại). Trong song đề tù nhân của Ví dụ 1 lặp lại với xác suất tiếp tục \(\delta < 1\), nếu đối phương theo chiến lược "im lặng cho tới khi bị khai, từ đó khai mãi mãi", thì im lặng mãi mãi cho tổng kỳ vọng lớn hơn hay bằng khai ngay khi và chỉ khi \(\delta \geq \frac15\).

Chứng minh. Im lặng mãi mãi cho \(-\sum_{k \geq 0} \delta^k = -\frac{1}{1 - \delta}\). Khai ở ván đầu cho 0 ở ván ấy; từ ván sau đối phương khai mãi mãi, và khai tiếp là tốt nhất cho người đã khai (\(-5 > -10\)), nên tổng là \(-5 \sum_{k \geq 1} \delta^k = -\frac{5\delta}{1 - \delta}\). Nhân hai vế của \(-\frac{1}{1 - \delta} \geq -\frac{5\delta}{1 - \delta}\) với \(1 - \delta > 0\) được \(-1 \geq -5\delta\), tức \(\delta \geq \frac15\). Khai ở một ván muộn hơn cũng dẫn tới cùng phép so sánh, chỉ nhân thêm với xác suất tới được ván ấy. \(\square\)

Định lý 7 (Nash, 1950; phát biểu). Mọi trò chơi với hữu hạn người chơi và hữu hạn chiến lược đều có ít nhất một cân bằng Nash nếu cho phép chiến lược hỗn hợp.

Chứng minh của Nash dùng một định lý về sự tồn tại điểm bất động, nằm ngoài cuốn sách này; điều đáng nhớ là cân bằng, một lần nữa, là một điểm bất động.

Sợi chỉ

  • S1. Bất biến qua biến đổi. Cân bằng Nash là một điểm bất động của phép "mỗi người chuyển sang phản ứng tốt nhất" (Mệnh đề 4), như điểm bất động của phép lặp ở Chương 24: trạng thái không đổi khi mọi người cùng cân nhắc lại. Một quy ước xã hội như đi bên phải là một cân bằng được chọn: quy ước là tùy ý, còn tính bền vững của nó là cấu trúc, đúng như sự phân biệt ở Chương 1.
  • S4. Cục bộ và toàn cục. Lựa chọn hợp lý cho từng người có thể dẫn tới kết cục tệ cho mọi người (song đề tù nhân, cân bằng giá thấp); khi trò chơi lặp lại đủ lâu (\(\delta \geq \frac15\)), lợi ích dài hạn kéo hành vi từng ván về phía hợp tác.
  • S3. Thứ tự của biến đổi. Ai đi trước thay đổi kết quả: đi sau thì thắng trò đoán đồng xu, đi trước thì chọn được cân bằng mình thích trong trò chơi phối hợp; lời đe dọa không đáng tin bị quy nạp lùi loại bỏ. Như trò chơi thách và đáp của Chương 15, thứ tự nước đi là một phần của luật chơi.

Tóm tắt

  • Một trò chơi gồm người chơi, chiến lược và lợi ích; với hai người, bảng lợi ích ghi cặp lợi ích ở mỗi ô.
  • Phản ứng tốt nhất là chiến lược tốt nhất khi biết người kia chơi gì; chiến lược bị trội có thể gạch bỏ.
  • Cân bằng Nash là một tổ hợp chiến lược mà không ai được lợi khi một mình đổi khác: một điểm bất động của phản ứng tốt nhất; tìm nó trên bảng bằng cách đánh dấu phản ứng tốt nhất của cả hai người.
  • Song đề tù nhân: hợp lý cá nhân dẫn tới thiệt hại tập thể; lặp lại đủ lâu thì hợp tác có thể bền vững.
  • Trò chơi phối hợp có nhiều cân bằng; một quy ước xã hội là một cân bằng được chọn và tự duy trì.
  • Có trò chơi không có cân bằng thuần; chiến lược hỗn hợp tìm bằng nguyên lý bàng quan, và theo định lý Nash, cân bằng hỗn hợp luôn tồn tại.
  • Trong trò chơi tuần tự, quy nạp lùi loại bỏ những lời đe dọa không đáng tin, và thứ tự nước đi thay đổi kết quả.

Bài tập

A. Tư duy

A1. Trong song đề tù nhân, mỗi người đều lựa chọn hợp lý. Vì sao kết cục chung vẫn tệ? Nêu một tình huống đời thường có cùng cấu trúc.

Lời giải

Mỗi người chỉ tính lợi ích của mình và coi lựa chọn của người kia là cho trước. Khai tốt hơn cho mình bất kể người kia làm gì, nhưng mỗi lần một người khai, người kia chịu thêm nhiều năm tù; không ai tính cái thiệt mình gây cho người kia. Cấu trúc ấy gặp ở nhiều nơi: mỗi hộ gia đình được lợi khi xả rác bừa thay vì mang đi xa, nhưng khi mọi người cùng làm thế thì cả khu phố bẩn; hai quốc gia chạy đua vũ trang dù cả hai sẽ tốt hơn nếu cùng giảm.

A2. Vì sao quy ước đi bên phải tự duy trì mà không cần ai giám sát từng người?

Lời giải

Vì (phải; phải) là một cân bằng Nash: khi mọi người khác đi bên phải, một người đổi sang bên trái chỉ tự chuốc nguy hiểm. Không ai được lợi khi một mình làm trái, nên không cần ép buộc từng người; luật chỉ cần giúp mọi người biết cân bằng nào đang được chọn.

A3. Vì sao trong trò chơi đoán đồng xu, chơi theo một quy luật dễ đoán là một chiến lược tồi, dù trò chơi hoàn toàn cân xứng?

Lời giải

Nếu A có xu hướng giơ sấp nhiều hơn, B chỉ cần giơ ngửa nhiều hơn để thắng trung bình mỗi ván. Chỉ khi A trộn đúng \(\frac12\) và \(\frac12\) thì B không khai thác được gì. Trong trò chơi tổng bằng không không có cân bằng thuần, tính khó đoán là điều kiện để không bị thua.

A4. Trong Ví dụ 5, vì sao xác suất sút trái của cầu thủ lại được tính từ các con số liên quan tới lựa chọn của thủ môn?

Lời giải

Trong cân bằng hỗn hợp, cầu thủ trộn sao cho thủ môn không còn hướng nào tốt hơn hướng kia; nếu không, thủ môn sẽ luôn đổ về hướng có lợi và cầu thủ bị khai thác. Điều kiện "thủ môn bàng quan" là một phương trình mà ẩn là \(q\) và hệ số là các xác suất ghi bàn theo từng hướng đổ của thủ môn. Vì thế \(q\) được quyết định bởi cách mà lựa chọn của thủ môn ảnh hưởng tới kết quả, chứ không phải bởi mong muốn của cầu thủ.

B. Tính toán

B1. (Giả định.) Hai bạn hẹn nhau đi chơi nhưng quên thỏa thuận đi đâu; mỗi người chọn đi xem phim hay xem bóng đá. Cùng xem phim: A được 2, B được 1; cùng xem bóng đá: A được 1, B được 2; lạc nhau: cả hai được 0. Tìm các cân bằng thuần và cân bằng hỗn hợp.

Lời giải

Đánh dấu phản ứng tốt nhất cho hai cân bằng thuần: (phim; phim) với \((2; 1)\) và (bóng đá; bóng đá) với \((1; 2)\). Cân bằng hỗn hợp: gọi \(p\) là xác suất A chọn phim; B bàng quan khi \(1 \cdot p = 2(1 - p)\), tức \(p = \frac23\). Gọi \(q\) là xác suất B chọn phim; A bàng quan khi \(2q = 1 \cdot (1 - q)\), tức \(q = \frac13\). Khi đó mỗi người được kỳ vọng \(\frac23\), thấp hơn ở cả hai cân bằng thuần, vì hai người hay lạc nhau.

B2. Tìm mọi cân bằng Nash thuần của trò chơi sau (A chọn hàng, B chọn cột).

L C R
T \(4; 3\) \(1; 1\) \(2; 2\)
M \(3; 0\) \(2; 4\) \(1; 3\)
B \(2; 2\) \(3; 1\) \(3; 1\)
Lời giải

Phản ứng tốt nhất của A: với L là T (4), với C là B (3), với R là B (3). Phản ứng tốt nhất của B: với T là L (3), với M là C (4), với B là L (2). Ô có cả hai dấu chỉ có (T; L): cân bằng Nash thuần duy nhất, với lợi ích \((4; 3)\). Chẳng hạn ô (B; C) có dấu của A nhưng không có dấu của B, vì khi A chọn B, B thích L hơn C.

B3. Giải bằng cách gạch các chiến lược bị trội nghiêm ngặt:

L C R
U \(3; 2\) \(2; 1\) \(4; 0\)
M \(1; 1\) \(1; 3\) \(2; 2\)
D \(2; 4\) \(0; 2\) \(3; 3\)
Lời giải

Với A, hàng U cho \((3; 2; 4)\), lớn hơn hẳn M \((1; 1; 2)\) và D \((2; 0; 3)\) ở từng cột, nên M và D bị trội nghiêm ngặt. Gạch chúng đi, A chơi U; khi đó B chọn L (\(2 > 1 > 0\)). Kết quả (U; L) với lợi ích \((3; 2)\), và đó là cân bằng Nash duy nhất.

B4. Trò chơi tổng bằng không: A được 2 nếu cả hai chọn sấp, được 1 nếu cả hai chọn ngửa, và mất 1 nếu hai người chọn khác nhau (B nhận đúng phần A mất). Tìm cân bằng hỗn hợp và lợi ích kỳ vọng của A.

Lời giải

Không có cân bằng thuần (đánh dấu cho thấy không ô nào có hai dấu). Gọi \(p\) là xác suất A chọn sấp. B bàng quan khi lợi ích của A như nhau với hai lựa chọn của B: \(2p - (1 - p) = -p + (1 - p)\), tức \(3p - 1 = 1 - 2p\), \(p = \frac25\). Tương tự, xác suất B chọn sấp là \(q = \frac25\) (từ \(2q - (1 - q) = -q + (1 - q)\)). Lợi ích kỳ vọng của A là \(3 \cdot \frac25 - 1 = \frac15\) mỗi ván: trò chơi có lợi cho A.

B5. Trong oẳn tù tì (thắng được 1, thua mất 1, hòa 0), đối thủ ra búa với xác suất \(\frac12\), bao \(\frac14\), kéo \(\frac14\). Phản ứng tốt nhất của bạn là gì và được kỳ vọng bao nhiêu?

Lời giải

Ra bao: thắng búa (\(\frac12\)), hòa bao (\(\frac14\)), thua kéo (\(\frac14\)): kỳ vọng \(\frac12 - \frac14 = \frac14\). Ra búa: hòa búa, thua bao, thắng kéo: \(-\frac14 + \frac14 = 0\). Ra kéo: thua búa, thắng bao, hòa kéo: \(-\frac12 + \frac14 = -\frac14\). Phản ứng tốt nhất là ra bao, được \(\frac14\) mỗi ván. Chỉ khi đối thủ trộn đều \(\frac13\) thì không lựa chọn nào có lợi.

B6. (Giả định.) Hai cửa hàng chọn giữ giá hay giảm giá. Cùng giữ: mỗi cửa hàng lãi 10; cùng giảm: mỗi cửa hàng lãi 6; một bên giảm còn bên kia giữ: bên giảm lãi 14, bên giữ lãi 3. Tìm cân bằng Nash. Nó có tốt nhất cho hai cửa hàng không?

Lời giải

Với mỗi cửa hàng, giảm giá cho \(14 > 10\) khi bên kia giữ và \(6 > 3\) khi bên kia giảm: giảm giá là chiến lược trội nghiêm ngặt. Theo Định lý 3, (giảm; giảm) với \((6; 6)\) là cân bằng duy nhất, dù (giữ; giữ) với \((10; 10)\) tốt hơn cho cả hai. Đây là một song đề tù nhân; nó cũng giải thích vì sao luật pháp nhiều nước cấm các hãng thỏa thuận ngầm để cùng giữ giá cao.

B7. Trong Ví dụ 6, nếu chiến tranh giá cho hãng cũ lợi nhuận 6 (chẳng hạn vì nó dọa được các đối thủ khác), kết quả thay đổi thế nào?

Lời giải

Quy nạp lùi: sau khi hãng mới vào, hãng cũ chọn chiến tranh giá (\(6 > 5\)), để lại cho hãng mới \(-2\). Biết vậy, hãng mới không vào (\(0 > -2\)). Kết quả là (không vào) với lợi nhuận \((0; 10)\): lời đe dọa giờ đáng tin, vì thực hiện nó có lợi cho chính hãng cũ.

B8. Trong một song đề tù nhân, cùng im lặng mỗi người chịu 1 năm, cùng khai mỗi người 4 năm, khai khi người kia im lặng được tha, còn im lặng khi người kia khai chịu 8 năm. Với chiến lược đối phương như ở Ví dụ 7, xác suất tiếp tục \(\delta\) phải bằng bao nhiêu để im lặng mãi mãi không thua khai ngay?

Lời giải

Im lặng mãi cho \(-\frac{1}{1 - \delta}\); khai ngay cho \(0 - \frac{4\delta}{1 - \delta}\). Cần \(-1 \geq -4\delta\), tức \(\delta \geq \frac14\). Hình phạt khi cùng khai nhẹ hơn (4 năm thay vì 5), nên cần tương lai quan trọng hơn một chút để giữ hợp tác.

B9. (Giả định.) Làm lại Ví dụ 5 với xác suất ghi bàn: sút trái và thủ môn đổ trái \(0{,}4\), sút trái và đổ phải \(0{,}9\), sút phải và đổ trái \(0{,}8\), sút phải và đổ phải \(0{,}5\).

Lời giải

Thủ môn bàng quan: \(0{,}4q + 0{,}8(1 - q) = 0{,}9q + 0{,}5(1 - q)\), tức \(0{,}8 - 0{,}4q = 0{,}5 + 0{,}4q\), \(q = \frac38\). Cầu thủ bàng quan: \(0{,}4r + 0{,}9(1 - r) = 0{,}8r + 0{,}5(1 - r)\), tức \(0{,}9 - 0{,}5r = 0{,}5 + 0{,}3r\), \(r = \frac12\). Xác suất ghi bàn ở cân bằng là \(0{,}9 - 0{,}5 \cdot \frac12 = 0{,}65\).

C. Phản ví dụ và chứng minh

C1. Chứng minh rằng một chiến lược bị trội nghiêm ngặt không bao giờ có mặt trong một cân bằng Nash thuần.

Lời giải

Giả sử \(s\) bị trội nghiêm ngặt bởi \(s'\): \(u_A(s', t) > u_A(s, t)\) với mọi \(t\). Nếu \((s, t)\) là một cân bằng, thì \(s\) là phản ứng tốt nhất với \(t\), tức \(u_A(s, t) \geq u_A(s', t)\), trái với bất đẳng thức trên. \(\square\) Vì thế gạch bỏ chiến lược bị trội không làm mất cân bằng nào.

C2. Chứng minh rằng trong trò chơi đoán đồng xu, cặp chiến lược hỗn hợp \(\left(\frac12; \frac12\right)\) cho cả hai người là cân bằng Nash duy nhất.

Lời giải

Gọi \(p\), \(q\) là xác suất A, B chọn sấp. Lợi ích kỳ vọng của A là \(pq + (1 - p)(1 - q) - p(1 - q) - (1 - p)q = (2p - 1)(2q - 1)\). Nếu \(p > \frac12\), B (muốn lợi ích của A nhỏ) chỉ có phản ứng tốt nhất là \(q = 0\); khi đó A muốn làm nhỏ nhất \((2p - 1) \cdot (-1)\), tức muốn \(p = 0\), trái với \(p > \frac12\). Tương tự, \(p < \frac12\) dẫn tới \(q = 1\) rồi \(p = 1\), mâu thuẫn. Vậy \(p = \frac12\), và lập luận đối xứng cho \(q = \frac12\). Ngược lại, với \(p = q = \frac12\) mọi lựa chọn của mỗi người đều cho kỳ vọng 0, nên đó là cân bằng. \(\square\)

C3. Chứng minh hoặc bác bỏ: nếu một người chơi có chiến lược trội nghiêm ngặt, trò chơi có đúng một cân bằng Nash thuần.

Lời giải

Sai. Xét A có hai hàng U, D và B có hai cột L, R, với lợi ích (U; L) \(= (2; 1)\), (U; R) \(= (2; 1)\), (D; L) \(= (1; 0)\), (D; R) \(= (0; 2)\). Hàng U trội nghiêm ngặt (\(2 > 1\) và \(2 > 0\)). Nhưng khi A chơi U, B được 1 dù chọn L hay R, nên cả (U; L) lẫn (U; R) đều là cân bằng. Mệnh đề đúng nếu thêm điều kiện phản ứng tốt nhất của người kia với chiến lược trội là duy nhất, hoặc cả hai người đều có chiến lược trội nghiêm ngặt (Định lý 3).

Câu hỏi để ngỏ

Một cỗ máy có thể "học" để chơi trò chơi, trả lời câu hỏi, viết văn. Nó dùng những công cụ nào trong số những gì ta đã học, và hiểu chúng giúp ta kiểm chứng nó như thế nào?