Game theory - Prisoner's Dilemma - Win win game

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.

John Nash và lý thuyết cân bằng Wednesday, 31 January 2007 22:08
[FONT=verdana,geneva]John Forbes Nash Jr., sinh ngày 13 tháng 6 năm 1928, là một nhà toán học nghiên cứu về lý thuyết trò chơi và hình học vi phân. Ở tuổi 30, khi đang cống hiến hết mình cho toán học, Nash mắc chứng tâm thần phân liệt kéo dài 25 năm. Năm 1994, nhờ những đóng góp của "cân bằng Nash" trong kinh tế, ông được trao giải Nobel Kinh tế.[/FONT]
[FONT=verdana,geneva]Cân bằng Nash là một khái niệm trong Lý thuyết Trò chơi (Game Theory), được tiến sỹ John Nash đưa ra trong luận án năm 1950 tại Priceton với mô hình trò chơi với n đối thủ. Cân bằng Nash [1] xác định một chiến lược tối ưu cho các trò chơi khi chưa có điều kiện tối ưu nào được xác định trước đó. Định nghĩa cơ bản của cân bằng Nash là: Nếu tồn tại một tập hợp các chiến lược cho một trò chơi với đặc tính là không một đối thủ nào có thể hưởng lợi bằng cách thay đổi chiến lược hiện tại của mình khi các đối thủ khác không thay đổi, tập hợp các chiến lược đó và phần thu nhận tương ứng tạo nên cân bằng Nash. Nói cách khác, cân bằng Nash đạt được nếu như thay đổi một cách đơn phương của bất cứ ai trong số các đối thủ cũng sẽ làm cho chính người đó thu lợi ít hơn mức có được với chiến lược hiện tại. Khái niệm này áp dụng cho những trò chơi gồm từ hai đối thủ trở lên và Nash đã chi ra rằng tất cả các khái niệm khác nhau về giải pháp (solution) trong các trò chơi được đưa ra trước đó đều có cân bằng Nash.[/FONT]

[FONT=verdana,geneva]Một ví dụ đơn giản [2]: trong một trò chơi gồm hai đối thủ cùng chọn song song một số bất kỳ từ 0 đến 10. Người nào chọn số lớn hơn sẽ thua và phải trả tiền cho người kia. Trò chơi này chỉ có 1 cân bằng Nash duy nhất: cả hai đối thủ đều chọn số 0. Bất kỳ sự lựa chọn nào khác (mà không biết sự lựa chọn của đối thủ kia) cũng có thể làm đối thủ thua cuộc. Khi thay đổi luật chơi: mỗi đấu thủ sẽ được hưởng số tiền bằng con số mà cả hai cùng chọn, nếu không chọn trùng nhau thì không ai có tiền, ta sẽ có 11 cân bằng Nash.[/FONT]

[FONT=verdana,geneva]Một trò chơi có thể có nhiều hoặc không có cân bằng Nash. Nash cũng chứng minh rằng nếu cho phép các chiến lược hỗn hợp (mixed strategies) tức là các đối thủ chọn ngẫu nhiên các chiến lược dựa vào khả năng đã được ấn định trước, thì bất cứ một trò chơi với n đối thủ nào trong đó mỗi đối thủ có thể chọn trong giới hạn cho trước nhiều chiến lược sẽ có ít nhất 1 cân bằng Nash của các chiến lược hỗn hợp.[/FONT]

[FONT=verdana,geneva]Ví dụ với Trò chơi Phối hợp (Coordination Game) [2]. Đây là trò chơi ma trận đôi cổ gồm 2 đối thủ A và B. A thường ở bên trái (tương ứng với số đầu tiên trong cặp số), B thường ở phía trên (tương ứng với số thứ hai trong cặp số). Trò chơi phối hợp trong việc lái xe. Có thể chọn lái bên trái hoặc bên phải với 1 tức là không gây tai nạn và 0 tức là gây tai nạn.[/FONT]

[FONT=verdana,geneva]B
Trái Phải
A Trái 1,1 0,0
Phải 0,0 1,1[/FONT]

[FONT=verdana,geneva]Trong trường hợp này, ta thấy có 2 cân bằng Nash khi cả 2 cùng chọn hoặc lái bên trái hoặc lãi bên phải.[/FONT]

[FONT=verdana,geneva]Ví dụ với Song đề Tù nhân (Prisoner’s dilemma) [2]. Song đề này minh hoạ sự mâu thuẫn giữa hành vi cá nhân có năng lực suy đoán và lợi ích của việc hợp tác. Vấn đề mấu chốt là mỗi đối thủ đều cố gắng tối đa hoá lợi ích của mình mà không quan tâm tới lợi ích của những người khác, tức là đối thủ có tính ích kỷ. Song đề tù nhân có 1 cân bằng Nash khi cả 2 đối thủ đều không tôn trọng giao ước. Tuy nhiên cả 2 đều sai rõ ràng không bằng cả hai cùng hợp tác. Chiến lược hợp tác không bền vì một đối thủ có thể làm tốt hơn bằng cách không tôn trọng giao ước trong khi đối thủ của anh ta vẫn hợp tác.[/FONT]

[FONT=verdana,geneva]Cân bằng Nash giúp làm rõ sự phân biệt giữa các trò chơi hợp tác và không hợp tác. Các trò chơi hợp tác có những thoả thuận có thể được áp đặt bời toà án chẳng hạn. Trong các trò chơi không hợp tác không tồn tại cơ chế thoả thuận như vậy. Và vì thế chỉ có các thoả thuận cân bằng được duy trì. Một hướng lý thuyết trò chơi mới được mở đường bằng cân bằng Nash xoá bỏ sự phân biệt này bằng cách xoá bỏ các cơ chế áp đặt có liên quan trong mô hình trò chơi, từ đó các trò chơi được mô hình hoá với tính chất không hợp tác.[/FONT]

[FONT=verdana,geneva]Lý thuyết kinh tế về đấu giá [3] cũng là một trong những áp dụng lớn của cân bằng Nash và lý thuyết trò chơi. Trước kia, các nhà kinh tế thường chỉ phân tích thị trường thông qua cung và cầu hàng hoá mà không chú trọng tới quy luật của “trò chơi” làm cho các hình thức đấu giá trở nên khác biệt với nhau và với các hình thức thị trường khác (thị trường chứng khoán, siêu thị…). Ngày nay nghiên cứu đấu giá thường dựa trên cân bằng Nash của các quy luật đấu giá.[/FONT]

[FONT=verdana,geneva]P. Ordeshook [4] Giáo sư chính trị học, Học viện công nghệ California, tác giả cuốn “Lý thuyết trò chơi và lý thuyết chính trị” đã viết: “Khái niệm cân bằng Nash có lẽ là ý tưởng quan trọng nhất trong lý thuyết trò chơi không hợp tác… dù trong việc phân tích chiến lược ứng viên / bầu cử, phân tích nguyên nhân chiến tranh, …, hay hành động của các nhóm quyền lợi, dự báo về các sự kiện đều thu lại trong việc tìm kiếm và mô tả các trạng thái cân bằng. Đơn giản hơn, các chiến lược cân bằng là những dự đoán về con người”.[/FONT]

[FONT=verdana,geneva]Trong thế kỷ 19, các nhà khoa học khác đã sử dụng lý thuyết cân bằng như Maxwell, Walrus, Gibbs. Đầu thế kỷ 20, cân bằng kinh tế và hoá học được sử dụng bởi van der Waals, Onnes, Keynes trước khi được Nash sử dụng. Nhiều nhà khoa học khác đã bổ sung cho lý thuyết của Nash trong thập kỷ 50 và 60 như Selten, Harsanyi, và tiếp túc khám phá các khả năng khác nhau của Lý thuyết cân bằng tổng thể (General Equilibrium Theory – GET) từ thập kỷ 70 tới thập kỷ 90, trong đó có Arrow, Hicks, và Debreu. Lý thuyết này vẫn được giảng dạy trong các trường đại học ngày nay.[/FONT]
[FONT=verdana,geneva]Cuộc đời của Nash đã được chuyển thể thành phim với tiêu đề “A Beautiful Mind”, dựa theo cuốn sách cùng tên của Sylvia Nasar và đã đoạt 4 giải Oscars 2002. [/FONT][FONT=verdana,geneva]Lý thuyết của Nash đã trở thành một hệ thống giải thích và chứng minh đa dạng hơn rất nhiều so với khái niệm ban đầu của tác giả. Hệ thống ấy đang ngày một phát triển trong xã hội, ở cả những nơi mà Nash có lẽ không bao giờ nghĩ đến.[/FONT]

Win Win.
Chẳng mấy ai có tư tưởng này.
Dù sao cũng ủng hộ chủ topic.

Lý thuyết này dành cho TT oligopoly, nchung là hay

Hay, thanks...

Bác nào biết sách dịch về đề tài này thì PM giới thiệu cho em với nhé... [r2)]

Chủ đề rất hay

Anh biết chú là ai rồi

Thằng kia đã khai với anh

Nào ta tiếp tục trò chơi[]

chủ thớt là dân kinh tế học chắc rồi...game theory là một lý thuyết quá hay.[r2)][r2)][r2)]