Bài giảng Lý thuyết nâng cao: chiến lược hỗn hợp và sự tồn tại cân bằng

Nội dung của bài giảng Lý thuyết nâng cao: chiến lược hỗn hợp và sự tồn tại cân bằng nhằm trình bày về chiến lược hỗn hợp, giải thích chiến lược hỗn hợp, giải bài toán chiến lược hai giới.
Nội dung trích xuất từ tài liệu:
Bài giảng Lý thuyết nâng cao: chiến lược hỗn hợp và sự tồn tại cân bằng 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 đâyTrò 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ủ Sấp -1 , 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ủ Sấp -1 , 1 1 , -11 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óngC 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óngThí 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 ,2Giả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ổngquá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à: K p k 1 u (s1 j , s2k ) 2k 1 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à: J K J K (*) (p , p )  p p u (s , s )  v 1 1 2   j1 1j k1 ...