Luận văn thạc sĩ toán ứng dụng: Khám phá lý thuyết trò chơi

Luận văn thạc sĩ toán học nghiên cứu toán ứng dụng lý thuyết trò chơi và ứng dụng, khảo sát thực trạng, phân tích nguyên nhân, đề xuất giải pháp cải thiện thực tiễn.

• Tác giả: Nguyễn Thị Thanh Vui
• Người hướng dẫn: TS. Lê Xuân Đại
• Trường học: Đại học Bách Khoa - ĐHQG-HCM
• Chuyên ngành: Toán ứng dụng
• Đề tài: Lý Thuyết Trò Chơi Và Ứng Dụng
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2014
• Địa điểm: TP. Hồ Chí Minh

Tóm tắt

I. Lý thuyết trò chơi

Lý thuyết trò chơi (lý thuyết trò chơi) là một nhánh của toán ứng dụng và kinh tế học nhằm nghiên cứu các tình huống mà trong đó các bên tham gia (trò chơi) áp dụng những chiến lược ra quyết định để tối ưu hóa kết quả. Lý thuyết này đã được phát triển từ thời kỳ Thế chiến thứ hai và trở thành một công cụ quan trọng trong nhiều lĩnh vực. Việc áp dụng lý thuyết trò chơi giúp các nhà nghiên cứu và chuyên gia trong các lĩnh vực như kinh tế, chính trị, và quân sự đưa ra những quyết định chính xác hơn. Trong luận văn này, lý thuyết trò chơi được phân chia thành bốn loại cơ bản: trò chơi tĩnh với thông tin đầy đủ, trò chơi động với thông tin đầy đủ, trò chơi tĩnh với thông tin không đầy đủ, và trò chơi động với thông tin không đầy đủ. Các loại trò chơi này tương ứng với các khái niệm về điểm cân bằng, đặc biệt là cân bằng Nash, được phát triển bởi John Nash vào năm 1950.

1.1. Giới thiệu Lý thuyết trò chơi

Lý thuyết trò chơi bắt đầu hình thành từ những năm đầu của Thế chiến thứ hai, khi các lực lượng hải quân Anh áp dụng những khái niệm về lý thuyết trò chơi để cải thiện khả năng bắn trúng mục tiêu. Cuốn sách "Lý thuyết trò chơi và các hành vi kinh tế" của John Von Neumann và Oscar Morgenstern vào năm 1944 đã đánh dấu sự ra đời chính thức của lý thuyết này. Từ đó, lý thuyết trò chơi đã phát triển mạnh mẽ, với nhiều ứng dụng trong các lĩnh vực khác nhau như sinh học, triết học, và chính trị học. Định nghĩa về cân bằng Nash đã mở ra một hướng nghiên cứu mới, cho phép các nhà nghiên cứu xem xét sự tương tác giữa các bên trong trò chơi một cách sâu sắc hơn. Những thành tựu này đã được công nhận qua giải Nobel về kinh tế cho các nhà lý thuyết trò chơi vào năm 1994.

1.2. Biểu diễn trò chơi

Trò chơi có thể được biểu diễn dưới dạng chuẩn tắc và dạng mở rộng. Trong dạng chuẩn tắc, trò chơi được mô tả bằng ba thành phần: tập hợp người chơi, các chiến lược có thể thực hiện, và mức thưởng phạt nhận được cho mỗi sự kết hợp của các chiến lược. Ví dụ, trong một trò chơi hai người, mỗi người có thể chọn một trong hai chiến lược, và mức thưởng phạt sẽ được ghi rõ trong một bảng. Dạng mở rộng được biểu diễn dưới dạng "cây trò chơi", cho phép người chơi thấy rõ thứ tự các quyết định và các khả năng lựa chọn. Cây trò chơi giúp người chơi suy luận ngược lại từ kết quả đến các quyết định ban đầu, từ đó đưa ra các chiến lược hợp lý trong tình huống cụ thể.

II. Trò chơi tĩnh với thông tin đầy đủ

Trong phần này, trò chơi tĩnh với thông tin đầy đủ sẽ được phân tích. Trò chơi tĩnh là loại trò chơi mà các đối thủ thực hiện các nước đi một cách đồng thời, không biết về hành động của nhau. Điều này tạo ra một môi trường cạnh tranh mà trong đó mỗi người chơi phải dự đoán hành động của đối thủ để đưa ra quyết định tối ưu. Trong trò chơi tĩnh với thông tin đầy đủ, tất cả các người chơi đều biết các chiến lược và mức thưởng phạt của nhau. Điều này giúp cho việc tìm kiếm các điểm cân bằng trở nên khả thi và dễ dàng hơn. Một trong những ứng dụng nổi bật của lý thuyết trò chơi trong lĩnh vực kinh tế là mô hình Cournot, nơi các công ty cạnh tranh về sản lượng. Các công ty này sẽ đưa ra quyết định sản xuất dựa trên dự đoán về sản lượng của đối thủ, từ đó tối ưu hóa lợi nhuận của mình.

2.1. Chiến lược thuần túy và chiến lược hỗn hợp

Trong trò chơi tĩnh với thông tin đầy đủ, các chiến lược có thể được phân loại thành chiến lược thuần túy và chiến lược hỗn hợp. Chiến lược thuần túy là khi người chơi chọn một chiến lược cụ thể mà không thay đổi, trong khi chiến lược hỗn hợp cho phép người chơi chọn giữa nhiều chiến lược với xác suất nhất định. Việc sử dụng chiến lược hỗn hợp có thể giúp người chơi tạo ra sự không chắc chắn cho đối thủ, từ đó nâng cao khả năng đạt được kết quả tốt hơn. Cân bằng Nash trong trò chơi tĩnh với thông tin đầy đủ thường xảy ra khi không có người chơi nào có động lực để thay đổi chiến lược của mình, vì mọi người đều đã tối ưu hóa quyết định của mình dựa trên hành động của đối thủ.

2.2. Phân tích trò chơi tĩnh với thông tin không đầy đủ

Trò chơi tĩnh với thông tin không đầy đủ là loại trò chơi mà không phải tất cả người chơi đều biết thông tin về chiến lược và mức thưởng phạt của nhau. Điều này tạo ra một môi trường phức tạp hơn, nơi mà sự không chắc chắn có thể dẫn đến các quyết định sai lầm. Trong trường hợp này, các khái niệm như cân bằng Bayesian Nash trở nên quan trọng. Cân bằng này cho phép các người chơi đưa ra quyết định dựa trên thông tin không đầy đủ mà họ có. Việc áp dụng lý thuyết trò chơi trong các tình huống thực tế như đấu giá hoặc thị trường cạnh tranh cũng cho thấy sự cần thiết phải hiểu rõ về thông tin và cách mà nó ảnh hưởng đến quyết định của người chơi.

III. Ứng dụng của lý thuyết trò chơi

Lý thuyết trò chơi đã chứng tỏ giá trị thực tiễn trong nhiều lĩnh vực khác nhau, đặc biệt là trong kinh tế học. Các mô hình như Cournot và Bertrand là những ví dụ điển hình cho việc áp dụng lý thuyết trò chơi trong phân tích cạnh tranh. Trong mô hình Cournot, hai công ty cạnh tranh về sản lượng, trong khi mô hình Bertrand tập trung vào cạnh tranh về giá cả. Cả hai mô hình này đều sử dụng lý thuyết trò chơi để tối ưu hóa lợi nhuận và hiểu rõ hơn về hành vi của các đối thủ trong thị trường. Những ứng dụng này không chỉ giúp các nhà kinh tế học mà còn hỗ trợ các nhà quản lý trong việc đưa ra quyết định chiến lược.

3.2. Mô hình Bertrand

Mô hình Bertrand tập trung vào cạnh tranh giá cả giữa các công ty. Trong mô hình này, các công ty đặt giá cho sản phẩm của mình và cạnh tranh để thu hút khách hàng. Kết quả là một cuộc chiến giá cả, nơi mà giá cả có thể giảm xuống mức chi phí sản xuất. Mô hình này minh họa rõ ràng rằng trong một thị trường cạnh tranh hoàn hảo, lợi nhuận của các công ty sẽ giảm xuống mức tối thiểu. Việc áp dụng lý thuyết trò chơi trong mô hình Bertrand giúp các nhà kinh tế học hiểu rõ hơn về động lực cạnh tranh và các chiến lược giá cả.

Trích đoạn nội dung tài liệu

Chương 1 Lý thuyết trò chơi 1.1 Giới thiệu Lý thuyết trò chơi Lý thuyết trò chơi bắt đầu hình thành và được áp dụng từ những ngày đầu của Thế chiến thứ hai, khi các lực lượng hải quân Anh chơi trò mèo vờn chuột với các tàu chiến ngầm của phát xít Đức và họ muốn nắm rõ hơn về trò chơi để có thể thắng được nhiều hơn. Họ đã khám phá ra rằng những bước đi đúng hóa ra lại không phải là những gì mà các hoa tiêu và thuyền trưởng vẫn làm dựa vào trực giác của mình. Bằng cách áp dụng những khái niệm về sau được biết đến như lý thuyết trò chơi, người Anh đã có thể cải thiện thành tích bắn trúng đích của mình lên đáng kể. Thắng lợi đối với các tàu ngầm của địch đã cho phép họ tiếp tục áp dụng lý thuyết trò chơi vào các hoạt động khác trong chiến tranh.

Như vậy, có thể nói lý thuyết trò chơi đã chứng tỏ được mình trong những tình huống sống còn trên thực tế trước khi nó được viết ra giấy và trở thành một lý thuyết mang tính hệ thống [6]. Lý thuyết trò chơi chưa thực sự tồn tại cho đến khi nhà toán học John Von Neumann và nhà kinh tế Oscar Morgenstern xuất bản cuốn sách Lý thuyết trò chơi và các hành vi kinh tế vào năm 1944, tác phẩm này chứa đựng lời giải tối ưu cho những trò chơi tổng bằng không với trò chơi hai người. Từ đó dẫn đến một số lượng lớn các công trình kĩ thuật được viết ra trong các lĩnh 3 vực kinh tế, chính trị, chiến lược quân sự, luật, công nghệ thông tin, sinh học,.Trong mỗi lĩnh vực kể trên, lý thuyết trò chơi lại đưa ra những khám phá quan trọng. Vào năm 1950 John Nash đã phát biểu một định nghĩa về một chiến thuật tối ưu cho trò chơi với nhiều người chơi và nó được biết đến như một cân bằng Nash.

Cân bằng này là đủ tổng quát giúp chúng ta bước ra bên ngoài những ý tưởng giản đơn về cạnh tranh và hợp tác để đạt đến tầm nhìn của cạnh tranh hợp tác hay để đưa cạnh tranh và hợp tác lại gần nhau hơn - một tầm nhìn phù hợp hơn với các cơ hội trong thời đại chúng ta. Vào năm 1965, Reinhard Selten giới thiệu khái niệm lời giải của các cân bằng lí tưởng của các trò chơi con, làm chính xác thêm cân bằng Nash. Vào năm 1967, John Harsanyi phát triển các khái niệm thông tin đầy đủ và trò chơi Bayesian. Năm 1994 ba nhà tiên phong trong lý thuyết trò chơi là John Nash, John Harsanyi, Reinhard Selten đã được nhận giải Nobel về kinh tế.

Trong những năm 1970, lý thuyết trò chơi được áp dụng rộng rãi vào sinh học chủ yếu là do kết quả của các công trình của John Maynard Smith và chiến lược tiến hóa bền vững của ông. Thomas Schelling đã tạo ra các mô hình động và các ví dụ ban đầu của lý thuyết tiến hóa trò chơi và Robert Aumann đóng góp thêm vào trường cân bằng (equilibrium school), phát triển một cân bằng làm thô đi những cân bằng liên quan nhau và phát triển các phân tích chi tiết về giả sử của các kiến thức chung. Với những thành tựu đó, vào năm 2005 hai nhà lý thuyết gia trò chơi này đạt giải thưởng Nobel về kinh tế.2 Biễu diễn trò chơi 1.1 Biểu diễn trò chơi dạng chuẩn tắc Dạng chuẩn tắc của một trò chơi gồm ba thành phần 4 1. N là tập hợp những người chơi trong trò chơi 2.

Các chiến lược có thể thực hiện mỗi người chơi 3. Mức thưởng phạt nhận được của mỗi người chơi cho mỗi sự kết hợp các chiến lược có thể được chọn bởi người chơi đó. Xét một trò chơi N người chơi trong đó các người chơi được đánh số từ 1 đến N và một người chơi tùy ý được gọi là người chơi i. Kí hiệu tập Si là tập hợp các chiến lược có thể thực hiện của người chơi i (hay còn gọi là không gian chiến lược của người chơi i) và kí hiệu si là phần tử bất kì của tập hợp này., sN ) là một sự kết hợp của các chiến lược tương ứng cho mỗi người chơi, kí hiệu ui : S1 × S2 ×.

× SN −→ R là hàm thưởng phạt cho người chơi i và do đó ui (s1 , ., sN ) là mức thưởng phạt cho người chơi i nếu tất cả những người chơi chọn chiến lược (s1 , ., sN ) tương ứng. Định nghĩa 1 [2] Dạng chuẩn tắc của một trò chơi N người chơi được đặc trưng bởi những không gian chiến lược của từng người chơi S1 , ., SN và các hàm thưởng phạt của họ u1 ,. Kí hiệu của một trò chơi là G = {S1 ,. Thông thường 3 thành phần này thường được biểu diễn trong một bảng kết hợp.

Ví dụ 1 Một trò chơi có 2 đối thủ: một người chọn hàng, một người chọn cột. Mỗi đối thủ có 2 chiến lược: S1 = { trên, dưới } và S2 = { trái, phải }, mỗi chiến lược được biểu diễn bởi số hiệu hàng hoặc số hiệu cột của nó. Mức thưởng phạt ghi trong ô đó. Trong ô thưởng phạt có 2 giá trị: giá trị đầu là mức thưởng phạt cho đối thủ chơi theo hàng (đối thủ 1), giá trị thứ hai là mức thưởng phạt cho đối thủ chơi theo cột (đối thủ 2).

Ví dụ: đối thủ 1 chọn 5 di chuyển lên đồng thời đối thủ 2 chọn di chuyển sang trái thì đối thủ 1 sẽ −3 điểm còn đối thủ 2 cũng sẽ −3 điểm. Di chuyển sang trái Di chuyển sang phải Di chuyển lên -3,-3 0,-6 Di chuyển xuống -6,0 -1,-1 Tuy nhiên trò chơi này cũng có biễu diễn theo 2 ma trận riêng lẻ: Ma trận thưởng phạt cho đối thủ 1: Di chuyển sang trái Di chuyển sang phải Di chuyển lên -3 0 Di chuyển xuông -6 -1 Ma trận thưởng phạt cho đối thủ 2: Di chuyển sang trái Di chuyển phải Di chuyển lên -3 -6 Di chuyển xuống 0 -1 Chú ý: Khi một trò chơi được biểu diễn dưới dạng chuẩn tắc thì coi như mỗi đối thủ hành động một cách đồng thời hay không biết về hành động của người kia.2 Biễu diễn trò chơi dạng mở rộng Dạng mở rộng được biểu diễn dưới dạng "cây trò chơi". Hầu hết các tình huống trong thực tế có nhiều cách ra quyết định và mỗi cách như vậy lại có nhiều khả năng để lựa chọn và nếu chỉ dùng trí nhớ thì khó nhớ hết được các khả năng đó. Chúng ta cần một công cụ hiệu quả hơn để suy luận ngược lại bài toán và giúp chúng ta có cái nhìn tổng quát hơn.

Công cụ đó chính là "cây trò chơi". Như vậy "cây trò chơi " chỉ ra thứ tự các quyết định trong trò chơi. 6 Mỗi đỉnh biểu diễn các khả năng mà người chơi có thể lựa chọn. Người chơi được chỉ rõ bằng một con số ghi trên đỉnh, các đoạn thẳng đi ra từ đỉnh đó biểu diễn các khả năng có thể của người chơi đó.

Mức thưởng phạt được ghi rõ tại đáy cạnh. Một cạnh từ một đỉnh u đến một đỉnh v kế tiếp (v được vẽ dưới u ) chỉ một bước đi có thể có trong trò chơi. Những đỉnh mà không có đỉnh kế tiếp trong cây được gọi là các đỉnh cuối hay các lá. Như vậy, trong dạng mở rộng này thì các đối thủ có thông tin về sự lựa chọn của các đối thủ khác.

Và chúng ta sẽ sử dụng thông tin trên cây đồ thị để dự đoán tất cả các bước đi trong tương lai và suy ngược lại những quyết định ban đầu. Ví dụ 2 ( Cây trò chơi )[7] Giả sử thị trường máy hút bụi ở Cu - Ba đang bị chi phối bởi nhãn hiệu Fastcleaner (F) và một công ty mới có tên Newcleaner (N) đang xem xét có nên nhảy vào thị trường này hay không? Nếu N tham gia thì F có hai lựa chọn: dàn xếp với N hoặc chiến tranh giá cả. Giả sử F dàn xếp với N khi N tham gia thị trường thì N sẽ có lợi nhuận 100.000 đô la, nếu cạnh tranh giá cả thì N sẽ mất 200. Nếu N không nhảy vào thị trường Cuba thì lợi nhuận của công ty N sẽ là 0.

Chúng ta sẽ mô tả bài toán này bằng "cây trò chơi": 7 Hình 1.1: Ví dụ về cây trò chơi 1.3 Các loại trò chơi Có một số phương pháp phân loại trò chơi. Cách phân chia thứ nhất là căn cứ vào khả năng hợp đồng và chế tài hợp đồng của những người chơi thì có thể chia trò chơi làm hai loại: trò chơi hợp tác (cooperative games) và trò chơi bất hợp tác (non-cooperative games). Cách phân chia thứ hai là căn cứ vào thông tin của những người chơi thì các trò chơi được chia thành trò chơi với thông tin đầy đủ (complete information)và trò chơi với thông tin không đầy đủ (incomplete information)hoặc là trò chơi với thông tin hoàn hảo (perfect information) và thông tin không hoàn hảo (imperfect information). Cách phân chia thứ ba là căn cứ vào thời gian hành động của mỗi người chơi, các trò chơi được chia làm hai loại là tĩnh và động.

Phối hợp cách phân chia thứ hai và thứ ba ta có 4 dạng thức trò chơi là: trò chơi động với thông tin đầy đủ, trò chơi tĩnh với thông tin đầy đủ, trò chơi tĩnh với thông tin không đầy đủ, trò chơi tĩnh với thông tin không đầy đủ. Cách phân chia thứ tư là dựa trên tổng kết quả (payoff) của những người chơi mà ta phân chia thành trò chơi hai loại tổng bằng không và tổng khác không.1 Trò chơi tổng bằng không và trò chơi tổng khác không Để hiểu rõ hơn về hai loại trò chơi này, ta chỉ xét các trò chơi hai 8 người tham gia. Với Si , i ∈ {1, 2} là tập các chiến lược của hai người chơi và hàm thưởng phạt ui : S1 × S2 −→ R. Nếu hai người chơi lần lượt chọn các chiến lược s1j , s2k thì mức thưởng phạt của hai người lần lượt là u1 (s1j , s2k ), u2 (s1j , s2k ), j = 1,.

Để thuận tiện, ta có thể biểu diễn trò chơi dưới dạng một ma trận m × n:   u (s , s ) ui (s11 , s22 ) · ui (s11 , s2n )  i 11 21   ui (s12 , s21 ) ui (s12 , s22 ) · ui (s12 , s2n )    Ai =   , i = 1, 2  .