Bài tập nhóm: Cân bằng Nash chiến lược hỗn hợp

Nội dung text: Bài tập nhóm: Cân bằng Nash chiến lược hỗn hợp

1. GAME THEORY 1
2. CÂN BẰNG NASH CHIẾN LƯỢC HỖN HỢP Sự tồn tại của cân bằng Nash. Nhóm 7 1. Nguyễn Quang Tuấn 2. Đỗ Minh Tùng 3. Phạm Xuân Đồng 4. Hoàng Thị Vân 2
3. Nội dung thảo luận 1. Giới thiệu chung 2. Sự tồn tại chiến lược cân bằng Nash 3. Bài toán 2.6 3
4. 1.Giới thiệu chung 1. Nhà toán học Nash. • Người Mỹ (1928) • Chuyên ngành LTTC và hình học vi phân. • Năm 1944 đạt giải nobel về kinh tế. 2. Cân bằng Nash (NE). • Trò chơi dạng chuẩn: G={S,u}. • Vectơ chiến lược (s*1, ,s*n) là 1 cân bằng Nash nêu : ui(s*i, s*-i) ≥ (si, s*-i) • Hay s*i là nghiệm của bài toán: (s*i s*i-1,si,s*i+1 sn) 4
5. 2.Sự Tồn Tại Cân Bằng Nash • Nội Dung A. Sự tồn tại cân bằng Nash chiến lược hỗn hợp B. Trình bày ví dụ 2.6
6. A-Sự tồn tại cân bằng nash chiến lược hỗn hợp • Ví dụ về thiết lập bài toán để tìm chiến lược cân bằng • Bài toán tổng quát • Định nghĩa 6
7. vVí dụ: Trò chơi 2 đấu thủ +Giả sử có 2 đấu thủ: Đấu thủ cột Thu hoạch của mỗi đối thủ được cho ở bảng: Đấu L R + Giả sử (pt,pb) là xác suất để đối thủ hàng thủ T 2,1 0,0 hàng chơi chiến lược (T,B);(pl,pr) là xác suất để B 0,0 1,2 đối thủ cột chơi chiến lược (L,R). => Lợi ích kỳ vọng của đấu thủ hàng là: pt*[pl*2+pr*0]+pb*[pl*0+pr*1] Lợi ích kỳ vọng của đấu thủ cột là : pl*[pt*1+pb*0]+pr*[pt*0+pb*2] =>Bài toán tìm lợi ích cực đại lợi ích kỳ vọng của đấu thủ hàng: Max pt{pl*2+pr*0}+pb{pl*0+pr*1} pt,pb với ràng buộc: pt+pb=1; pt>=0,pb>=0 Với đấu thủ cột: Max(pl,pr) pt*{pt*1+pb*0)+pr*{pt*0+pb*2) với ràng buộc pl+pr=1; pl.pr>=0 Giải ra ta được pl=1/3, pr=2/3 và pb=1/3 pt=2/3 7
8. vBài toán tổng quát • Kí hiệu J là số chiến lược thuần túy trong và K là số chiến lược thuần túy trong • Ta viết ; và sd , để kí hiệu các chiến lược thuần túy tùy ý trong và • Nếu đấu thủ 1 tin rằng đấu thủ 2 sẽ chơi các chiến lược với các xác suất => thu hoạch kỳ vọng của đấu thủ 1 với chiến lược thuần túy là: và thu hoạch kỳ vọng của đấu thủ 1 chơi chiến lược hỗn hợp là : • Để chiến lược hỗn hợp là phàn ứng tốt nhất của đấu thủ 1 đối với chiến lược hỗn hợp của đấu thủ 2 thì phải có >0 chỉ nếu ≥ với mọi trong 8
9. Bài toán tổng quát (tiếp) • Làm tương tự đấu thủ 2 như đấu thủ 1 • là cân bằng Nash chiến lược hỗn hợp nếu chúng là nghiệm của bài toán : hay 0≤ 9
10. vĐịnh nghĩa : Cân bằng nash chiến lược hỗn hợp • Trong trò chơi dạng chuẩn của 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 của đối thủ kia. 10
11. 3-Ví dụ 2.6 • Xét bài toán 2 người chơi, mỗi người 2 chiến lược thuần túy Thuần Túy (2) Xét các thu hoạch của đấu thủ 1 ở bảng: T P • Chiến lược hỗn hợp L x,? y,? của 1 với (L,X) là (r,1-r) (1) X z,? w ,? của 2 với (T,P) là (q, 1-q) • Xét 4 trường hợp Hỗn Hợp (2) I. x>z và y>w T(q) P(1-q) II. x z và y w 11
12. I. TH1 x>z và y> w +Rõ ràng L phản ứng tốt nhất với mọi q, tức là lên trội ngặt so với xuống. +Ta có thể biểu diễn các hàm phản ứng tốt nhất của (i) bằng đồ thị: r L r*(q) (i) q X T P 12
13. II- TH2: x<z và y<w • TH này X phản ứng tốt nhất với mọi q • Đồ thị miêu tả : r L r*(q) (ii) q X q T P 13
14. Ta có thu hoạch kì vọng của (1). Thu hoạch kì vọng khi chọn L: q.x + (1 - q).y Thu hoạch kì vọng khi chọn X: q.z + (1 - q).w • Gọi A là chênh lệch của thu hoạch kì vọng của (1). A = q.x + (1 - q).y – q.z – (1 - q).w = q.[(x - z) + (w - y)] + (y - w) Đặt Vậy 14
15. TH3: x>z và y q’ thì L là tốt nhất; q<q’ thì xuống là tốt nhất;q=q’thì bàng quan. • Đồ thị miêu tả: L r (q) (iii) X q’ 15 T P
16. TH4:x w • Trường hợp này tương tự th3, xét mức q’= (w-y)/((x-z)+(w-y)) Với q q’ thì X phản ứng tốt nhất; q=q’ thì bàng quan. • Đồ thị miêu tả: r L r*(q) X (iv) q T q’ P 16
17. Th đặc biệt :w=y thì q’=0; x=z thì q’=1 • Đồ thị: r L L y=w q x=z X X q’=0 P P T q’=1 T 17
18. • Tương tự, Xét thu hoach của người chơi thứ 2 • Cũng như trên mỗi người chơi Thuần túy (2) đều có 2 chiến lược thuần túy T P (1) L ?,x’ ?,y’ và chiến lược hỗn hợp của: X ?,z’ ?,w’ (1) với (L,X) là (r,1-r) (2) với (T,P) là (q,1-q) Hỗn hợp (2) • Tương tự trên, ta cũng xét 4 T(q) P(1-q) trường hợp: (1) L(r) ?,x’ ?,y’ ü x’>y’ và z’>w’ X(1-r) ?,z’ ?,w’ ü x’ y’ và z’ w’ 18
19. Ta có các đồ thị biểu diễn các TH trên như sau: r r L L q*(r ) i q (ii) q X X T P T P r r L L (iv) (iii) q q X X T P T P 19
20. Biện luận điểm cân bằng Nash • Ta cho bất kỳ 1 trong 4 hàm phản ứng tốt nhất của đấu thủ 1( r*(q)) kết hợp với bất kỳ 1 trong 4 hàm phản ứng tốt nhất của đấu thủ 2 ( q*(r)). • Ta thấy cặp phản ứng tốt nhất này cho ít nhất 1 giao điểm, do đó trò chơi có ít nhất 1 cân bằng Nash. • Kiểm tra 16 cặp phản ứng có thể có ,ta có thể phân ra làm các TH để xét cân bằng Nash: 1. Một cân bằng Nash thuần túy: Điểm NE 20
21. 2. Một cân bằng Nash hỗn hợp (NE) 1 điểm NE hỗn hợp 3. Hai NE thuần, một NE hỗn hợp 21
22. 4. Một NE thuần, một tập NE hỗn hợp: NE thuần 1 tập NE hỗn hợp 5.Hai NE thuần, một tập NE hỗn hợp: 22
23. 4- Vài mẩu truyện vui-thảo luận • 1-Đi thẳng vào tù (Câu chuyện 2 người tù) Người nhạc trưởng dàn giao hưởng ở Liên Xô (vào thời kỳ Stalin) đang trên tàu đến nơi biểu diễn tiếp theo của mình và ông ta chăm chú nhìn vào bản nhạc mà ông ta sẽ chỉ huy dàn nhạc biểu diễn vào tối hôm đó. Hai sĩ quan KGB nhìn thấy ông ta đang đọc và họ cho rằng các nốt nhạc mang một mật mã bí mật nào đó nên đã bắt ông ta như một gián điệp. Ông ta cố phản đối, nói rằng bản nhạc đó là bản concerto dành cho violon của Traicôpxki, nhưng vô ích. Vào ngày thứ hai trong tù, người thẩm vấn với một vẻ tự mãn bước vào và nói với ông ta: “Tốt nhất là hãy khai tất cả đi. Chúng ta đã bắt được bạn của mày, Traicôpxki, và hắn ta đã khai rồi đó” • 2- Thảo luận tình huống : Đỏ tôi thắng, đen anh thua 23
24. Vào cuối khóa học, Barry đã kỷ niệm ngày+ ra trường tại một trong các dạ tiệc khiêu vũ của trường tổng hợp Cambridge. Một phần của buổi dạ tiệc là casinô. Mỗi người chơi được tặng cho một số thẻ chơi tương đương 20 đôla và cuối buổi người nào tích lũy được một số lượng thẻ có giá trị lớn nhất sẽ được tặng vé miễn phí dạ tiệc năm sau. Khi đến vòng quay cuối cùng của bàn rulô, một sự may mắn tình cờ đã khiến Barry dẫn đầu với số thẻ có tổng trị giá 700 đôla, người tiếp theo là một phụ nữ Anh với 300 đôla. Số còn lại gần như đã bỏ cuộc. Ngay trước khi vòng quay cuối bắt đầu, người phụ nữ Anh nọ đề nghị chia đôi chiếc vé dạ tiệc năm sau nhưng Barry đã từ chối. Với việc đang dẫn đầu vói khoảng cách bỏ xa như vậy, chẳng có lý do gì để phải chia đôi giải thưởng Để hiểu rõ hơn về bước chiến lược tiếp theo, chúng tôi sẽ giải thích qua về quy tắc chơi trò quay rulô. Chiến thắng trong trò chơi này phụ thuộc vào vị trí quả bóng sẽ lăn vào khi vòng bánh xe tròn dừng lại. Thường sẽ có các số từ 0 đến 36 trên vòng tròn quay. Khi quả bóng lăn vào số (0), nhà cái sẽ thắng. Cách đặt cược an toàn nhất trong trò rulô là đánh cược vào số chẵn hoặc lẻ (được biểu thị bằng màu đen hoặc đỏ). Đánh cược kiểu này sẽ thu về một số tiến chẵn: cứ 1 đôla đánh cược thắng sẽ thu về 2 đô la trong khi cơ hội để thắng là 18/37. Ngay cả khi đánh cược toàn bộ số tiền mình có thì người phụ nữ cũng vẫn không thể thắng theo cách này; do vậy cô ta buộc phải chơi một trò chơi rủi ro hơn là đặt cược toàn bộ bộ số tiền của mình vào các bội số của 3. Chơi theo cách này, người phụ nữ sẽ nhận được tiền gấp ba nếu thắng (số tiền 300 đô la sẽ trở thành 900 đô la). Tuy nhiên cơ hội thắng chỉ còn 12/37. Người phụ nữ đã đặt tiền của mình lên bàn như vậy, vào thời điểm này không còn cơ hội để rút lại nữa. Barry sẽ phải làm gì lúc này? 24
25. Bài thuyết trình của nhóm đến đây là kết thúc! Cám ơn mọi người đã lắng nghe! 25