Trò chơi 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 đai 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ụ

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.