Bài giảng Chương 2 Các trò chơi tĩnh với thông tin đầy đủ

CHƯƠNG HAI CÁC TRÒ CHƠI TĨNH VỚI THÔNG TIN ĐẦY ĐỦ NỘI DUNG CƠ BẢN A. Xét trò chơi với các tính chất sau  Trò chơi được xét trong chương này có tính chất sau:(1) các đấu thủ cùng đồng thời chọn hành động; (2) Sau đó các đấu thủ nhận được thu hoạch phụ thuộc vào tổ hợp các hành động vừa chọn.  Tong các trò chơi tĩnh đi cùng một lúc , ta chú ý đến trò chơi với thông tin đầy đủ B. Điểm qua những vấn đề cơ bản  Mô tả một trò chơi  Giải quyết các bài toán cơ bản của lý thuyết trò chơi  Phát triển công cụ để sử dụng trong phân tích trò chơi tĩnh với thông tin đầy đủ  Khái niệm chiến lược bị trội ngặt  Cân bằng Nash LÝ THUYẾT CƠ BẢN TRÒ CHƠI DẠNG CHUẨN VÀ CÂN BẰNG NASH  Biểu diễn dạng chuẩn của một trò chơi  Định nghĩa: Biểu diễn dạng chuẩn của trò chơi là chỉ rõ (1) Các đấu thủ trong trò chơi (2) Các chiến lược sẵn có đối với mỗi đấu thủ và (3) Thu hoạch của mỗi đấu thủ nhận được đối với mỗi tổ hợp chiến lược mà các đấu thủ có thể chọn Hình thức biểu diễn dưới dạng chuẩn  Biểu diễn dưới dạng ma trận là hình thức biểu diễn chủ yếu của trò chơi rời rạc dưới dạng chuẩn  Phân tích biểu diễn dưới dạng ma trận  (1) Biết được các đấu thủ  (2) Biết các chiến lược sẵn có  (3) Biết được các thu hoạch Các thí dụ Tù nhân 2 Không khai khai Tù nhân 1 Không khai -2 , -2 -10 , -1 Khai -1 , -10 -5 , -5 Định nghĩa hình thức  Ta xét trò chơi có n đấu thủ.  Mỗi đấu thủ có một tập hợp các chiến lược sẵn có ký hiệu là S. Si là tập hợp các chiến lược sẵn có của đấu thủ i.  si là một phần tử của Si , nghĩa là si là một chiến lược của đấu thủ i.  Gọi ui(s1,s2,,sn ) là hàm thu hoạch của đấu thủ i khi các đấu thủ chọn các chiến lược (s1,s2, sn). Định nghĩa: Biểu diễn dạng chuẩn của trò chơi  §Þnh nghÜa:  BiÓu diÔn d¹ng chuÈn cña mét trß ch¬i n ®Êu thñ chØ râ c¸c kh«ng gian chiÕn l­îc S1,..., Sn cña c¸c ®Êu thñ vµ c¸c hµm thu ho¹ch u1,...,un cña hä.  Ta ký hiÖu trß ch¬i nµy lµ G = {S1,..., Sn; u1,...,un}. Bài tập thực hành  Biểu diễn dạng chuẩn của trò chơi: “ Cuộc chiến giữa hai giới”:  P và C đang quyết định chọ tiêu khiển vào buổi tối:  Họ chọ xem di xem ca nhạc hay đấu bóng. Nếu cả hai cùng xem ca nhạc thì thu hoạch của C là 2 và P là 1.  Nếu cả hai đi xem đấu bóng thì thu hoạch của C là 1 và P là 2. Nếu đi xem các chương trình khác nhau thì thu hoạch của họ bằng không PHÉP KHỬ LẶP CÁC CHIẾN LƯỢC BỊ TRỘI NGẶT  Định nghĩa :  Chiến lược si là một chiến lược trội ngặt đối với người chơi i nếu nó duy nhất cực đại thu hoạch của người chơi i đối với bất kỳ chiến lược nào mà đối thủ của người chơi i có thể chơi.  Hiểu thế nào định nghĩa này (giải thích) Thí dụ chiến lược trội ngặt Tù nhân 2 Không khai khai Tù nhân 1 Không khai -2 , -2 -10 , -1 Khai -1 , -10 -5 , -5 CHIẾN LƯỢC BỊ TRỘI NGẶT  Định nghĩa trong trò chơi dạng chuẩn có n đấu thủ , trong đó đấu thủ i có tập hợp các chiến lược Si.  Chiến lược si của người chơi i bị trội ngặt bởi si* , nếu mỗi tổ hợp của các chiến lược của các đấu thủ còn lại , thu hoạch của i do chọn si kém hơn hẳn khi chọ si* Hiểu thế nào định nghĩa này Xét trò chơi ma trận: (1) Để xem đấu thủ hàng có chiến lược bị trội ngặt không thì ta so sánh giữa các thu hoạch ở hai hàng tương ứng (2) Để xem đấu thủ cột có chiến lược bị trội ngặt hay không thì ta so sánh các phần tử của các cột tương ứng. Định nghĩa hình thức  §Þnh nghÜa: Trong trß ch¬i d¹ng chuÈn G = {S1,..., Sn; u1,...,un}, cho s’i vµ s”i lµ chiÕn l­îc kh¶ thi (cã thÓ thùc hiÖn) ®èi víi ®Êu thñ i ( nghÜa lµ, s’i vµ s”i lµ phÇn tö cña Si ). ChiÕn l­îc s’i lµ bÞ tréi ngÆt bëi chiÕn l­îc s”i nÕu víi mçi tæ hîp kh¶ thi cña c¸c chiÕn l­îc cña nh÷ng ®Êu thñ cßn l¹i, thu ho¹ch cña ®Êu thñ i b»ng viÖc chän chiÕn l­îc s’i kÐm h¬n h¼n khi chän chiÕn l­îc s”i:  ui(s1,..., si-1, s’i , si+1,..., sn) < ui(s1,..., si-1, s”i , si+1,..., sn) ®èi víi mäi (s1,..., si-1, si+1,..., sn) cã thÓ ®­îc x©y dùng tõ c¸c kh«ng gian chiÕn l­îc S1,..., Si-1, Si+1,..., Sn cña nh÷ng ®Êu thñ cßn l¹i. Thuật toán  (1) Có thể thực hiện tìm chiến lược bị trội ngặt của đấu thủ hàng hoặc cột. Nếu phát hiện chiến lược bị trội ngặt ở hàng (cột ) thì ta loại hàng (cột) tương ứng.  (2) Sau khi loại hàng (cột) trò chơi được thu gọn và quá trình lại lặp lại trên trò chơi này cho đến khi kết thúc Thí dụ và phân tích cách giải Xét trò chơi trừu tượng sau: Đấu thủ 2 Trước Giữa Phải Đấu thủ 1 Trên 1 , 0 1 , 2 0,2 Dưới 0 , 3 0 , 2 1,0 Giải thích thuật toán- Đấu thủ 1 nghĩ  §Êu thñ 1 cã hai chiÕn l­îc cßn ®Êu thñ 2 cã ba: S1 = {Lªn, Xuèng} vµ S2 = {Tr¸i, Gi÷a, Ph¶i}. Víi ®Êu thñ 1, c¶ Lªn hay Xuèng ®Òu kh«ng bÞ tréi ngÆt: Lªn tèt h¬n Xuèng nÕu ®Êu thñ 2 ch¬i n­íc Tr¸i (v× 1>0), nh­ng Xuèng l¹i tèt h¬n Lªn nÕu ®Êu thñ 2 ch¬i n­íc Ph¶i (v× 2>0).  Víi ®Êu thñ 2, dï c¸ch g× th× chiÕn l­îc Ph¶i còng bÞ tréi ngÆt bëi chiÕn k­îc Gi÷a (v× 2>1 vµ 1>0), bëi vËy mét ®Êu thñ 2 s¸ng suèt sÏ kh«ng ch¬i n­íc Ph¶i. Giải thích thuật toán  Nh­ vËy, nÕu ®Êu thñ 1 biÕt ®Êu thñ 2 lµ ng­êi s¸ng suèt th× ®Êu thñ 1 cã thÓ lo¹i chiÕn l­îc Ph¶i ra khái kh«ng gian chiÕn l­îc cña ®Êu thñ 2.  §iÒu ®ã cã nghÜa lµ, nÕu ®Êu thñ 1 biÕt ®Êu thñ 2 lµ ng­êi s¸ng suèt th× ®Êu thñ 1 cã thÓ ch¬i trß ch¬i trong h×nh 1 nh­ thÓ lµ ch¬i trß ch¬i trong h×nh 2. Trò chơi rút gọn Đấu thủ 2 Tr¸i Giữa ĐÊu thñ 1 Lªn 1,0 1,2 Xuèng 0,3 0,1 Đấu thủ 2 nghĩ  Trong H×nh 2, ®èi víi ®Êu thñ 1, chiÕn l­îc Xuèng b©y giê l¹i bÞ tréi ngÆt bëi chiÕn l­îc Lªn, v× thÕ nÕu ®Êu thñ 1 s¸ng suèt (vµ ®Êu thñ 1 biÕt ®Êu thñ 2 lµ ng­êi s¸ng suèt, do ®ã trß ch¬i trong h×nh 2 lµ thÝch øng) th× ®Êu thñ 1 sÏ kh«ng ch¬i chiÕn l­îc Xuèng.  Nh­ vËy, nÕu ®Êu thñ 2 biÕt ®Êu thñ 1 lµ ng­êi s¸ng suèt, vµ ®Êu thñ 2 biÕt r»ng ®Êu thñ 1 biÕt ®Êu thñ 2 lµ ng­êi s¸ng suèt (do ®ã ®Êu thñ 2 biÕt r»ng h×nh 2 lµ thÝch øng), th× ®Êu thñ 2 cã thÓ lo¹i bá chiÕn l­îc Xuèng ra khái kh«ng gian chiÕn l­îc cña ®Êu thñ 1, cßn l¹i trß ch¬i nh­ trong h×nh 3. Trò chơi rút gọn ĐÊu thñ 2 ĐÊu thñ 1 Tr¸i Giữa Lªn 1,0 1,2 Kết cục của trò chơi Nh­ng víi ®Êu thñ 2 b©y giê, chiÕn l­îc Tr¸i l¹i bÞ tréi hoµn toµn bëi chiÕn l­îc Gi÷a, cßn l¹i (Lªn, Gi÷a) nh­ lµ kÕt côc cña trß ch¬i. Nhược điểm của thuật toán Mỗi bước đi của thuật toán lại đòi hỏi một giả địnhvề điều mà các đấu thủ đã biết về sự sáng suốt của nhau. Nếu muốn áp dụng quá trình này một số bước tùy ý thì cần phải giả định kiến thức chung là : CÁC ĐẤU THỦ LÀ NHỮNG NGƯỜI SÁNG SUỐT Quá trình này có thể dẫn đến kết quả dự đoán mơ hồ Bài tập Bài tập 1: Sử dụng thuật toán cân bằng trội ngặt tìm chiến lược chiến lược cân bằng của trong bài toán thế nan giải của tù nhân. Bài tập 2: Dùng thuật toán phép khử lặp các chiến lược bị trội ngặt tìm chiến lược cân bằng của bài toán cuộc chiến giữa 2 giới Bài tập Đấu thủ 2 Trước Giữa Phải Đấu thủ 1 Tr 2 , 0 3 , 1 0,2 D 0 , 2 2 , 2 4,3 sử dụng thuật toán phép khử lặp để giải bài toán sau L2 M2 R2 L1 0,4 4,0 5,3 M1 4,0 0,4 5,3 R1 3,5 3,5 6,6 PHÁT TRIỂN ĐỊNH NGHĨA CÂN BẰNG NASH  Mét c¸ch ®Ó ph¸t triÓn ®Þnh nghÜa c©n b»ng Nash lµ nÕu lý thuyÕt trß ch¬i cung cÊp mét nghiÖm duy nhÊt cho mét bµi to¸n LTTC th× nghiÖm ®ã ph¶i lµ c©n b»ng Nash theo nghÜa sau ®©y:  Gi¶ sö LTTC ®­a ra mét dù ®o¸n duy nhÊt vÒ chiÕn l­îc mµ mçi ®Êu thñ sÏ chän. §iÒu cÇn thiÕt ®Ó dù ®o¸n nµy lµ ®óng lµ mçi ®Êu thñ s½n lßng chän chiÕn l­îc dù ®o¸n bëi lý thuyÕt nµy. Nh­ vËy, chiÕn l­îc dù ®o¸n cña mçi ®Êu thñ ph¶i lµ chiÕn l­îc ph¶n øng tèt nhÊt cña ®Êu thñ ®ã ®èi víi c¸c chiÕn l­îc dù ®o¸n cña c¸c ®Êu thñ kh¸c. Dù ®o¸n nh­ vËy cã thÓ ®­îc gäi lµ æn ®Þnh chiÕn l­îc hay tù tu©n thñ, bëi v× kh«ng ®Êu thñ nµo muèn chÖch khái chiÕn l­îc dù ®o¸n cña m×nh. Chóng ta sÏ gäi dù ®o¸n nh­ vËy lµ mét c©n b»ng Nash. Định nghĩa cân bằng Nash  Trong trß ch¬i d¹ng chuÈn n ®Êu thñ G = {S1,..., Sn; u1,...,un}, c¸c chiÕn l­îc (s*1,..., s*n) lµ mét c©n b»ng Nash nÕu ®èi víi mçi ®Êu thñ i, s*i lµ ph¶n øng tèt nhÊt cña ®Êu thñ i tr­íc c¸c chiÕn l­îc ®· cho ®èi víi n-1 ®Êu thñ cßn l¹i (s*1,..., s*i-1,s*i+1,..., s*n):  ui(s*1,..., s*i-1, s*i , s*i+1,..., s*n)  ui (s*1,..., s*i-1, si , s*i+1,..., s*n) (NE)  víi mäi chiÕn l­îc kh¶ thi si trong Si; nghÜa lµ, si lµ nghiÖm  maxui(s*1, , s*i-1, si, s*i+1, , s*n).  siSi Giải thích cân bằng NASH  Ta gi¶ sö r»ng lý thuyÕt trß ch¬i cho ta c¸c chiÕn l­îc (s’1,..., s’n) lµ nghiÖm cña trß ch¬i d¹ng chuÈn G = {S1,..., Sn; u1,...,un}. Nãi r»ng (s’1,..., s’n) kh«ng ph¶i lµ c©n b»ng Nash cña G còng t­¬ng ®­¬ng víi nãi r»ng cã tån t¹i mét ®Êu thñ i mµ s’i kh«ng ph¶i lµ ph¶n øng tèt nhÊt tr­íc (s’1,..., s’i-1, s’i+1,..., s’n). NghÜa lµ cã tån t¹i s”i trong Si sao cho  ui(s’1,..., s’i-1, s’i , s’i+1,..., s’n) < ui(s’1,..., s’i-1, s”i , s’i+1,..., s’n).  Nh­ vËy, nÕu lý thuyÕt cho ta c¸c chiÕn l­îc (s’1,..., s’n) lµ nghiÖm nh­ng c¸c chiÕn l­îc nµy kh«ng ph¶i lµ mét c©n b»ng Nash th× Ýt nhÊt mét ®Êu thñ sÏ cã ®éng c¬ chÖch khái dù ®o¸n lý thuyÕt, do ®ã lý thuyÕt nµy sÏ bÞ bãp mÐo bëi diÔn biÕn thùc tÕ cña trß ch¬i. Hiểu thế nào định nghĩa này Ứng với mỗi tập hợp n-1 chiến lược của các đấu thủ còn lại thì s*I là phản ứng tốt nhất Chiến lược của N-1 đấu thủ còn lại cũng phải thoả mãn như vậy Thí dụ S C R T 0,4 4,0 5,3 M 4,0 0,4 5,3 B 3,5 3,5 6,6 Quy tắc giải  Để đơn giản ta xét trò chơi 2 đấu thủ: với mỗ đấu thủ và với mỗi chiến lược ta xác định phản ứng tốt nhất của đấu thủ còn lại đối với chiến lược đó.  Quy tắc sau:  (1) Chọ một đấu thủ thí dụ 2 , ta xét các chiến lược của 1 từ trái sang phải S, C R Quy tắc giải  - Cố định cột S nghĩa là 2 chơi S thì phản xét phản ứng của 1: phản ứng tốt nhất của 1 là so sánh các phần tử của cột 1 thì 4>3 và 4>0 do đó M của 1 là phản ứng tốt nhất của 1 khi 2 chơi S- gạch chân 4  Cố định C , cố định R xét tương tự như trên  3. Cố định hàng, cũng xét như vậy .  Cân bằng NASH sẽ là chiến lược ứng với ô có 2 thu hoạch được gạch chân Kết cục của trò chơi L C R T O,4 4,0 5,3 M 4,0 0,4 5,3 B 3,5 3,5 6,6 Các bài tập thực hành  1. Giải bài toán cuộc chiến 2 giới  2. Thế nan giải của tù nhân  3. Các bài tập đã tìm cân bằng trội ngặt Bài tập tìm cân bằng NASH Đấu thủ 2 Trước Giữa Phải Đấu thủ 1 S1 2 , 0 3 , 1 0,2 S2 0 , 2 2 , 2 4,3 Bài tập Đấu thủ 1 S R Đấu thủ 2 T a , b e , d B e , f g ,h Bài tập  (1) Nếu (T, S) là chiến lược cân bằng trội ngặt thì quan hệ giữa các thu hoạch tong bản như thế nào  (2) Nếu (T,S) là cân bằng NASH thì các quan hệ giữa các thu hoạch trong bảng như thế nào Nếu (T,S) là cân bằng trội ngặt thì có phải là cân bằng NASH không? Định lý: Quan hệ giữa phép khử lặp và cân bằng NASH Trong trò chơi dạng chuẩn n đấu thủ , nếu phép khử lặp của các chiến lược bị trội ngặt loại bỏ tất cả các chiến lược từ chiến lược (s*1,,s*n) thì những chiến lược này là cân bằng NASH duy nhất của trò chơi Cân bằng NASH mạnh hơn các chiến lược bị trội ngặt Trong trò chơi dạng chuẩn n đối thủ nếu các chiến lược (s*1,,s*n) là một cân bằng NASH thì chúng không bị loại bởi phép khử lặp các chiến lược bị trội ngặt CHƯƠNG 3 ỨNG DỤNG LÝ THUYẾT TRÒ CHƠI TĨNH VỚI THÔNG TIN ĐẦY ĐỦ TRONG VIỆC XÁC ĐỊNH CHIẾN LƯỢC KINH DOANH MỤC ĐÍCH Nhằm giới thiệu lý thuyết đã trình bày trong các chương trước vào:  kinh tế và  kinh doanh. PHÂN LOẠI ỨNG DỤNG THEO CẤU TRÚC THỊ TRƯỜNG  Các cấu trúc thị trường được xét dưới giác độ của mô hình kinh điển.  Bốn ứng dụng sử dụng các công cụ phát triển ở chương trước là:  (1) Mô hình Cournot với hai công ty độc quyền (1883)  (2) Mô hình Bertrand (1883) Mô hình phân xử theo đề nghị cuối cùng Mục đích giải quyết các ứng dụng Trong mỗi ứng dụng, trước hết ta chuyển không chính thức của bài toán sang biểu diễn dạng chuẩn của trò chơi Tìm cân bằng NASH của các trò chơi đã kể trêndựa trên biểu diễn dưới dạng chuẩn của nó. Mô hình Cournot với 2 công ty độc quyền  Trong một thị trường có 2 công ty ( Công ty I và II) cung ứng một loại sản phẩm thuần nhất.  Lượng cung của công ty I và II , ký hiệu q1 và q2 tương ứng  Chi phí của công ty I sản xuất qi là cqi  Tổng cung trên thị trường là Q=q1+q2 và giá của thị trường về sản phẩm đólà p(Q) Chuyển bài toán sang dạng chuẩn Tập hợp đấu thủ là công ty I và công ty II Gọi tập hợp các chiến lược của công ty i là Si thì Si chính là các quyết định cung của i, nghiã là Si gồm tất cả qi>0 Thu hoạch của công ty i chính là lợi nhuận cực đại của i. Cân bằng Nash của bài toán  Để tìm cân bằng Nash , ta phải theo định nghĩa :Trong trò chơi dạng chuẩn n đấu thủ G . Các chiến lược (s*1,sn *) là một cân bằng NASH nếu đối với mỗi i , s*i là phản ứng tốt nhất của i đứng trước các chiến lược đã cho của n-1 đấu thủ còn lại (s*1,s*i-1,s*i-1,s*n) với mọi chiến lược có thể có của i.  Trong trường hợp này phản ứng tốc nhất là hành vi cực đại lợi nhuận của mỗi hãng Lời giải của mô hình Giả sử hàm cầu ngược thị trường về hai hàng hoá mà hai công ty này cung cấp là p(Q). Hàm chi phí của mỗi công ty là : cqi Lời giải cân bằng Nash là: Mở rộng khi có n người chơi thì lời giải sẽ là 3 ** 21 ca qq   1 ** 21    n ca qq Bảng các tham số và lời giải của mô hình Cournot 4 ** 21 ca qq   1 ** 21    n ca qq 3 ** 21 ca qq   Tham số Cân bằng Nash n a c 2 a c 3 a c n â c Mô hình Bertrand Thay cho việc cạnh tranh về lượng các công ty lựa chọn giá . Như vậy mô hình này khác với mô hình trên ở: (1)Không gian chiến lược vì lúc này công ty i chọn pi không chọn qi; Hàm thu hoạch (công ty sẽ cực đại lợi nhuận theo giá); (3) Hành vi trong cân bằng Nash của mô hình này cũng khác Chuyển bài toán sang dạng chuẩn Tập hợp đấu thủ là công ty I và công ty II Gọi tập hợp các chiến lược của công ty i là Si thì Si chính là các quyết định cung của i, nghiã là Si gồm tất cả pi>0 Thu hoạch của công ty i chính là lợi nhuận cực đại của i theo giá pi. Lời giải của mô hình Giả sử biết hàm cầu thị trường về hai hàng hoá mà hai công ty i cung cấp là qi=a-pi+bpj . Hàm chi phí của mỗi công ty là : cqi Lời giải cân bằng Nash là: b ca pp    2 ** 21 Mô hình phân xử theo đề nghị cuối cùng Giả thiết: Có sự tranh chấp giữa ban lãnh đạo công ty và công đoàn Họ đã ngồi vào bàn đàm phán , các đề nghị sẽ được đưa ra . Công đoàn đề nghị tiền lương là wu, công ty đề nghị tiền lương wf (wf< wu) Người phân xử sẽ quyết định một trong 2 đề nghị làm phương án giả quyết. Biết rằng người phân xử có một phương án giải quyết lý tưởng x và nếu đề nghị nào gần x hơn thì sẽ được chọn. Biết rằng X có phân phối chuẩn với hàm mật độ xác suất F(x). Tìm tiền lương cân bằng. Mô hình phân xử theo đề nghị cuối cùng Lời giải của mô hình  Giả sử phương án giải quyết được người phân sử ưa thích có phân phối cuẩn với giá trị trung bình là  và phương sai là 2 , khi đó các mức đề nghị cân bằng Nash sẽ là 2 *, 2 * 22      fu ww CHƯƠNG IV LÝ THUYẾT NÂNG CAO: CHIẾN LƯỢC HỖN HỢP VÀ SỰ TỒN TẠI CÂN BẰNG Giới thiệu : Chiến lược hỗn hợp  Chúng ta đã Si là tập hợp các chiến lược của đấu thủ i ,  tổ hợp các chiến lược (s1*,sn*) là cân bằng NASH nếu với mỗi đấu thủ i si* là phản ứng tốt nhất đối với n-1 đấu thủ còn lại.  Theo định nghĩa này sẽ không có cân bằng NASH nào trong trò chơi sau đây Trò chơi đọ xu – không có cân bằng chiến lược thuần tuý Đấu thủ 2 Sấp Ngửa Đấu thủ 1 Sấp -1 , 1 1 , -1 Ngửa 1 , -1 -1 ,1 Nhận xét  Trong trò chơi này tập hợp chiến lược của mỗi đấu thủ là {ngửa, sấp}  Nhưng nếu người chơi không phải sẽ chơi ngửa hoặc sấp mà sẽ chơi ngửa với xác suất p và sấp với xác suất là q=1-p thì ta sẽ có khái niệm về chiến lược hỗn hợp Giải thích chiến lược hỗn hợp  Một chiến lược hỗn hợp đối với đấu thủ i là một phân phối xác suất trên (một số hay tất cả) các chiến lược trong tập các chiến lược của i  Điều quan trọng hiểu chiến lược hỗn hợp ở đây là tập hợp các xác suất gắn với chiến lược thuần sao cho mỗi chiến lược thuần có một xác suất chơi dương và tổng xác suất ứng với tất cả các chiến lược thuần phái bằng 1. Định nghĩa chiến lược hỗn hợp  Định nghĩa:  Một chiến lược hỗn hợp đối với đấu thủ i là một phân phối xác suất trên (một số hoặc tất cả) các chiến lược trong si.  Một cách hình thức có thể định nghĩa: Trong trò chơi dạng chuẩn G. Khi đó một chiến lược hỗn hợp đối với đấu thủ i là một phân phối xác suất pi=(pi1,..pik) vơi 0pik1, pi1++pik=1 Thí dụ Đấu thủ 2 Sấp Ngửa Đấu thủ 1 Sấp -1 , 1 1 , -1 Ngửa 1 , -1 -1 ,1 Giải thích  Một chiến lược của hỗn hợp của đấu thủ 1 là một phân phối xác suất trên các chiến lược {sấp , ngửa} chẳng hạn người chơi 1 sẽ chơi sấp với xác suất p và ngửa vơi xác suất 1-p.  chiến lược của hỗn hợp của đấu thủ 2 là một phân phối xác suất trên các chiến lược {sấp , ngửa} chẳng hạn người chơi 2 sẽ chơi sấp vớp xác suất q và ngửa với xác suất 1-q. Thí dụ 2: Cuộc chiến giữa 2 giới P Ca nhạc Đấu bóng C Ca nhạc 2 , 1 0 , 0 Đấu bóng 0 , 0 1 ,2 Giải thích  Giả sử p1 là xác suất để C chơi chiến lược ca nhạc và 1-p1 là xác suất để C chơi chiến lược đấu bóng  Giả sử q1 là xác suất để P chơi chiến lược ca nhạc và 1-q1 là xác suất để P chơi chiến lược đấu bóng Thí dụ Về bài toán tìm chiến lược hỗn hợp P CN TĐ C CN 2 , 1 0 , 0 TĐ 0 , 0 1 ,2 Giải bài toán cuộc chiến giữa 2 giới  Tập hợp người chơi chỉ có 2 người là C và P.  Tìm chiến lược hỗn hợp:  (1) Chiến lược hỗn hợp của C: giả sử C chơi Ca nhạc với xác suất p1 và Đấu bóng với xác suất p2 =1-p1  (2) Chiến lược hỗn hợp của P: Giả sử P chơi ca nhạc với xác suất q2= 1-q1 và xem đấu bóng với xác suất q1. Phân tích để thiết lập bài toán  Lợi ích mà C thu được khi chơi chiến lược Ca nhạc là : 2q1+0.q2.Lợi ích mà C thu được khi chơi ĐB là: 0q1+1q2.  Vậy lợi ích kỳ vọng của C khi chơi chiến lược hỗn hợp p1,p2 sẽ là:  p1[2q1+0.q2]+p2[0q1+1q2]  Tương tự lợi ích kỳ vọng của P sẽ là:  q1[1p1+0.p2]+q2[0p1+2p2] Thiết lập bài toán và giải  Như vậy bài toán tìm lợi ích kỳ vọng của đấu thủ hàng sẽ là  Max p1(2q1+0.q2)+p2(0.q1+1.q2)(1)  P1+p2=1 , pi không âm  Max q1(1p1+0.p2)+q2(0.p1+1.p2)(2)  q1+ q2=1 , qi không âm  Cách giải: Thay p1=1-p2 và (1) và q1=1-q2 vào (2) và giải ta sẽ được chiến lược hỗn hợp cân bằng Nash Thiết lập bài toán trong trường hợp tổng quát  Xét trò chơi với 2 đấu thủ1 và 2. Gọi S1, S2 là không gian chiến lược của đấu thủ 1 và 2 tương ứng.  Gọi J là số chiến lược thuần trong S1, K là số chiến lược thuần trong S2.Nghĩa là:  S1={s11,., s1J} và S2={s21,., s2K}  Giả sử đấu thủ 1 tin rằng đấu thủ 2 chơi các chiến lược {s21,., s2K} với xác suất ={p21,., p2K}, thì thu hoạch kỳ vọng của đấu thủ 1 từ việc chơi chiến lược thuần túy s1j là: Thiết lập bài toán trong trường hợp tổng quát  thì thu hoạch kỳ vọng của đấu thủ 1 từ việc chơi chiến lược thuần túy s1j là:  thì thu hoạch kỳ vọng của đấu thủ 1 từ việc chơi chiến lược hỗn hợp là:  (*) ),( 211 1 2 kj K k k ssup  ),(),(),( 211 1 21 1 211 1 2 1 1211 kj K k kj J j kj K k k J j j ssuppssuppppv    Thu hoạch kỳ vọng của đấu thủ 2  Thu hoạch kỳ vọng của đấu thủ 2 từ việc chơi chiến lược thuần túy s2k là:  thì thu hoạch kỳ vọng của đấu thủ 2 từ việc chơi chiến lược hỗn hợp là:  (**) ),( 212 1 1 kj J j j ssup  ),(),(),( 212 1 21 1 212 1 1 1 2212 kj K k kj J j kj J j j K k k ssuppssuppppv    Điều kiện của cân bằng  Khi cho v1(p1,p2) vµ v2(p1,p2) ta cã thÓ ph¸t biÓu l¹i ®ßi hái cña c©n b»ng Nash r»ng chiÕn l­îc hçn hîp cña mçi ®Êu thñ lµ mét ph¶n øng tèt nhÊt ®èi víi chiÕn l­îc hçn hîp cña ®Êu thñ kia: ®Ó