Avatar's shochu

Ghi chép của shochu

Prisoner's Dilemma.

Tạm dịch: Song đề tù nhân.

Mở ngoặc là với các bạn học chuyên ngành có dính tới kinh tế, chính trị, tâm lý...thì cái này chắc là được học từ buổi đầu vào trường, nhưng với mình thì...mới toanh, kiểu như lần đầu được lên Phănxipăng ngắm mặt trời mọc í. Nên mình post lên để...tự răn :D. Đóng ngoặc.


Nguồn: Wikipedia.

Phiên bản cổ điển:

Song đề tù nhân cổ điển được kể như sau:

Hai kẻ bị tình nghi là tội phạm bị cảnh sát bắt. Cảnh sát không có đủ chứng cớ để kết án họ, và đã cách ly họ. Cảnh sát gặp từng người một và làm cùng thoả thuận:
  . Nếu một người thú tội mà người kia im lặng, người im lặng sẽ bị phạt 10 năm tù và người thú tội sẽ được thả tự do.
  . Nếu cả hai đều im lặng, cảnh sát chỉ phạt được mỗi tù nhân 6 tháng tù vì một tội nhỏ khác.
  . Nếu cả hai đều thú tội, mỗi người sẽ bị phạt 2 năm.

Trò chơi có thể được tóm tắt như sau:


Tù nhân A phủ nhận Tù nhân A thú tội
Tù nhân B phủ nhận Cả hai bị 6 tháng tù B bị 10 năm tù; A được thả tự do
Tù nhân B thú tội A bị 10 năm tù; B được thả tự do Cả hai bị 2 năm tù

Giả sử rằng cả hai tù nhân đều ích kỷ và đều muốn làm giảm tối thiểu thời gian tù tội của mình. Mỗi tù nhân có hai lựa chọn: hợp tác với kẻ đồng lõa và giữ im lặng, hay phản bội và thú tội. Kết quả của mỗi lựa chọn đều tuỳ thuộc vào lựa chọn của người kia. Tuy nhiên, không người nào biết được lựa chọn của người kia. Nếu họ có thể nói chuyện với nhau, họ cũng chưa chắc là tin tưởng nhau được.

Nếu người này tin rằng người kia sẽ giữ im lặng, lựa chọn tối ưu của hắn là thú tội, vì thế hắn sẽ được thả tự do ngay trong khi người kia sẽ bị nằm tù 10 năm. Ngược lại, nếu hắn tin rằng người kia sẽ thú tội, lựa chọn tối ưu cũng là thú tội, vì nếu thú tội thì hắn sẽ bị tù chỉ 2 năm thay vì 10 năm nếu giữ im lặng. Tuy nhiên, nếu cả hai hợp tác với nhau và giữ im lặng, cả hai sẽ được thả tự do trong vòng 6 tháng.

Vì thế ta thấy mỗi người đều nên thú tội. Bất kể lựa chọn của người kia, mỗi tù nhân đều được giảm thời gian tù nếu thú tội. Xui thay cho cả hai, vì kết quả là cả hai đều thú tội và cả hai đều bị tù lâu hơn là cùng giữ im lặng.

Nếu lý luận từ quan điểm tốt cho cả hai người, kết quả tốt nhất sẽ là hai người đều hợp tác với nhau, vì như thế thời gian ở tù tổng cộng của cả hai người chỉ là một năm. Bất cứ lựa chọn nào khác sẽ dẫn đến thời gian tù tội của hai người dài hơn. Vì mỗi người đều đi theo quyền lợi ích kỷ của mình, hai người bị lãnh án dài hơn.

Nếu mỗi người đều có cơ hội trừng phạt người kia khi họ thú tội, kết quả sẽ là sự hợp tác. Hình thể lặp lại của trò chơi này cho phép sự trừng phạt đó. Trong trò chơi đó, nếu một người gian lận người kia trong một lần nào, hắn có thể bị trừng phạt bằng cách người kia gian lận trong lần kế. Vì thế, trò chơi lặp lại tạo một cơ hội để mỗi người chơi trừng phạt người kia nếu hắn không hợp tác.


---> Ma trận thưởng phạt:

Ma trận thưởng phạt của song đề tù nhân có thể viết bằng nhiều cách, miễn là theo những nguyên lý sau đây: T > R > P > S

trong này, T là động cơ đào ngũ (temptation - khi đào ngũ và người kia hợp tác); R là phần thưởng khi cả hai đều hợp tác (reward); P là sự trừng phạt khi cả hai đều đào ngũ (punishment); và S là phần bị lãnh khi hợp tác và người kia đào ngũ (sucker's payoff).

(Các giá trị số phải được chọn để T + S < 2R để trò chơi được đáng kể).

Công thức trên bảo đảm rằng bất kỳ số nào được chọn, lựa chọn đào ngũ cũng lúc nào cũng tốt hơn bất chấp lựa chọn của người kia.

Theo nguyên lý này, chúng ta lấy được ma trận thưởng phạt chuẩn thường được nêu ra trong các bài viết về đề tài này. Trong cách trình bày này, số càng lớn thì kết quả càng tốt.

Ma trận thưởng phạt chuẩn

Hợp tác Đào ngũ
Hợp tác 3, 3 0, 5
Đào ngũ 5, 0 1, 1

Trong thuật ngữ "thắng-thắng" ma trận sẽ giống như sau:


Hợp tác Đào ngũ
Hợp tác thắng-thắng thua nhiều-thắng nhiều
Đào ngũ thắng nhiều-thua nhiều thua-thua


Thí dụ trong thực tế

Song đề tù nhân đáng được đề cập đến trong các môn khoa học xã hội như kinh tế học, chính trị và xã hộii học, cũng như trong các môn sinh học như phong tục học và sinh học tiến hóa.

Trong khoa học chính trị, hiện tượng song đề tù nhân thường được dùng để minh hoạ vấn đề hai quốc gia đang tham gia trong một cuộc đua vũ khí. Cả hai đều lý luận rằng họ có hai lựa chọn, một là tăng tiền quân sự hay hai là thoả thuận giảm vũ khí. Nhưng không nước nào có thể chắc chắn rằng nước kia sẽ tuân theo thoả thuận; vì thế, cả hai đều bỏ tiền ra để tăng số vũ khí. Tuy hai nước đều hành động theo suy luận có lý, nhưng kết quả lại vô lý.

Cuối cùng, kết quả lý thuyết của song đề là lý do tại một số quốc gia không cho phép giao kèo bào chữa. Nhiều khi trường hợp y như song đề cổ điển được áp dụng: thường cả hai đều có động cơ để nhận tội và khai chống người kia, mặc dù mỗi người đều vô tội. Kết quả xấu nhất phải nói là khi một người có tội và một người vô tội: người vô tội sẽ không nhận tội, trong khi người có tội lại nhận tội và vu khống người vô tội.

Nhiều hoàn cảnh song đề trong thực tế có nhiều người tham gia. Hoàn cảnh bi kịch bàn ăn chung(tragedy of the commons), tuy là ẩn dụ, có thể được xem là một hình thể nhiều người của song đề tù nhân: mỗi người trong làng đều có một lựa chọn để có lợi ích cá nhân hay tự kiềm chế. Kết quả khi nhiều người đào ngũ là một phần "thưởng" rất thấp (tượng trưng cho sự phá huỷ của "bàn ăn").


Những hình thể khác

Song đề tù nhân có nhiều hình thể khác, với nhiều cách chơi khác và ma trận thưởng phạt khác nhau.

Song đề tù nhân lặp lại

Trong quyển The Evolution of Cooperation (1984) (Quá trình tiến hoá của sự hợp tác), tác giả Robert Axelrod đã khảo sát một trường hợp mở rộng của song đề tù nhân mà ông gọi là song đề tù nhân lặp lại (iterated prisoner's dilemma - IPD). Trong trường hợp này, những người tham gia phải chọn một chiến thuật nhiều lần, và có thể nhớ được những lần trước. Ông đã mời nhiều nhà nghiên cứu từ khắp thế giới tạo ra những chiến thuật vi tính để đấu nhau trong một cuộc đấu IPD. Những chương trình được gửi về khác nhau rất nhiều về sự phức tạp của thuật toán, thái độ thù địch ban đầu, khả năng tha thứ, v.v.

Axelrod đã khám phá ra rằng khi các cuộc đấu này trải qua một thời gian dài với nhiều người chơi, mỗi người với một chiến thuật riêng, thì những chiến thuật "tham lam" thường có kết quả rất thấp khi so với những chiến thuật "vị tha" hơn. Ông đã dùng khám phá này để đưa ra một giải thích để bù một lỗ trong thuyết tiến hóa: trong chọn lọc tự nhiên chỉ có những động cơ ích kỷ, vậy sao lại tiến hoá đến những hành động vị tha?

Chiến thuật tốt nhất là ăn trả miếng thịt (tit for tat) do ông Anatol Rapoport phát triển. Chiến thuật này là chiến thuật đơn giản nhất, chỉ dùng bốn hàng  ngôn ngữ lập trình Basic, nhưng lại thắng cuộc. Chiến thuật này là hợp tác trong lần đầu, và sau đó chỉ làm theo đối thủ trong trận trước. Một chiến thuật tốt hơn một tí là "ăn miếng trả miếng với tha thứ". Khi đối thủ đào ngũ, trong trận kế tiếp đôi khi vẫn hợp tác với một cơ hội nhỏ (1-5%). Việc này cho phép phục hồi nếu cả hai cứ đào ngũ. "Ăn miếng trả miếng với tha thứ" hoạt động tốt nhất khi trong trò chơi có thể bị mất liên lạc. Việc này có nghĩa là đôi khi đối thủ được thông báo sai về lựa chọn của mình: mình hợp tác nhưng đối thủ lại tưởng là mình đã đào ngũ.

Axelrod kết luận rằng "ăn miếng trả miếng" thành công vì hai lý do. Thứ nhất, nó "tử tế" (nice): nó hợp tác lúc đầu và chỉ đào ngũ để trả đũa khi đối thủ đào ngũ trước, cho nên nó không bao giờ bắt đầu một vòng tròn đào ngũ. Thứ nhì, nó có thể linh động, lúc nào cũng có thể phản ứng việc đào ngũ của đối thủ; nó trừng phạt người kia ngay sau khi họ đào ngũ, nhưng lập tức đối xử tử tế ngay khi họ bắt đầu hợp tác.

Nếu một IPD được lặp lại đúng N lần, và N được biết trước, thì một kết luận thú vị sẽ xảy ra. Trong trường hợp này thì chiến thuật hay nhất cũng sẽ là đào ngũ cho mỗi lần. Điều này có thể chứng minh được theo phương pháp quy nạp. Trong trận cuối, vì đối thủ không có cơ hội trừng trị mình được, lựa chọn tốt nhất sẽ là đào ngũ. Như thế, cả hai sẽ đào ngũ trong trận cuối. Nhưng theo lý đó thì mình cũng nên đào ngũ trong trần trước trận cuối, vì đối thủ sẽ đào ngũ trong trận cuối bất chấp mình làm gì. Và cứ suy luận như thế. Vì thế, nếu muốn cả hai đều hợp tác, cả hai đều không được biết khi nào trò chơi kết cuộc. Một giải pháp là làm số N một số ngẫu nhiên.

Trò chơi thách (Chicken)

Có một loại trò chơi có tổng không bằng không nữa là trò chơi thách (Chicken) được đặt tên theo một trò chơi đua xe. Hai chiếc xe chạy tiến gần đến nhau và đang đà đụng nhau - người đầu tiên đổi hướng xe để khỏi bị tung bị xem là kẻ nhát gan ("chicken"). Cả hai người có thể đổi hướng để tránh tai nạn (hợp tác) hay cứ tiến thẳng (đào ngũ). Trong trò chơi này, nếu đối thủ hợp tác thì ta nên đào ngũ - đây là kết quả tốt nhất. Nếu đối thủ đào ngũ, ta lại nên hợp tác. Trường hợp cả hai đều đào ngũ là trường hợp xấu nhất, nhưng trong song đề tù nhân kết quả xấu nhất là khi mình hợp tác trong khi người kia đào ngũ.







3574 ngày trước · Bình luận · Loan tin ·  
được loan tin bởi Snowflake , Krad
Krad
Đau đầu quá @@
9 năm trước· Trả lời
shochu
@Krad: hôm nào sáng tinh mơ, khỏe khoắn yêu đời thì đọc ih em, hic hà. Ráng đi em, hay lúm ó T_T
9 năm trước· Trả lời
VuonChuoi
Đã đc biết qua trong truyện Liar Game phần kết.
Trò chơi táo địa đàng
Có 3 loại quả táo: táo vàng táo bạc và táo đỏ chân thật
11 người chơi, đc phép chọn 1 trong 3 loại
Trường hợp ko ai chọn táo đỏ : 11 người chơi sẽ chọn 2 loại táo vàng và táo bạc,
9 năm trước· Trả lời
Snowflake
Saved!
9 năm trước· Trả lời
WhY_L0vE
thích mấy cái như thế này :x
9 năm trước· Trả lời
Website liên kết