Game theory và một số mô hình ứng dụng
Nếu không tiện đọc bài viết, bạn có thể nghe bản audio tại đây: John Nash bắt đầu bằng PhD tại Đại học...
Nếu không tiện đọc bài viết, bạn có thể nghe bản audio tại đây:

John Nash bắt đầu bằng PhD tại Đại học Princeton năm 1948 với một bức thư giới thiệu nói rằng "Đây là một thiên tài toán học". Thật sự vậy, 19 tuổi, dự duy nhất một lớp Kinh tế trong chương trình học Đại học của mình, Nash cho ra đời công trình toán học đầu tiên chỉ sau 14 tháng nghiên cứu, để sau này, năm 1994, ông nhận giải Nobel cho những đóng góp to lớn của mình trong Kinh tế và cụ thể là trong Lý thuyết Trò chơi.
(Lưu ý: những tiêu đề dưới đây hoàn toàn không phản ánh nội dung, được đặt ra theo cảm xúc của người viết và mang mục đích đánh dấu từng phần và giải trí là chính)
1. Trò chơi...trời cho
Ngày 16/11/1949, Nash gửi một bản note chỉ dài hơn 1 trang lên Proceedings of the National Academy of Sciences, trong đó ông có giới thiệu về một khái niệm mới trong Lý thuyết Trò chơi, mà sau này nó được biết đến với tên gọi "Cân Bằng Nash".
Khái niệm này về cơ bản mô tả chiến thuật của một trò chơi cá nhân, chơi bởi những gã khôn ngoan luôn biết tìm cách tốt nhất để tối đa hóa lợi nhuận của mình
(making rational choices) dựa trên việc dự đoán về chiến thuật của các đối thủ. Sau đó trò chơi được mô tả là sẽ đạt cân bằng Nash khi tất cả người chơi đã chọn được một chiến thuật tối ưu nhất của mình.

Còn sau đó là phần toán học, Nash chứng minh rằng trong một trò chơi có hữu hạn người chơi và hữu hạn lựa chọn, thì luôn luôn tồn tại ít nhất một cân bằng Nash.
Nghe có vẻ vẫn chung chung quá...Okay, chúng ta sẽ xét một ví dụ cực kì cổ điển của cân bằng Nash: Prisoner's Dilemma ...nghe gk^e thế nhỉ, thôi gọi là Song đề tù nhân nhé...
2. Khi hai cầu thủ Juventus không tin tưởng nhau
Song đề tù nhân đưa ra một tình huống khá là "khoai" (hay còn gọi một cách có học hơn là "tiến thoái lưỡng nan") của hai người tù nhân.
Câu chuyện là thế này: Hai anh chàng xấu số, Khá Bảnh và Khá Đuối, về cơ bản là có tội rồi, nhưng công an thì cần hai anh hợp tác cho lời khai để còn nhanh nhanh kết thúc vụ án. Họ đưa hai anh vào hai phòng tách biệt, chủ yếu là để ngăn mọi sự liên lạc giữa hai người, rồi đưa cho họ 1 offer cực "thơm" như sau.
Nếu anh Bảnh khai mà anh Đuối không khai, thì anh Bảnh được hưởng khoan hồng, thả tự do, trong khi anh Đuối thì bị tù chung thân. Và ngược lại. Còn nếu cả hai anh cùng khai, thì cùng đi tù 2 năm. Còn nếu cùng im lặng, well, công an vẫn sẽ tống cả hai anh vào tù, nhưng 6 tháng thôi.

Dưới góc nhìn của người thứ ba, bạn nghĩ lựa chọn nào sẽ tốt nhất cho cả hai?
Sau đó, chúng ta xét tình huống dưới góc nhìn của từng người tham gia nhé!
Anh Bảnh và anh Đuối về cơ bản thì cũng chả tin tưởng gì nhau lắm, xong lại còn bị cắt đứt liên lạc, nên tình huống bây giờ đưa về trò chơi cá nhân - giống như trong mô tả về cân bằng Nash, với hai người chơi (có thể giả sử là) khôn ngoan là Bảnh và Đuối.
Đặt mình vào vị trí của anh Bảnh, chúng ta thấy có 2 trường hợp, phụ thuộc vào lựa chọn của Đuối : nếu Đuối khai, Bảnh cũng sẽ phải khai (đi tù 2 năm) thay vì im lặng (đi tù chung thân); nếu Đuối im lặng, Bảnh cũng sẽ vẫn khai (được thả tự do) thay vì im lặng (đi tù 6 tháng). Như vậy thì kiểu gì đi nữa, Bảnh cũng sẽ khai.
Đặt vào vị trí của Đuối, tương tự, Đuối cũng sẽ khai.
Cuối cùng, cả hai người đều khai. Ở đây, ta đã đạt được 1 cân bằng Nash, là 1 vector lựa chọn của 2 người (khai, khai) - tức là cả 2 đi tù 2 năm.
Quay lại trò chơi với góc nhìn của một người thứ ba, rõ ràng, việc cả hai người đều im lặng thì sẽ là lựa chọn tốt nhất - tức là cả 2 chỉ đi tù 6 tháng??? Vậy thì tại sao người chơi lại không làm vậy???
Cũng dễ hiểu nè, chủ yếu là vì họ không tin tưởng nhau, và chỉ cố gắng tối đa hóa lợi ích của riêng mình thôi. Và vì vậy, người ta nói, cân bằng Nash chỉ ra rằng: tối đa hóa lợi ích cho từng cá nhân chưa chắc đã là cách tối ưu hóa lợi ích cho một đám đông.
Self-improving individuals could lead to self-harming crowds
Và sau đây, là một số ứng dụng cổ điển của cân bằng Nash (không chỉ ở trong kinh tế).
3. Hai cô gái bán hoa trên cùng 1 con đường
Okay, chúng ta sẽ đến với mô hình đầu tiên: Hotelling.
Bài toán đưa ra như sau: 2 cửa hàng bán kem dự định mở cửa hàng trên 1 con phố đi bộ, ở đó ta giả sử người mua hàng được phân phối đều trên con đường, và ai cũng phải mua 1 và chỉ 1 cây kem. Cả hai cửa hàng cùng bán một loại sản phẩm, y xì nhau từ chất lượng đến giá cả. Thứ mà họ cạnh tranh nhau hiện tại là lượng người mua. Biết rằng, người mua luôn chọn cửa hàng kem gần mình nhất, và nếu 2 cửa hàng cùng đặt trên cùng 1 vị trí (đối diện nhau chẳng hạn), thì thị phần sẽ được chia đôi cho cả hai. Câu hỏi đặt ra là, chiến thuật chọn vị trí của 2 cửa hàng như thế nào để tối đa hóa lượng người mua?



Nhìn vào hình minh họa, ta có thể thấy, cả hai cửa hàng kem luôn có xu hướng tiến gần đến giữa con phố, để tối đa hóa thị phần của mình. Và khi cả hai đã ở chính giữa con phố, chẳng ai muốn chuyển đi nữa cả. Ở đây, ta đạt được 1 cân bằng Nash, và thị phần của mỗi cửa hàng là 50%.
Đứng ở góc nhìn ở người thứ ba, ta đều thấy rằng việc hai cửa hàng nằm cách đều nhau ở 2 bên phố (hình ở giữa, bên trái) là đủ để đem lại thị phần cho họ là 50% - tức là tương đương với cân bằng Nash. Chưa kể, ở vị trí này, người mua chỉ cần đi xa nhất là 1/4 con phố để đến được hàng kem. Trong khi, ở cân bằng Nash, người ở đầu phố phải đi đến 1/2 con phố để mua kem.
Kết luận : Trong cân bằng Nash này, lợi nhuận là tối đa cho cả hai người bán, nhưng lại chưa phải là cân bằng tối ưu cho thị trường chung.
4. Xây đường suốt mà đường tắc thì vẫn cứ tắc?
Tiếp theo, ta phân tích một vấn đề thú vị trong quy hoạch giao thông: nghịch lý Braess.
Bài toán được đưa ra dưới dạng giản lược như sau :
Một hệ thống đường, ban đầu chỉ có 2 con đường : Start - A - End và Start - B - End. Trong đó, Start - B và A - End là hai con đường cao tốc có thể chịu được lượng lưu thông khổng lồ, nên thời gian di chuyển trên 2 con đường này là hằng số, 45 phút. Tuy nhiên, 2 cây cầu, Start - A và B - End là nút cổ chai của 2 tuyến đường này, chỉ chịu được lượng lưu thông giới hạn, nên thời gian di chuyển sẽ tỉ lệ thuận với lượng lưu thông : t = T/100, T là lượng phương tiện di chuyển. Tổng lượng xe muốn di chuyển từ Start đến End là 4000.

Bài toán ban đầu khá đơn giản. Dễ dàng thấy, lượng xe cộ lưu thông sẽ chia làm đôi, lưu thông trên 2 con đường khác nhau là Start - A - End và Start - B - End. Sẽ không có kẻ khôn ngoan nào đổi ý định, chọn con đường còn lại vì điều đó sẽ kéo theo tăng lượng lưu thông trên cầu, làm chậm thời gian di chuyển đi. Ta có cân bằng Nash. Với thời gian lưu thông của mỗi người là : 2000/100 + 45 = 65 phút.
Bây giờ, người ta muốn cải thiện việc di chuyển trên mạng lưới giao thông này, nên thành phố đã xây dựng thêm một con đường "siêu tốc" A - B. Với công nghệ xây đường vượt trội (có thể là 1 dạng của Teleport), người ta di chuyển từ A đến B mà không tốn chút thời gian nào, và không phụ thuộc vào lưu lượng xe cộ luôn !!!

Một kẻ ranh ma đang đi trên cây cầu Start - A nghĩ rằng, nếu hắn đi theo con đường Start - A - B - End thì sẽ chỉ mất : 2000/100 + 0 + 2001/100 = 40.01 phút !!! Tiết kiệm được hẳn 25 phút. Nghĩ sao, hắn làm vậy. Rồi không chỉ mình hắn, những người khác đang đi trên cây cầu Start - A cũng làm vậy. Rồi tất cả mọi người đều bỏ con đường A - End mà đi theo lộ trình A - B - End vì : 2000/100 + 0 + 4000/100 = 60, vẫn nhanh hơn là 65 phút !!! Lúc này, người đi theo lộ trình Start - B - End thì tự nhiên bị kéo chậm lại bởi : 45 + 4000/100 = 85 phút !!! Điên tiết, họ lại đồng loạt bỏ con đường Start - B rồi lại đi theo lộ trình Start - A - B - End, bởi vì : 4000/100 + 0 + 4000/100 = 80 phút, vẫn nhanh nhiều so với 85 phút đi theo con đường Start - B - End. Và cuối cùng, tất cả đều đi theo lộ trình Start - A - B - End dù thời gian di chuyển lên tới 80 phút :) Tuy vậy, cũng chẳng ai muốn chọn đi qua Start - B hay A - End, vì đi trên cầu tuy hơi đông nhưng cũng chỉ mất 40 phút, còn đi trên đường cao tốc thì mất những 45 phút cơ :) Ở đây, ta đạt cân bằng Nash, với thời gian di chuyển là 80 phút (?)
Kết luận: Dễ nhận thấy, kể cả khi xây thêm đường A-B, việc mọi người đồng loạt nhất trí không đi trên con đường này thì bài toán quay trở lại ban đầu, và thời gian di chuyển tối ưu chỉ là 65 phút mà thôi. Nhưng vì mọi người đều cố gắng tối ưu hóa việc di chuyển của riêng mình, nên đã kéo dài thời gian lên thành 80 phút, và 2 con đường cao tốc thì bị bỏ không. Một lần nữa, cân bằng Nash cho thấy, đám đông không phải lúc nào cũng khôn ngoan. Và quan trọng hơn, nghịch lý về việc, không phải cứ xây thêm đường thì sẽ giải tỏa được ách tắc giao thông.
Bài toán này còn nhấn mạnh sự cần thiết của việc áp dụng toán học một cách đúng đắn vào quy hoạch đô thị.
5. Nguồn tham khảo
Braess's Paradox: Wikipedia, VCP/Havard

Khoa học - Công nghệ
/khoa-hoc-cong-nghe
Bài viết nổi bật khác
- Hot nhất
- Mới nhất

deathstar
Điều thú vị ở lý thuyết trò chơi với một người cộng sản như mình là nó giải thích tại sao chế độ cộng sản lại tốt nhưng khó mà thành công. Bởi vì nếu mọi người hoàn toàn hợp tác với nhau thì đạt được lợi ích tối đa, nhưng nhìn từ phía mỗi cá nhân, lựa chọn ích kỷ mới là tốt nhất. Thế nên trước khi mọi người có thể trao đổi thông tin tức thời và có cơ chế giúp hoàn toàn tin tưởng lẫn nhau thì xã hội cộng sản không thể khả thi.
- Báo cáo

Hùng Vũ
thật sự là chỉ có hive mind như đàn kiến mới khiến cho hình thái xã hội cộng sản được thành công
- Báo cáo

Thịnh Ngô
Cảm ơn bạn đã quan tâm tới bài viết. Lúc nói về thuyết trò chơi, người ta cũng hay liên hệ vấn đề đến sự hiệu quả của nền dân chủ/cộng sản. Cá nhân mình thì nghĩ các vấn đề chính trị thường vĩ mô hơn rất nhiều, nó không chỉ nói về lợi ích và kinh tế. Và con người không phải lúc nào cũng khôn ngoan (making rational choices). Thực tế một thí nghiệm về song đề tù nhân đã được đưa ra, và chỉ có 50% cặp người tham gia là chọn phương án giống với cân bằng Nash thôi. Nói gì đi nữa, những lý thuyết này cũng chỉ thể hiện một phần góc nhìn của cuộc sống, Dùng nó để đánh giá 1 hệ thống chính trị thì có phần hơi bất công và phiến diện. Mình không nói ý kiến của bạn sai. Nhưng vấn đề này quá vĩ mô để có thể mang ra bàn luận qua bài viết này. Cảm ơn bạn.
- Báo cáo

deathstar
Vì con người không khôn ngoan nên mới mâu thuẫn đó bạn, nếu ai cũng khôn ngoan và biết hợp tác thì luôn cho kết quả tối ưu còn gì, vấn đề của chúng ta chính là thực tế chênh lệch với lý thuyết bàn giấy đó. Mà đây cũng chỉ là một trong những lý do thôi, không phải là một đánh giá toàn diện.
- Báo cáo

MạnhAS
Vấn đề là 2 bạn Bảnh và Đuối không tin tưởng lẫn nhau thôi nên việc tối đa hóa lợi ích xảy ra mới như vậy
- Báo cáo

Psycho
Thật ra mấu chốt của CNSC là tiền cơ (thực ra là của cải vật chất). Khi con người có nhiều của cải vật chất tới mức độ nào đó tự khác ngta sẽ tin tưởng lẫn nhau. Cũng giống như 2 cầu thủ Juve vậy, đây là đi tù 10 năm trong khi tuổi thọ chỉ trên dưới 100 năm nên mới thấy tiếc, chứ nếu tuổi thọ là 1 tỉ năm thì nó lại đã rất khác
- Báo cáo

w.d'z
Ví dụ như ở song đề tù nhân, lý thuyết này bỏ qua một yếu tố là trên thực tế, nếu bán đứng bạn tù thì còn có đồng bọn ở ngoài đánh hội đồng hoặc tẩy chay để trả thù cho người trong tù.
Về chủ nghĩa cộng sản, mình từng nghe kể một trường hợp về chế độ khẩu phần ăn tập thể thời bao cấp. Trong một nồi cơm chung, theo lý thuyết thì có vẻ như mỗi người sẽ cố dành lấy phần ăn cho mình nhiều nhất có thể, nhưng mình được kể là lúc đó, nếu ai dám múc cơm hơi nhỉnh hơn người khác, ngay lập tức sẽ có người ấy sẽ bị giật bát cơm rồi bị úp bát cơm thẳng lên đầu để cảnh cáo. Như thế, mọi người đều ăn khẩu phần bằng nhau, cơ thể cũng thích ứng, dần dần thì dù cho ở đó toàn thanh niên trẻ nhưng chẳng ai có thể ăn nổi quá một bát cơm, nên cũng chẳng ai muốn giành phần cơm nhiều hơn để làm gì. Điều kiện ở đây là mọi người quen biết, gắn bó với nhau trong suốt thời gian dài.
Đây là ví dụ về một trường hợp của cải được chia đều theo kiểu cộng sản, không bàn về việc nó tốt hay xấu nhé.
- Báo cáo

Psycho
Thật ra cái cách mà ngta hiểu về CS hầu hết đều méo mó vì hầu như chẳng có quốc gia nào trên thế giới tiến gần đến tích góp lượng đủ để biến đổi chất (tư bản -> cộng sản). Nhưng lại vẫn có vài nước CS nên họ phải thay đổi mỗi thứ 1 ít để gọi là chống chế. CS thực tế không phải là chia đều, CS là quá nhiều của cái đến mức ngta chẳng thèm chia (Làm theo năng lực, hưởng theo nhu cầu mà nhu cầu mỗi người đâu có giống nhau nên đâu thể chia đều). Thực tế, những quốc gia tiến đến gần CNCS hơn lại là những quốc gia tư bản vì họ có nhiều của cải để chia hơn.
- Báo cáo
Ha Van Diep
Mình cũng như bạn, khi tiếp xúc với cái lý thuyết trò chơi liền nghĩ ngay đây có thể là một lý do giải thích cho bản chất tư bản/cộng sản. Tuy nhiên đây cũng chỉ là 1 khía cạnh chứ ko phải là tất cả, tuyệt đối nó lại thành siêu hình mất.
- Báo cáo

nghelak
1. Bảng minh hoạ ở ví dụ song đề tù nhân có vấn đề ở ô cả A và B cùng đổ tội. Phải là 10 năm chứ không phải 2 năm.
2. Đoạn văn trước phần kết luận bạn ghi là "chẳng ai muốn chọn đi qua Start - A và B-End" thì cũng bị lẫn lộn, phải là Start-B và A-End.
Bài viết của bạn đề cập về một chủ đề khó hiểu nên việc lầm lẫn những thông tin quan trọng sẽ khiến người đọc khó tiếp thu. Mong bạn lần sau đọc kỹ bài viết trước khi post.
- Báo cáo

Thịnh Ngô
Cảm ơn bạn đã đọc bài và góp ý. Mình đã sửa lại rồi ^^
- Báo cáo
An_aver@ge_reader
cám ơn bạn, bài viết rất dễ hiểu
- Báo cáo

Thịnh Ngô
mình dự định bài kế tiếp sẽ tiếp tục về game theory. Nhưng có thể sẽ hướng đến mảng tin học hơn 1 chút. Mong bạn ủng hộ ^^
- Báo cáo
Will.i.Am
hóng :v
- Báo cáo

Hồ Ngọc Hoàng Minh
hóng quá hóng quá
- Báo cáo

Spiderum Production

Bài viết "Game theory và một số mô hình ứng dụng" của bạn Duy Nguyen đã được lựa chọn để chuyển thể sang dạng video trên kênh Youtube của Spiderum. Mời mọi người cùng đón xem nhé
https://youtu.be/HxAafpzmQXw

- Báo cáo

Leonardo
ung ho tac gia ra them bai ve Game theory !!
- Báo cáo