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 .