Song đề tù nhân

Bách khoa toàn thư mở Wikipedia

Song đề tù nhân (Prisoner's Dilemma) là một trò chơi có tổng không bằng không (non-zero sum) trong lý thuyết trò chơi (game theory). Hình thể đơn giản nhất của trò chơi có hai người chơi (gọi là tù nhân), mỗi người đều muốn giành thuận lợi cho mình, bất chấp tình trạng của người kia. Kết quả của trò chơi này không tối ưu. Nếu hai người đều hợp tác với nhau thì kết quả sẽ tốt nhất, nhưng mỗi người đều có động cơ để đào ngũ. Vì thế trò này mới được gọi là song đề.

Một thể khác của trò chơi này, được gọi là Song đề tù nhân lặp lại (Iterated Prisoner's Dilemma), cho phép những người chơi lặp lại nhiều trận. Như thế, mỗi người chơi có cơ hội "trừng phạt" người kia nếu họ không hợp tác trong các trận trước. Kết quả của trò này là cả hai đều hợp tác vì động cơ để ăn gian bị mối đe dọa trừng phạt khống chế.

[sửa] Song đề 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 loã 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.

[sửa] 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

[sửa] Thí dụ trong thực tế

Trò chơi này nhìn vào thấy có lẽ khó có thật trong thực tế, nhưng thật sự có nhiều trường hợp trong giao thiệp giữa người với người hay với thiên nhiên có ma trận thưởng phạt tương đương. Vì thế, 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ội 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 hoá.

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ý.

William Poundstone, trong một quyển sách về song đề tù nhân (xem tham khảo), đả miêu tả một tình cảnh ở New Zealand nơi các hộp báo không được khoá. Một người có thể lấy báo mà không cần trả tiền (đào ngũ) nhưng rất ít người làm việc đó vì họ thấy rằng nếu mọi người đều "chôm" báo (cả hai đào ngũ).

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").

[sửa] 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.

[sửa] 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 hoá: 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 miếng trả miếng (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.

[sửa] 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ũ.

Một ma trận thưởng phạt sẽ giống như sau:

Nếu cả hai hợp tác, mỗi người được +5.
Nếu một người hợp tác và một người đào ngũ, người thứ nhất được +1 còn người kia được +10.
Nếu cả hai đều đào ngũ, mỗi người bị -20.

[sửa] Trò chơi cam đoan (Assurance)

[sửa] Tham khảo

Axelrod, Robert and Hamilton, William D. (1981). "The Evolution of Cooperation". Science, 211:1390–1396.
Axelrod, Robert (1984). The Evolution of Cooperation.
Axelrod, Robert (1997). The Complexity of Cooperation. Princeton University Press. ISBN 0691015678.
Grofman and Pool (1975). "Bayesian Models for Iterated Prisoner's Dilemma Games". General Systems 20:185–94.
Hofstadter, Douglas R. (1985) The Prisoner's Dilemma Computer Tournaments and the Evolution of Cooperation Ch.29 from Metamagical Themas: questing for the essence of mind and pattern. ISBN 0465045669.
Poundstone, William (1992). Prisoner's Dilemma: John von Neumann, Game Theory, and the Puzzle of the Bomb. Doubleday. ISBN 0385415672. A wide-ranging popular introduction, as the title indicates.
Rapoport, Anatol and Chammah, Albert M. (1965). Prisoner's Dilemma. University of Michigan Press. An account of many experiments in which the psychological game Prisoner's Dilemma was played.
Verhoeff, Tom (1998). "The Trader's Dilemma: A Continuous Version of the Prisoner's Dilemma". Computing Science Notes 93/02, Faculty of Mathematics and Computing Science, Technische Universiteit Eindhoven, The Netherlands.
New Tack Wins Prisoner's Dilemma (from Wired.com)