Lý giải một nền tảng của Lý thuyết trò chơi: Cân bằng Nash

Lý giải một nền tảng của Lý thuyết trò chơi: Cân bằng Nash

John Nash at OsloJohn F. Nash Jr. tại một buổi lễ vào tuần trước tại Oslo, Na Uy, nơi ông đã được trao giải thưởng Abel Prize. CreditBerit Roald/ NTB SCANPIX

John F. Nash Jr. nổi tiếng vì những tiến bộ trong lý thuyết trò chơi, vốn chủ yếu là việc nghiên cứu cách thức xây dựng một chiến lược thắng lợi trong trò chơi của cuộc sống — đặc biệt khi không biết được những gì đối thủ mình đang làm và những lựa chọn thì không phải lúc nào cũng đầy hứa hẹn.

Tiến sĩ Nash không phát minh ra lý thuyết trò chơi; nhà toán học John von Neumann là người tiên phong thiết lập lãnh vực này trong nửa đầu thế kỷ 20. Nhưng Tiến sĩ Nash đã mở rộng phân tích xa hơn, kiểu trò chơi tổng bằng không, “tôi thắng bạn thua” thành những tình huống phức tạp hơn, trong đó mọi người chơi đều có thể thắng, hoặc mọi người chơi đều có thể thua.

Khái niệm trung tâm là cân bằng Nash, được định nghĩa đại thể là một trạng thái ổn định, trong đó không có người chơi nào có thể đạt được lợi thế qua việc đơn phương thay đổi chiến lược, giả định rằng những người chơi khác không thay đổi những gì họ đang làm.

Bộ phim “A Beautiful Mind (Trí tuệ hoàn hảo)”, dựa trên cuộc đời của tiến sĩ Nash, nỗ lực giải thích lý thuyết trò chơi trong một màn mà Russell Crowe, đóng vai Tiến sĩ Nash, ở trong một quán bar với ba người bạn, và mọi người đều bị mê mẩn bởi một cô gái tóc vàng xinh đẹp, bước vào quán với bốn người bạn tóc nâu khác.

Cô gái tóc vàng bước vào quán bar. Bốn chàng trai nên làm gì? (A Beautiful Mind)

Trong khi bạn bè ông bông đùa về việc ai trong số họ sẽ tán tỉnh được cô gái tóc vàng, thì Tiến sĩ Nash lại kết luận rằng họ phải làm điều ngược lại: Hãy quên cô ta đi. “Nếu tất cả chúng ta đều quan tâm đến cô gái tóc vàng,” ông nói, “chúng ta sẽ cản trở lẫn nhau và không một ai trong chúng ta sẽ tán được cô ấy. Vì vậy, chúng ta sẽ chuyển qua tán tỉnh bạn bè của cô ấy, nhưng tất cả các cô ấy sẽ lạnh nhạt với chúng ta bởi vì không ai thích mình là sự lựa chọn thứ hai. Nhưng điều gì sẽ xảy ra nếu không ai quan tâm đến cô gái tóc vàng? Chúng ta không cản trở lẫn nhau và chúng ta cũng không xúc phạm các cô gái khác. Đó là cách duy nhất để giành chiến thắng“.

Trong khi một điều như trên không bao giờ xảy ra trong cuộc sống thực minh họa cho một số mưu đồ được các nhà lý thuyết trò chơi xem xét, thì trường hợp trên không phải là một ví dụ về cân bằng Nash.

Một ví dụ đơn giản hơn là cái được gọi là Thế lưỡng nan của tù nhân. Hai nghi phạm trong một vụ án phạm tội bị bắt giữ và được đề nghị một thỏa thuận: “Nếu bạn khai ra và làm chứng chống lại tòng phạm, thì chúng tôi sẽ thả bạn và quy tội cho bạn kia — 10 năm tù giam“.

Nếu cả hai đều giữ im lặng, thì các công tố viên không thể chứng minh được những cáo buộc nặng hơn và cả hai sẽ bị kết án một năm tù giam về một hành vi phạm tội không nghiêm trọng bằng. Nếu cả hai cùng khai, thì các công tố viên sẽ không cần đến bằng chứng của họ, và cả hai sẽ bị kết án tám năm tù giam.

Thoạt nhìn, giữ im lặng dường như là chiến lược tốt nhất. Nếu cả hai đều làm như vậy, thì cả hai sẽ có cơ hội được giảm tội khá nhẹ.

Nhưng tính toán của cân bằng Nash cho thấy cả hai có nhiều khả năng sẽ thú tội.

Kiểu vấn đề này được gọi là trò chơi bất hợp tác, có nghĩa là hai tù nhân không thể truyền đạt được ý định cho nhau. Khi không biết được những gì mà tù nhân khác làm, thì từng người phải đối mặt với lựa chọn sau: Nếu thú tội, thì có thể được tự do hoặc bị kết án tám năm tù giam. Nếu giữ im lặng, thì bị kết án một năm hoặc 10 năm tù giam.

Với suy nghĩ đó, thì thú tội là lựa chọn tốt hơn. Và nếu biết rằng tù nhân khác có cùng động lực để thú tội, thì lựa chọn giữ im lặng sẽ ít có khả năng xảy ra.

Ngoài ra, thay đổi chiến lược sang thành giữ im lặng sẽ là một một bước đi xấu — ở tù lâu hơn — trừ khi tù nhân khác bằng cách nào đó cũng làm điều tương tự. Nếu không truyền thông được với nhau, đó sẽ là một phỏng đoán mang tính rủi ro cao, và do đó, chiến lược này biểu trưng một cân bằng Nash.

Tuy nhiên, trường hợp ở quán bar thì không phải vậy. Với bốn người đàn ông theo đuổi bốn cô gái tóc nâu, thì thay vì làm vậy bất kì người đàn ông nào cũng có thể bị cám dỗ để theo đuổi cô gái tóc vàng, một kết quả đáng mong muốn hơn nếu bạn bè của người ấy cũng không thay đổi chiến lược.

KENNETH CHANG

Huỳnh Thiện Quốc Việt dịch

Nguồn: “Explaining a Cornerstone of Game Theory: John Nash’ Equilibrium”, New York Times, May 24, 2015


 John Nash (1928-2015), người Mĩ

John Nash at the Abel PrizeLà một thiên tài toán học, có lẽ Nash là nhà Nobel được công chúng biết đến nhất … nhờ bệnh tâm thần phân liệt mà ngay từ 1958 hầu như đã chấm dứt sự nghiệp của ông. Trước đó chỉ trong ba bài viết ngắn, ông đã đào sâu lí thuyết trò chơi, cả trò chơi chiến lược (hay không hợp tác tức là những trò chơi “được giả định là mỗi người tham gia ứng xử một cách độc lập, không có hợp tác hay trao đổi với bất kì đấu thủ nào khác” [1951] lẫn trò chơi hợp tác (“các cá nhân được giả định là có khả năng thảo luận với nhau về tình hình và đồng ý với nhau về một kế hoạch hành động chung và duy lí” [1953]).

Nash đã đề nghị khái niệm “điểm cân bằng” (ngày nay gọi là “cân bằng Nash”) cho các trò chơi không hợp tác: một tập lựa chọn, hay chiến lược, của các đấu thủ là một cân bằng nếu chiến lược được mỗi đấu thủ chọn là đáp trả tốt nhất cho các chiến lược của tất cả các đấu thủ khác [1951]. Lấy ví dụ (các ví dụ của Nash là khá phức tạp) của “cuộc chiến giữa hai giới”: Ông và Bà đều muốn trải qua buổi tối với nhau nhưng bà muốn đi xem một trận quyền Anh còn ông muốn xem một vở ba-lê. Do đó có trò chơi sau:

Ông

Quyền Anh

Ba-lê

Quyền Anh

Ba-lê

4,2

0,0

0,0

2,4

Cách đọc: nếu Bà (dòng) chọn quyền Anh và Ông (cột) cũng chọn quyền Anh thì Bà được 4 và Ông được 2; nếu Bà chọn quyền Anh và Ông chọn ba-lê cả hai đều 0.

(Quyền Anh, Quyền Anh) là một cân bằng Nash: biết rằng Bà sẽ chọn quyền Anh thì đáp trả tốt nhất của Ông là chấp nhận quyền Anh hơn là đi xem ba-lê một mình – và ngược lại. Nhưng (ba-lê, ba-lê) cũng là một cân bằng Nash … Chính vì thế mà Nash phân biệt “cân bằng” với “lời giải”, một khái niệm khắt khe hơn: nếu mọi trò chơi hữu hạn có ít nhất một cân bằng thì đó không phải trường hợp của các lời giải. Cân bằng này có thể cân bằng với chiến lược hỗn hợp, một pha trộn của nhiều chiến lược (thuần túy) được xác suất hóa: chẳng hạn, nếu Ông chơi (1/3, 2/3) thì đáp trả tốt nhất của Bà là (2/3, 1/3), và ngược lại – do đó đây là một cân bằng (nhưng có một xác suất không bằng không là cả hai đều đạt 0,0).

Đối với các trò chơi hợp tác, Nash đề nghị một loạt tiên đề phải chăng mà kết quả của cuộc thương thảo phải tuân thủ (kết quả này luôn tồn tại và là duy nhất) để được xem là một lời giải (đặc biệt là tính tối ưu Pareto hay sự bằng nhau giữa các đấu thủ đối xứng – nếu phải phân chia 1 thì kết quả sẽ là (1/2, 1/2)) và đề xuất một cách kiến giải hình học [1950]. Kết quả là điểm thực hiện được làm tích của thu hoạch từ cuộc thương thảo của hai đấu thủ là tối đa: phân chia sẽ có lợi cho đấu thủ nào tự xoay xở một mình tốt nhất vì người này có thể đe dọa không hợp tác.

Nash biện minh cho lời giải tiên đề hóa này bằng cách chứng minh rằng, nếu viết lại trò chơi hợp tác dưới dạng một trò chơi không hợp tác hai bước (các đấu thủ trước tiên chọn sự “đe dọa” của mình, nghĩa là sẽ làm gì nếu cuộc thương thảo thất bại, tiếp đó chọn mức thu hoạch tối thiểu họ đòi hỏi để cuộc thương thảo được xem là thành công), cân bằng Nash của trò chơi cuối này tương ứng với lời giải tiên đề hóa [1953].

Các công trình của Nash, một thời gian dài không được biết đến, được giải thưởng vài năm sau khi chúng được phát hiện lại trong kinh tế học, và khái niệm cân bằng Nash như là lời giải ngày nay cũng là một khái niệm chuẩn như khái niệm cân bằng cạnh tranh. Đặc biệt nó cho phép nghiên cứu những tình thế cạnh tranh không hoàn hảo.

Nguyễn Đôn Phước dịch

Nash [1951], “Non- cooperative Games”, Annals of Mahematics, vol.54, n.2

Nash [1953], “Two-Persons Cooperaive Games“, EMA, vol.21, n.1

Nguồn: Giải Nobel kinh tế của Jean-Édouard Colliard và Emmeline Travers, NXB Tri thức, Hà Nội, 2009, trang 125-127.

Advertisements

Trả lời

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Đăng xuất / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Đăng xuất / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Đăng xuất / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Đăng xuất / Thay đổi )

Connecting to %s