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

Chia sẻ: Gdfb Gdfb | Ngày: | Loại File: PDF | Số trang:73

Thêm vào BST

Báo xấu

290
lượt xem 20
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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 đâ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ủ 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 , -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à: 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 p p u (s ,s ) 2k 1 1j 2k  j k 1 1 1j 2k 1 1j 2k
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à: J  p u (s j 1 1j 2 1j , s2k )  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à: K J J K  (**) v2(p1, p2) p2k p1ju2 (s1j , s2k )  p1j p2ku2(s1j ,s2k ) k1 j1 j k 1 1
Điều kiện của cân bằng  Khi cho v1(p 1,p2) vµ v2(p 1,p 2) 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: ®Ó cÆp chiÕn lîc hçn hîp (p*1,p*2) lµ mét cÊn b»ng Nash, p*1 ph¶i tho¶ m·n  v1(p*1,p*2)  v1(p1,p*2)  ®èi víi mäi ph©n phèi x¸c suÊt p1 trªn S1, vµ p2 ph¶i tho¶ m·n  v2(p*1,p*2)  v2(p*1,p2)  ®èi víi mäi ph©n phèi x¸c suÊt p2 trªn S2.
Định nghĩa : cân bằng NASH chiến lược hỗn hợp  Trong trß ch¬i d¹ng chuÈn hai ®Êu thñ  G = {S1,S2;u1,u2}, c¸c chiÕn lîc hçn hîp (p*1,p*2) lµ mét c©n b»ng Nash nÕu 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: (*) vµ (**) ph¶i ®óng.
Định lý: NASH (1950)  Trong trò chơi dạng chuẩn N đấu thủ G={S1,…,Sn;u1,…,un}, nếu n hữu hạn và Si là hữu hạn đối với mọi i thì tồn tại tít nhất một cân bằng NASH , có thể gắn với các chiến lược hỗn hợp