Trò chơi Bayes

Trong lý thuyết trò chơi, trò chơi Bayes là trò chơi mà thông tin về đặc điểm của những người chơi còn thiếu (ví dụ, không biết về thu hoạch của đối phương). Theo phương pháp của John C. Harsanyi,^[1] có thể mô hình hóa trò chơi Bayes bằng cách bổ sung một người chơi – gọi là Tạo hóa/Tự nhiên. Vai trò của Tự nhiên là đặt ra một biến số ngẫu nhiên cho mỗi người chơi, bao gồm các kiểu người chơi khác nhau, và xác suất (hoặc phương trình xác suất) tương ứng với mỗi kiểu. Trong khi diễn ra trò chơi, ‘’Tự nhiên’‘ sẽ ngẫu nhiên chọn một kiểu người chơi, tùy theo xác suất phân bố các kiểu có thể xảy ra với mỗi người chơi. Mô hình hóa trò chơi Bayes theo phương pháp Harsanyi sẽ biến ‘’trò chơi thiếu thông tin’‘ thành ‘’trò chơi thông tin không hoàn hảo (tức là, người chơi không nắm được tất cả các bước đã diễn ra trong lịch sử trò chơi)’‘. Kiểu người chơi sẽ quyết định phương trình thu hoạch của người chơi đó. Xác suất tương ứng với mỗi kiểu người chơi, là xác suất mà người chơi thực sự hành động theo kiểu đó trên thực tế. Trong trò chơi Bayes, thiếu thông tin nghĩa là ít nhất một người chơi không biết kiểu người chơi (và đồng thời, không biết phương trình thu hoạch) của đối phương.

Những trò chơi như vậy được gọi là trò chơi Bayes, gọi tên theo cách phân tích xác suất trong trò chơi. Ban đầu, người chơi sẽ đặt ra ‘’niềm tin’‘ về kiểu người chơi của đối phương (‘’niềm tin’‘ là phân bố xác suất về các kiểu có thể xảy ra với một người chơi), và có thể củng cố/ sửa đổi ‘’niềm tin’‘ đó theo Nguyên tắc Bayes trong quá trình tham gia trò chơi, ví dụ, ‘’niềm tin’‘ của một người chơi về đối phương có thể thay đổi dựa trên các hành động người đó đã thực hiện. Ở đây, người chơi thiếu thông tin, và niềm tin được mô hình hóa, do đó những trò chơi này cũng được sử dụng khi phân tích các trường hợp thông tin không hoàn hảo.

Biểu diễn chi tiết trò chơi

Đối với những trò chơi KHÔNG-PHẢI ‘’trò chơi Bayes’‘ với thông tin hoàn hảo, ‘’biểu diễn trò chơi theo dạng thông thường’‘ tức là nêu ra chi tiết các ‘’khoảng chiến lược’‘ và ‘’phương trình thu hoạch’‘ của tất cả người chơi. Một „chiến lược’‘ của người chơi là một kế hoạch hành động đầy đủ, tính đến tất cả các trường hợp có thể xảy ra trong trò chơi, ngay cả khi trường hợp đó có thể không bao giờ xảy ra. ‘’Khoảng chiến lược’‘ của người chơi là tập hợp tất cả các chiến lược mà người chơi có thể sử dụng. ‘’Phương trình thu hoạch’‘ là phương trình bao gồm các hồ sơ chiến lược và các khoản thu hoạch (thường là một loạt số thực), trong đó hồ sơ chiến lược là một véc tơ chỉ ra chiến lược cho tất cả người chơi.

Đối với ‘’trò chơi Bayes’‘, cần chỉ ra khoảng chiến lược, các kiểu người chơi, phương trình thu hoạch và niềm tin cho mỗi người chơi. Một ‘’chiến lược’‘ của người chơi là một kế hoạch hành động đầy đủ, tính đến tất cả các trường hợp có thể xảy ra‚ đối với mỗi kiểu người chơi. Một chiến lược phải chỉ ra hành vi của người chơi không chỉ trong trường hợp kiểu người chơi đã được ấn định, mà còn chỉ ra cả những hành động sẽ được thực hiện trong các trường hợp người chơi rơi vào kiểu khác. Khoảng chiến lược vẫn được định nghĩa như trên. Các kiểu người chơi đơn giản là tập hợp tất cả các kiểu có thể xảy ra với mỗi người chơi. Niềm tin của người chơi miêu tả mức độ người chơi không chắc chắn về kiểu người chơi của đối phương. Mỗi niềm tin của người chơi là xác suất đối phương thuộc về một kiểu nhất định, ấn định trước kiểu người chơi của người đang mang niềm tin đó. (ví dụ, niềm tin là xác suất xảy ra các kiểu người chơi của đối thủ, ấn định trước kiểu người chơi của người đó: P (kiểu người chơi của đối phương | kiểu người chơi của người chơi đó). Phương trình thu hoạch là phương trình gồm 2 phần, bao gồm ‘’hồ sơ chiến lược’‘ và ‘’kiểu người chơi’‘. Nếu người chơi có phương trình thu hoạch $U(x,y)$ và thuộc kiểu người chơi t, những gì người đó thu hoạch được sẽ là $U(x^{*},t)$ , trong đó $x^{*}$ là hồ sơ chiến lược được thực hiện trong trò chơi (ví dụ, véc tơ liệt kê các chiến lược đã được thực hiện) Một trong các định nghĩa chính thức được biểu diễn như sau:

Trò chơi được định nghĩa là: $G=\langle N,\Omega ,\langle A_{i},u_{i},T_{i},\tau _{i},p_{i},C_{i}\rangle _{i\in N}\rangle$ , trong đó

$N$ là tập hợp người chơi.
$\Omega$ là tập hợp các trạng thái tự nhiên. Ví dụ, trong trò chơi bài tây, trạng thái tự nhiên có thể là bất kì quân bài nào
$A_{i}$ là tập hợp các hành động của người chơi $i$ . Ta coi: $A=A_{1}\times A_{2}\times \dotsb \times A_{N}$ .
$T_{i}$ là kiểu người chơi của người chơi $i$ , được định nghĩa theo phương trình $\tau _{i}\colon \Omega \rightarrow T_{i}$ . Do đó, đối với mỗi trạng thái tự nhiên, trò chơi sẽ có các kiểu người chơi khác nhau. Khoản thu hoạch của người chơi sẽ quyết định kiểu người chơi. Những người chơi thu hoạch cùng một lượng bằng nhau sẽ thuộc về cùng một kiểu người chơi.
$C_{i}\subseteq A_{i}\times T_{i}$ định nghĩa các hành động có thể được thực hiện bởi người chơi $i$ thuộc kiểu $T_{i}$ .
$u_{i}\colon \Omega \times A\rightarrow R$ là phương trình thu hoạch của người chơi $i$ .. Nếu diễn đạt một cách chính thống hơn, ta coi $L=\{(\omega ,a_{1},\dotsc ,a_{N})\mid \omega \in \Omega ,\forall i,(a_{i},\tau _{i}(\omega ))\in C_{i}\}$ , và $u_{i}\colon L\rightarrow R$ .
$p_{i}$ là phân bố xác suất của các trạng thái tự nhiên $\Omega$ cho mỗi người chơi $i$ , tức là, mỗi người chơi có các quan điểm khác nhau về phân bố xác suất của các trạng thái tự nhiên. Trong trò chơi, họ không bao giờ biết được chính xác trạng thái tự nhiên thật sự

Chiến lược thuần túy (pure strategy) $s_{i}\colon T_{i}\rightarrow A_{i}$ cần thỏa mãn $(s_{i}(t_{i}),t_{i})\in C_{i}$ với mọi kiểu người chơi $t_{i}$ . Do đó, chiến lược của mỗi người chơi chỉ phụ thuộc vào kiểu người chơi của bản thân người đó, vì người đó có thể không biết gì về kiểu người chơi của đối phương. Và thu hoạch kì vọng (expected payoff) của người chơi $i$ đối với hồ sơ chiến lược đó được biểu diễn bằng $u_{i}(S)=E_{\omega \sim p_{i}}[u_{i}(\omega ,s_{1}(\tau _{1}(\omega )),\dotsc ,s_{N}(\tau _{N}(\omega )))]$ .

Gọi $S_{i}$ là tập hợp các chiến lược thuần túy, ta có, $S_{i}=\{s_{i}\colon T_{i}\rightarrow A_{i}\mid (s_{i}(t_{i}),t_{i})\in C_{i},\forall t_{i}\}.$

Cân bằng Bayes của trò chơi $G$ được định nghĩa là cân bằng Nash (có thể là cân bằng chiến lược thuần túy hoặc hỗn hợp) của trò chơi ${\hat {G}}=\langle N,{\hat {A}}=S_{1}\times S_{2}\times \dotsb \times S_{N},{\hat {u}}=u\rangle$ . Do đó, đối với mỗi trò chơi hữu hạn $G$ , luôn tồn tại cân bằng Bayes.

Đánh tín hiệu

‘’Trò chơi đánh tín hiệu’’ là một ví dụ về trò chơi Bayes. Trong trò chơi này, bên nắm giữ thông tin (bên đại lý - ‘‘agent’‘) biết rõ kiểu người chơi của bản thân, trong khi bên thiếu thông tin (bên chủ - ‘‘principal’‘) không biết kiểu người chơi của đối phương (bên đại lý - agent). Trong một số trò chơi như vậy, bên chủ có thể suy diễn ra kiểu người chơi của bên đại lý, dựa vào những hành động mà bên đại lý đã thực hiện (như là tín hiệu gửi đến bên chủ) trong thể cân bằng riêng rẽ (‘‘separating equilibrium’‘).

Một ví dụ cụ thể của trò chơi đánh tín hiệu là mô hình chợ việc làm. Người chơi bao gồm ứng viên (bên đại lý – nắm giữ thông tin) và nhà tuyển dụng (bên chủ - thiếu thông tin). Có hai kiểu người chơi của ứng viên, ứng viên có kĩ năng và ứng viên không có kĩ năng. Nhà tuyển dụng không biết ứng viên thuộc loại có kĩ năng hay không, nhưng lại biết rằng 90% ứng viên không có kĩ năng, và chỉ có 10% có kĩ năng (kiểu người chơi ‘có kĩ năng’ có xác suất 0.1 và kiểu người chơi ‘không có kĩ năng’ có xác suất 0.9).

Khoảng hành động của nhà tuyển dụng là tập hợp số tự nhiên, biểu diễn số tiền lương, được sử dụng để lập hợp đồng, dựa trên hiệu quả công việc họ mong đợi từ ứng viên. Trả lương cao cho ứng viên có kĩ năng sẽ đem lại cho nhà tuyển dụng khoản thu hoạch lớn hơn, trong khi tiền lương trả cho ứng viên không có kĩ năng sẽ đem lại hiệu quả không rõ rệt. Do đó, khoản thu hoạch của nhà tuyển dụng được xác định bởi kĩ năng của ứng viên (nếu ứng viên chấp nhận hợp đồng) và khoản tiền lương được thanh toán. Một điểm quan trọng là, nhà tuyển dụng lựa chọn hành động (đưa ra mức lương bao nhiêu) dựa vào niềm tin về kĩ năng của ứng viên, và niềm tin này đa phần được xác định nhờ vào dấu hiệu do ứng viên đưa ra.

Các hành động ứng viên có thể thực hiện bao gồm 2 hành động: hoặc đi học đại học, hoặc bỏ đại học. Đối với ứng viên có kĩ năng, học đại học tốn ít chi phí về tiền bạc/ công sức hơn, vì họ có thể nhận được học bổng, học tập cũng dễ dàng hơn, v.v. Bằng đại học là một ‘’dấu hiệu’’, một phương tiện giúp ứng viên truyền đạt tới nhà tuyển dụng rằng họ có kĩ năng thực sự

Một chiến lược mà nhà tuyển dụng có thể sử dụng, đó là đưa ra mức lương cho phép ứng viên có kĩ năng đi học đại học, (do chi phí thấp hơn) nhưng không đủ cho ứng viên không có kĩ năng bù đắp cho chi phí học đại học. Điều này sẽ tạo ra thể cân bằng riêng rẽ (‘‘separating equilibrium’‘): ứng viên có kĩ năng có thể đánh tín hiệu về kĩ năng của mình, bằng cách đi học đại học, và ứng viên không có kĩ năng không thể làm vậy được. Nhà tuyển dụng có thể quan sát ứng viên nào có thể đi học đại học, và từ đó đạt được khoản thu hoạch cao nhất, bằng cách tăng lương cao cho nhân viên có kĩ năng và lương thấp cho nhân viên không có kĩ năng.

Cân bằng Nash Bayes

Đối với những trò chơi KHÔNG-PHẢI ‘’trò chơi Bayes’‘, một hồ sơ chiến lược được gọi là cân bằng Nash nếu mỗi chiến lược trong hồ sơ đó đều là phản ứng tốt nhất cho mọi chiến lược khác trong hồ sơ, ví dụ, nếu người chơi không thể thực hiện chiến lược nào khác để nhận được khoản thu hoạch lớn hơn, với điều kiện cho trước những chiến lược mà đối thủ sẽ thực hiện. Đối với trò chơi Bayes (trường hợp người chơi không bị tác động bởi rủi ro), người chơi có lý trí sẽ cố gắng đạt được khoản thu hoạch dự tính tối đa, với điều kiện đã có niềm tin về đối thủ (trong trường hợp khác, người chơi có thể thích rủi ro hoặc né ránh rủi ro, ta coi người chơi sẽ cố gắng đạt được khoản lợi ích dự tính tối đa.)

‘’Cân bằng Nash Bayes’’ được định nghĩa là một ‘’hồ sơ chiến lược’’ và ‘’niềm tin của từng người chơi về đối thủ’’, tại đó khoản thu hoạch dự tính của mỗi người chơi là tối đa, với điều kiện cho trước là niềm tin của người chơi về kiểu người chơi của đối thủ và các chiến lược của đối thủ.

Cách giải này sẽ tìm ra nhiều thế cân bằng trong những trò chơi động, khi không có giới hạn về niềm tin của người chơi. Do đó Cân bằng Nash Bayes không phải một công cụ hoàn thiện để phân tích các trò chơi động với thông tin không đầy đủ.

Cân bằng Bayes hoàn hảo

Cân bằng Bayes hoàn hảo chỉ ra những trường hợp cân bằng có khả năng xảy ra trong các trò chơi động, người chơi lần lượt ra quyết định thay vì phải ra quyết định đồng thời. Tương tự, những trường hợp cân bằng có thể xảy ra như cân bằng Nash trong các trò chơi hoàn hảo và đầy đủ thông tin, ví dụ như trường hợp hứa hẹn hoặc đe dọa vô hiệu. Ta có thể loại bỏ những trường hợp cân bằng vô hiệu như vậy trong trò chơi hoàn hảo và đầy đủ thông tin, bằng cách sử dụng cân bằng Bayes hoàn hảo trong từng phân đoạn trò chơi (subgame perfect Nash equilibrium). Tuy nhiên, không phải lúc nào cũng có thể sử dụng cách giải này trong trò chơi thiếu thông tin, vì những trò chơi như vậy chứa khối thông tin không độc lập, và vì phân đoạn trò chơi phải chứa khối thông tin đầy đủ, nên trong nhiều trường hợp, chỉ có một phân đoạn trò chơi duy nhất – đó là toàn bộ trò chơi – và vì thế tất cả các cân bằng Nash đều được coi là cân bằng hoàn hảo cho phân đoạn trò chơi. Ngay cả khi một trò chơi có nhiều hơn một phân đoạn, khái niệm ‘’phân đoạn trò chơi hoàn hảo’’ không thể cắt ngang một khối thông tin, do đó một số cân bằng vô hiệu vẫn không bị loại bỏ.

Để tinh giản các trường hợp cân bằng trong cách giải Bayes Nash hoặc ’phân đoạn trò chơi hoàn hảo, có thể áp dụng cách giải ‘’cân bằng Bayes hoàn hảo’’. Cân bằng Bayes hoàn hảo chính là phân đoạn trò chơi hoàn hảo, vì nó yêu cầu từng phân đoạn trò chơi phải được tối ưu. Tuy nhiên nó đặt ra niềm tin trong từng nốt quyết định, cho phép xử lý triệt để các bước trong khối thông tin không độc lập. Cho tới giờ, khi thảo luận về trò chơi Bayes, ta vẫn coi thông tin là hoàn hảo (hoặc nếu không hoàn hảo, các bước quyết định cũng diễn ra đồng thời). Tuy nhiên khi phân tích trò chơi động, cần phải có phương pháp mô hình hóa thông tin không hoàn hảo. Cân bằng Bayes hoàn hảo cung cấp cho chúng ta phương pháp này: người chơi đặt niềm tin vào các bước trong khối thông tin, điều này có nghĩa là khối thông tin có thể do Tự nhiên tạo ra (trong trường hợp thông tin không đầy đủ) hoặc do người chơi khác tạo ra (trong trường hợp thông tin không hoàn hảo)

Hệ thống niềm tin

Có thể tiếp cận niềm tin của người chơi trong trò chơi Bayes kĩ càng hơn thông qua ‘’cân bằng Bayes hoàn hảo’’. Một hệ thống niềm tin là cách gán xác suất cho từng bước trong trò chơi, sao cho tổng các xác suất trong mỗi khối thông tin bằng 1. Niềm tin của người chơi là xác suất của các bước trong khối thông tin tại đó người chơi đưa ra quyết định. (niềm tin của người chơi có thể được biểu diễn bằng phương trình, hợp nhất các khối thông tin về trong khoảng từ [0,1]). Một hệ thống niềm tin được coi là ‘’thống nhất’’ với một hồ sơ chiến lược cho trước khi và chỉ khi hệ thống này gán xác suất cho từng nốt, và xác suất niềm tin đó được tính bằng xác suất nốt đó diễn ra trong hồ sơ chiến lược, ví dụ bằng Nguyên tắc Bayes.

Lý trí tuần tự

Khái niệm lý trí tuần tự quyết định cách tối ưu phân đoạn trò chơi trong cân bằng Bayes hoàn hảo. Một hồ sơ chiến lược đạt điều kiện lý trí tuần tự tại một khối thông tin nhất định trong một hệ thống niềm tin nhất định khi và chỉ khi thu hoạch dự tính của người chơi sở hữu khối thông tin đó (ví dụ: người chơi có quyền đưa ra quyết định tại khối thông tin đó) đạt mức tối đa, với điều kiện cho trước là các chiến lược của đối thủ. Một hồ sơ chiến lược đạt điều kiện lý trí tuần tự trong một hệ thống niềm tin nhất định nếu nó thỏa mãn điều kiện trên tại tất cả các khối thông tin.

Định nghĩa

Một cân bằng Bayes hoàn hảo là một ‘’hồ sơ chiến lược’’ và một ‘’hệ thống niềm tin’’, tại đó các chiến lược đều đạt điều kiện lý trí tuần tự, với điều kiện cho trước là tồn tại hệ thống niềm tin, và hệ thống niềm tin đó thống nhất với hồ sơ chiến lược tại mọi trường hợp có thể xảy ra.

Cần phải nhất mạnh điều kiện ‘tại mọi trường hợp có thể xảy ra’, vì một số khối thông tin không xảy ra với hồ sơ chiến lược cho trước, và vì vậy không thể áp dụng Nguyên tắc Bayes để tính toán xác suất tại các nốt trong khối thông tin đó. Những khối thông tin đó được coi là ‘’nằm ngoài đường cân bằng’’ và có thể gán bất kì niềm tin nào cho các khối thông tin đó. Các khối thông tin nằm ngoài đường cân bằng chỉ có thể được gán một số niềm tin trong giới hạn chặt chẽ, do yêu cầu cao về tính thống nhất, so với các khối thông tin ‘’hợp lý’’ khác.

Ví dụ

Trò chơi Bayes với thông tin không hoàn hảo, được biểu diễn theo dạng đầy đủ

Thông tin trong trò chơi bên trái này là không hoàn hảo, vì người chơi thứ hai không biết hành động của người chơi thứ nhất khi bắt đầu tham gia trò chơi. Nếu cả hai người chơi đều có lý trí, và cả hai đều biết rằng tất cả bọn họ đều hành động theo lý trí, và mọi người chơi đều biết mọi thông tin mà đối thủ biết (ví dụ, người chơi thứ nhất biết rằng, người chơi thứ hai biết mình hành động theo lý trí, và người chơi thứ hai cũng biết đều này, v.v), theo cân bằng Bayes hoàn hảo, các diễn tiến trong trò chơi sẽ xảy ra như sau:

Người chơi thứ hai không thể quan sát hành vi của người chơi thứ nhất. Người chơi thứ nhất muốn lừa người chơi thứ hai tin rằng mình đã chọn ‘’U’’ trong khi thực tế anh ta chọn ‘’D’’, sao cho người chơi thứ hai sẽ chọn ‘’D’ ‘’ và người chơi thứ nhất sẽ nhận được khoản thu hoạch là 3. Thực tế sẽ có cân bằng Bayes hoàn hảo tại đó người chơi thứ nhất chọn ‘’D’’ và người chơi thứ hai chọn ‘’U’ ‘’ và người chơi thứ hai tin rằng người chơi thứ nhất chắc chắn sẽ chọn ‘’D’’ (ví dụ, người chơi thứ hai đặt xác suất bằng 1 tại điểm người chơi thứ nhất chọn ‘’D’’). Trong thế cân bằng này, mỗi chiến lược đều tuân theo lý trí, với điều kiện cho trước là các niềm tin của người chơi, và mỗi niềm tin đều thống nhất với các chiến lược được thực hiện. Trong trường hợp này, cân bằng Bayes hoàn hảo chính là cân bằng Nash duy nhất.

Tham khảo

^ Harsanyi, John C., 1967/1968. "Games with Incomplete Information Played by Bayesian Players, I-III." Management Science 14 (3): 159-183 (Part I), 14 (5): 320-334 (Part II), 14 (7): 486-502 (Part III).

[1] Harsanyi, John C., 1967/1968. "Games with Incomplete Information Played by Bayesian Players, I-III." Management Science 14 (3): 159-183 (Part I), 14 (5): 320-334 (Part II), 14 (7): 486-502 (Part III).

[1]