Bài giảng Tối ưu - Chương 1: Lý thuyết trò chơi

Nội dung text: Bài giảng Tối ưu - Chương 1: Lý thuyết trò chơi

1. Chương 1 LÝ THUYẾT TRÒ CHƠI 10/6/2012 MaMH: C02012 Ch ươ ng 1: Lý thuy ết trò ch ơi 1
2. NỘI DUNG 1. Gi ới thi ệu bài toán tổng quát 2. Trò ch ơi 2 ng ười tổng không 3. Chi ến lược thu ần túy, chi ến lược hỗn hợp 4. Lý thuy ết trò ch ơi dưới dạng QHTT 10/6/2012 MaMH: C02012 Ch ươ ng 1: Lý thuy ết trò ch ơi 2
3. GI ỚI THI ỆU BÀI TOÁN TỔNG QUÁT 1. Gi ới thi ệu −Trò ch ơi th ường có ít hai ng ười ch ơi và dựa vào một quy lu ật đã được đưa ra tr ước khi bắt đầ u trò ch ơi. Cu ối trò ch ơi, mỗi ng ười ch ơi sẽ nh ận được một thu ho ạch (payoff) nào đó, tùy theo th ỏa thu ận gi ữa nh ững ng ười ch ơi, ví dụ là ti ền hay hình th ức ph ạt nào đấ y. −Trò ch ơi có th ể mang tính ng ẫu nhiên (ném xúc xắc, chia bài ); trò ch ơi dùng kỹ thu ật, kỹ năng (cờ tướng, cờ ca rô ) 10/6/2012 MaMH: C02012 Ch ươ ng 1: Lý thuy ết trò ch ơi 3
4. GI ỚI THI ỆU BÀI TOÁN TỔNG QUÁT −Trong trò ch ơi, ng ười ta th ường xét đế n 3 yếu tố: chi ến lược, quy lu ật của trò ch ơi và thu ho ạch. −Lý thuy ết trò ch ơi nghiên cứu các tình hu ống chi ến lược trong đó các đố i th ủ (ng ười ch ơi) lựa ch ọn các hành độ ng khác nhau để cố gắng làm tối đa các kết qu ả nh ận được. 10/6/2012 MaMH: C02012 Ch ươ ng 1: Lý thuy ết trò ch ơi 4
5. GI ỚI THI ỆU BÀI TOÁN TỔNG QUÁT − Lý thuy ết trò ch ơi được ứng dụng trong nhi ều lĩnh vực: • Kinh tế và kinh doanh: đấ u giá, mặc cả • Sinh học: ph ần lợi của trò ch ơi là sự thích nghi, ứng dụng vào vi ệc gi ải thích sự ti ến hóa (và bền vững) của tỉ lệ gi ới tính gần 1 : 1. • Khoa học máy tính và logic • Chính tr ị học • Tri ết học 10/6/2012 MaMH: C02012 Ch ươ ng 1: Lý thuy ết trò ch ơi 5
6. TRÒ CHƠI 2 NGƯỜI TỔNG 0 = - Gi ả sử pi là thu ho ạch của ng ười ch ơi Pi , i 1, , k trong đó có k ng ười tham gia. k = Khi đó, nếu∑ pi 0 thìtròch ơi này được gọi là trò i =1 ch ơi k ng ười tổng 0. - Tr ường hợp k = 2 , ta có trò ch ơi 2 ng ười tổng 0. 10/6/2012 MaMH: C02012 Ch ươ ng 1: Lý thuy ết trò ch ơi 6
7. TRÒ CHƠI 2 NGƯỜI TỔNG 0 Dạng ma tr ận - Ng ười ch ơi th ứ nh ất (P1) có m chi ến lược, được bi ểu di ễn là các hàng của ma tr ận. - Ng ười ch ơi th ứ hai (P2) có n chi ến lược, được bi ểu di ễn là các cột của ma tr ận. × - Ta bi ểu di ễn ma tr ận A = ( aij ) cấpm n làthu ho ạch của P1. Và của P2 là –A. 10/6/2012 MaMH: C02012 Ch ươ ng 1: Lý thuy ết trò ch ơi 7
8. TRÒ CHƠI 2 NGƯỜI TỔNG 0 a⋯ a ⋯ a  11 1j 1 n  ⋮  A=( a ) = a⋯ a a  ij i1 ij in  ⋮    am1 a mj a mn  P1 ch ọn chi ến lược i , P2 ch ọn chi ến lược j và ng ười này không bi ết sự lựa ch ọn của ng ười kia. Khi đó, P1 sẽ nh ậnaij (P2 tr ả aij ). 10/6/2012 MaMH: C02012 Ch ươ ng 1: Lý thuy ết trò ch ơi 8
9. TRÒ CHƠI 2 NGƯỜI TỔNG 0 = • Nếu ma tr ậnA( a ij ) th ỏa mãn = = minmaxaij maxmin a ij a rs ji i j thì ma tr ận này được nói là có điểm yên ng ựa tại (r,s ). • Khi đó, r được gọi là chi ến lược tối ưu của P1 , s được gọi là chi ến lược tối ưu của P2. • ars được gọi là giá tr ị của trò ch ơi, kí hi ệu là v. 10/6/2012 MaMH: C02012 Ch ươ ng 1: Lý thuy ết trò ch ơi 9
10. CHI ẾN LƯỢC HỖN HỢP m = ≥ = = •x{ x1 , , x m } với xi0, i 1, , mx ,∑ i 1 được gọi là chi ến lược hỗn hợp. i =1 Với xi là xác su ất mà ng ười ch ơi ch ọn chi ến lược th ứ i. 10/6/2012 MaMH: C02012 Ch ươ ng 1: Lý thuy ết trò ch ơi 10
11. CHI ẾN LƯỢC THUẦN TÚY = ξ ξ = Chi ến lược hỗn hợpx i trong đói 1 , nh ững thành ph ần còn lại bằng 0 được gọi là một chi ến lược thu ần túy . 10/6/2012 MaMH: C02012 Ch ươ ng 1: Lý thuy ết trò ch ơi 11
12. HÀM THU HOẠCH = GọiX{ x } tập chi ến lược của P1, = Y{ y } tập chi ến lược của P2 . Khi đó, nếu P1 ch ọn chi ến lược hỗn hợp x, P2 ch ọn chi ến lược hỗn hợp y, thì hàm thu ho ạch là: m n = = T Axy( , ) ∑∑ xayi ij j xAy i=1 j = 1 10/6/2012 MaMH: C02012 Ch ươ ng 1: Lý thuy ết trò ch ơi 12
13. ĐỊ NH LÝ MINIMAX Đặ t = VI : maxmin Axy ( , ) là giá tr ị thu được của P1, x∈ X y∈ Y = VII : minmax Axy ( , ) là giá tr ị thu được của P2. y∈ Y x∈ X = = Ta có: VImaxmin x i a ij ; V II minmax y i a ij x∈ X j y∈ Y i Đị nh lý Minimax = VVI II . 10/6/2012 MaMH: C02012 Ch ươ ng 1: Lý thuy ết trò ch ơi 13
14. TÍNH TRỘI • Trong ma tr ận A, ta nói hàng i tr ội hàng k nếu ≥ ∀ aij a kj , j  ∃ >  j: aij a ik • Trong ma tr ận A, ta nói cột j tr ội cột l nếu ≤ ∀ aij a il , i  ∃ <  i: aij a il . → Áp dụng tính tr ội để rút ng ắn cỡ của ma tr ận A. 10/6/2012 MaMH: C02012 Ch ươ ng 1: Lý thuy ết trò ch ơi 14
15. CÁCH GI ẢI TRÒ CHƠI 2 x 2 Xét ma tr ận thu ho ạch (không có điểm yên ng ựa) a b  A =   c d  Đặ t r= ad + − bc − Giá tr ị của trò ch ơi: ad− bc v = r Các chi ến lược tối ưu: dcab−−  dbac −−  XY=,;  = ,.  rr  rr  10/6/2012 MaMH: C02012 Ch ươ ng 1: Lý thuy ết trò ch ơi 15
16. CÁCH GI ẢI TRÒ CHƠI 2 x n Ma tr ận thu ho ạch có 2 hàng, n cột. -Vẽ các đường th ẳng = + += zj: ax11 j axx 22 j ( 1 x 2 1) =+− ≤≤ hay zaj2 j( aax 121 j j ),0 x 1 1. - Ch ọnmin z j là đường (gấp khúc) nằm dưới cùng j trong hình vẽ. Sau đó, lấymaxmin zj tức là điểm x j (đoạn) cao nh ất trên đường (g1 ấp khúc) này. 10/6/2012 MaMH: C02012 Ch ươ ng 1: Lý thuy ết trò ch ơi 16
17. CÁCH GI ẢI TRÒ CHƠI 2 x n (tt) - Giao điểm cho ta nghi ệm của bài toán. Cụ th ể, xác đị nh được x1 , v và x2 . = - Để tìm chi ến lược tối ưuchoY( yy1 , 2 , , y n ) ,ta xem điểm cao nh ất nh ận được là giao của 2 đường ’ ’’ zj nào , ch ẳng hạn đó là đường j và j , thì ta sẽ có ma tr ận cấp 2 x 2 là hai cột tương ứng j’ và j’’ của ma tr ận A. Gi ải trò ch ơi với ma tr ận này, ta sẽ nh ận y, y đượcj' . j '' y, y - Vậy, ngo ại tr ừ hai giá tr ị j' j '' vừa tính được, các thành ph ần còn lại của Y sẽ có giá tr ị là 0. 10/6/2012 MaMH: C02012 Ch ươ ng 1: Lý thuy ết trò ch ơi 17
18. TRÒ CHƠI m x 2 - Ma tr ận thu ho ạch có m hàng, 2 cột. → Cách gi ải tương tự trò ch ơi 2 x n. - Đố i với trò ch ơi m x n, ta sẽ dùng tính tr ội để đưa về các dạng trò ch ơi 2 x 2; 2 x n hay m x 2 để gi ải. 10/6/2012 MaMH: C02012 Ch ươ ng 1: Lý thuy ết trò ch ơi 18
19. DẠNG QUY HOẠCH TUYẾN TÍNH Bài toán đố i với P1 , m maxmin∑ xi a ij x∈ X 1≤j ≤ n i =1 x+ x ++ x = 1  1 2 m ≥ = xi 0, i 1, , m Vì hàm mục tiêu ch ưa ph ải hàm tuy ến tính, nên ta ≤ thêm một bi ến mới p : pmin xi a ij 1≤j ≤ n 10/6/2012 MaMH: C02012 Ch ươ ng 1: Lý thuy ết trò ch ơi 19
20. DẠNG QUY HOẠCH TUYẾN TÍNH Bài toán tr ở thành: Tìm p, xi sao cho max p  m ≤ p∑ xi a i 1  i =1 ⋮  m  ≤ p∑ xi a in (1)  i =1 x+ x ++ x = 1  1 2 m ≥ = xi 0, i 1, , m  10/6/2012 MaMH: C02012 Ch ươ ng 1: Lý thuy ết trò ch ơi 20
21. DẠNG QUY HOẠCH TUYẾN TÍNH Tương tự, bài toán của P2 : Tìm w, yj sao cho min w  n ≥ w∑ a1j y j  j =1 ⋮  n  ≥ w∑ a1j y j (2)  j =1 y+ y ++ y = 1  1 2 n ≥ = yj 0, j 1, , n   10/6/2012 MaMH: C02012 Ch ươ ng 1: Lý thuy ết trò ch ơi 21
22. DẠNG QUY HOẠCH TUYẾN TÍNH (1), (2) có dạng tuy ến tính. → Dùng ph ương pháp đơn hình để gi ải. 10/6/2012 MaMH: C02012 Ch ươ ng 1: Lý thuy ết trò ch ơi 22