Bài giảng Toán rời rạc - Chương 1: Lý thuyết trò chơi

Chương 1 LÝ THUYẾT TRÒ CHƠI 10/6/2012 1MaMH: C02012 Chương 1: Lý thuyết trò chơi 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 2MaMH: C02012 Chương 1: Lý thuyết trò chơi 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 3MaMH: C02012 Chương 1: Lý thuyết trò chơi 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 4MaMH: C02012 Chương 1: Lý thuyết trò chơi 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 5MaMH: C02012 Chương 1: Lý thuyết trò chơi TRÒ CHƠI 2 NGƯỜI TỔNG 0 - Giả sử là thu hoạch của người chơi trong đó có k người tham gia. Khi đó, nếu thì trò chơi này được gọi là trò ip , 1,...,iP i k= 1 0 k i i p = =∑ 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 6MaMH: C02012 Chương 1: Lý thuyết trò chơi 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ấp là thu hoạch của P1. Và của P2 là –A. 10/6/2012 7MaMH: C02012 Chương 1: Lý thuyết trò chơi m n× TRÒ CHƠI 2 NGƯỜI TỔNG 0 11 1 1 1( ) j n i ij inij a a a a a aA a        = =     ⋯ ⋯ ⋮ ⋯ ⋮ 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ận (P2 trả ). 10/6/2012 8MaMH: C02012 Chương 1: Lý thuyết trò chơi 1m mj mna a a     ija ija TRÒ CHƠI 2 NGƯỜI TỔNG 0 • Nếu ma trận thỏa mãn thì ma trận này được nói là có điểm yên ngựa tại (r,s). ( )ijA a= minmax maxminij ij rsj ji ia a a= = • 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 9MaMH: C02012 Chương 1: Lý thuyết trò chơi CHIẾN LƯỢC HỖN HỢP • với được gọi là chiến lược hỗn hợp. Với xi là xác suất mà người chơi chọn chiến lược thứ i. 1{ ,..., }mx x x= 1 0, 1,..., , 1 m i i i x i m x = ≥ = =∑ 10/6/2012 10MaMH: C02012 Chương 1: Lý thuyết trò chơi CHIẾN LƯỢC THUẦN TÚY Chiến lược hỗn hợp trong đó , 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. ix ξ= 1iξ = 10/6/2012 11MaMH: C02012 Chương 1: Lý thuyết trò chơi HÀM THU HOẠCH Gọi tập chiến lược của P1, 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à: { }X x= { }Y y= m n ∑∑ 10/6/2012 12MaMH: C02012 Chương 1: Lý thuyết trò chơi 1 1 ( , ) Ti ij j i j A x y x a y xA y = = = = ĐỊNH LÝ MINIMAX Đặt là giá trị thu được của P1, là giá trị thu được của P2. : maxmin ( , )I y Yx XV A x y∈∈= : minmax ( , )II y Y x XV A x y∈ ∈= Ta có: Định lý Minimax 10/6/2012 13MaMH: C02012 Chương 1: Lý thuyết trò chơi .I IIV V= maxmin ; minmaxI i ij II i ijj y Yx X iV x a V y a∈∈= = TÍNH TRỘI • Trong ma trận A, ta nói hàng i trội hàng k nếu , : ij kj ij ik a a j j a a ≥ ∀ ∃ > • Trong ma trận A, ta nói cột j trội cột l nếu → Áp dụng tính trội để rút ngắn cỡ của ma trận A. 10/6/2012 14MaMH: C02012 Chương 1: Lý thuyết trò chơi , : . ij il ij il a a i i a a ≤ ∀ ∃ < 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) Đặt a b A c d   =     r a d b c= + − − Giá trị của trò chơi: Các chiến lược tối ưu: 10/6/2012 15MaMH: C02012 Chương 1: Lý thuyết trò chơi ad bc v r − = , ; , .d c a b d b a cX Y r r r r − − − −    = =        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 1 1 2 2 1 2: ( 1)j j jz a x a x x x= + + = hay - Chọn là đường (gấp khúc) nằm dưới cùng trong hình vẽ. Sau đó, lấy tức là điểm (đoạn) cao nhất trên đường (gấp khúc) này. 10/6/2012 16MaMH: C02012 Chương 1: Lý thuyết trò chơi 2 1 2 1 1( ) , 0 1.j j j jz a a a x x= + − ≤ ≤ min jj z 1 maxmin jjx z 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 ưu cho , ta xem điểm cao nhất nhận được là giao của 2 đường z nào, chẳng hạn đó là đường j’ và j’’ , thì ta sẽ có 1 2( , ,..., )nY y y y= j 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 được . - Vậy, ngoại trừ hai giá trị 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 17MaMH: C02012 Chương 1: Lý thuyết trò chơi ' '' ,j jy y ' '' ,j jy y 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 18MaMH: C02012 Chương 1: Lý thuyết trò chơi DẠNG QUY HOẠCH TUYẾN TÍNH Bài toán đối với P1 , 1 1 1 2 maxmin ... 1 m i ijj nx X i m x a x x x ≤ ≤∈ = + + + =  ∑ 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 : 10/6/2012 19MaMH: C02012 Chương 1: Lý thuyết trò chơi 0, 1,...,ix i m≥ = 1 min i ijj np x a≤ ≤≤ DẠNG QUY HOẠCH TUYẾN TÍNH Bài toán trở thành: Tìm p, xi sao cho 1 1 max m i i i p p x a =  ≤  ∑ 10/6/2012 20MaMH: C02012 Chương 1: Lý thuyết trò chơi 1 1 2 (1) ... 1 0, 1,..., m i in i m i p x a x x x x i m =    ≤   + + + =  ≥ =  ∑ ⋮ 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 1 1 min n j j j w w a y =  ≥   ∑ ⋮ 10/6/2012 21MaMH: C02012 Chương 1: Lý thuyết trò chơi 1 1 1 2 (2) ... 1 0, 1,..., n j j j n j w a y y y y y j n =   ≥   + + + =  ≥ =   ∑ 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 22MaMH: C02012 Chương 1: Lý thuyết trò chơi