Bài giảng Các trò chơi tĩnh với thông tin đầy đủ

Bài giảng Các trò chơi tĩnh với thông tin đầy đủ nêu xét trò chơi với các tính chất sau: trò chơi được xét trong chương này có tính chất sau, các đấu thủ cùng đồng thời chọn hành động. Sau đó các đấu thủ nhận được thu hoạch phụ thuộc vào tổ hợp các hành động vừa chọn. Tong các trò chơi tĩnh đi cùng một lúc , ta chú ý đến trò chơi với thông tin đầy đủ.
Nội dung trích xuất từ tài liệu:
Bài giảng Các trò chơi tĩnh với thông tin đầy đủ CHƯƠNG HAICÁC TRÒ CHƠI TĨNH VỚI THÔNG TIN ĐẦY ĐỦ NỘI DUNG CƠ BẢN A. Xét trò chơi với các tính chất sau Trò chơi được xét trong chương này có tính chất sau:(1) các đấu thủ cùng đồng thời chọn hành động; (2) Sau đó các đấu thủ nhận được thu hoạch phụ thuộc vào tổ hợp các hành động vừa chọn. Tong các trò chơi tĩnh đi cùng một lúc , ta chú ý đến trò chơi với thông tin đầy đủB. Điểm qua những vấn đề cơ bản Mô tả một trò chơi Giải quyết các bài toán cơ bản của lý thuyết trò chơi Phát triển công cụ để sử dụng trong phân tích trò chơi tĩnh với thông tin đầy đủ Khái niệm chiến lược bị trội ngặt Cân bằng Nash LÝ THUYẾT CƠ BẢN TRÒ CHƠI DẠNG CHUẨN VÀ CÂN BẰNG NASH Biểu diễn dạng chuẩn của một trò chơi Định nghĩa: Biểu diễn dạng chuẩn của trò chơi là chỉ rõ(1) Các đấu thủ trong trò chơi(2) Các chiến lược sẵn có đối với mỗi đấu thủ và(3) Thu hoạch của mỗi đấu thủ nhận được đối với mỗi tổ hợp chiến lược mà các đấu thủ có thể chọn Hình thức biểu diễn dưới dạng chuẩn Biểu diễn dưới dạng ma trận là hình thức biểu diễn chủ yếu của trò chơi rời rạc dưới dạng chuẩn Phân tích biểu diễn dưới dạng ma trận (1) Biết được các đấu thủ (2) Biết các chiến lược sẵn có (3) Biết được các thu hoạch Các thí dụ Tù nhân 2 Không khai khaiTù nhân 1 Không khai -2 , -2 -10 , -1 Khai -1 , -10 -5 , -5 Định nghĩa hình thức Ta xét trò chơi có n đấu thủ. Mỗi đấu thủ có một tập hợp các chiến lược sẵn có ký hiệu là S. Si là tập hợp các chiến lược sẵn có của đấu thủ i. si là một phần tử của Si , nghĩa là si là một chiến lược của đấu thủ i. Gọi ui(s1,s2,…,sn ) là hàm thu hoạch của đấu thủ i khi các đấu thủ chọn các chiến lược (s1,s2, …sn). Định nghĩa: Biểu diễn dạng chuẩn của trò chơi §Þnh nghÜa: BiÓu diÔn d¹ng chuÈn cña mét trß ch¬i n ®Êu thñ chØ râ c¸c kh«ng gian chiÕn lîc S1,..., Sn cña c¸c ®Êu thñ vµ c¸c hµm thu ho¹ch u1,...,un cña hä. Ta ký hiÖu trß ch¬i nµy lµ G = {S1,..., Sn; u1,...,un}. Bài tập thực hành Biểu diễn dạng chuẩn của trò chơi: “ Cuộc chiến giữa hai giới”: P và C đang quyết định chọ tiêu khiển vào buổi tối: Họ chọ xem di xem ca nhạc hay đấu bóng. Nếu cả hai cùng xem ca nhạc thì thu hoạch của C là 2 và P là 1. Nếu cả hai đi xem đấu bóng thì thu hoạch của C là 1 và P là 2. Nếu đi xem các chương trình khác nhau thì thu hoạch của họ bằng không PHÉP KHỬ LẶP CÁC CHIẾN LƯỢC BỊ TRỘI NGẶT Định nghĩa : Chiến lược si là một chiến lược trội ngặt đối với người chơi i nếu nó duy nhất cực đại thu hoạch của người chơi i đối với bất kỳ chiến lược nào mà đối thủ của người chơi i có thể chơi. Hiểu thế nào định nghĩa này (giải thích) Thí dụ chiến lược trội ngặt Tù nhân 2 Không khai khaiTù nhân 1 Không khai -2 , -2 -10 , -1 Khai -1 , -10 -5 , -5 CHIẾN LƯỢC BỊ TRỘI NGẶT Định nghĩa trong trò chơi dạng chuẩn có n đấu thủ , trong đó đấu thủ i có tập hợp các chiến lược Si. Chiến lược si của người chơi i bị trội ngặt bởi si* , nếu mỗi tổ hợp của các chiến lược của các đấu thủ còn lại , thu hoạch của i do chọn si kém hơn hẳn khi chọ si* Hiểu thế nào định nghĩa nàyXét trò chơi ma trận:(1) Để xem đấu thủ hàng có chiến lược bị trội ngặt không thì ta so sánh giữa các thu hoạch ở hai hàng tương ứng(2) Để xem đấu thủ cột có chiến lược bị trội ngặt hay không thì ta so sánh các phần tử của các cột tương ứng. Định nghĩa hình thức §Þnh nghÜa: Trong trß ch¬i d¹ng chuÈn G = {S1,..., Sn; u1,...,un}, cho s’i vµ s”i lµ chiÕn lîc kh¶ thi (cã thÓ thùc hiÖn) ®èi víi ®Êu thñ i ( nghÜa lµ, s’i vµ s”i lµ phÇn tö cña Si ). ChiÕn lîc s’i lµ bÞ tréi ngÆt bëi chiÕn lîc s”i nÕu víi mçi tæ hîp kh¶ thi cña c¸c chiÕn lîc cña nh÷ng ®Êu thñ cßn l¹i, thu ho¹ch cña ®Êu thñ i b»ng viÖc chän chiÕn lîc s’i kÐm h¬n h¼n khi chän chiÕn lîc s”i: ui(s1,..., si-1, s’i , si+1,..., sn) < ui(s1,..., si-1, s”i , si+1,..., sn) ®èi víi mäi (s1,..., si-1, si+1,..., sn) cã thÓ ®îc x©y dùng tõ c¸c kh«ng gian chiÕn lîc S1,..., Si-1, Si+1,..., Sn cña nh÷ng ®Êu thñ cßn l¹i. Thuật toán (1) Có thể thực hiện tìm chiến lược bị trội ngặt của đấu thủ hàng hoặc cột. Nếu phát hiện chiến lược bị trội ngặt ở hàng (cột ) thì ta loại hàng (cột) tương ứng. (2) Sau khi loại hàng (cột) trò chơi được thu gọn và quá trình lại lặp lại trên trò chơi này cho đến khi kết thúc Thí dụ và phân tích cách giảiXét trò chơi trừu tượng sau: Đấu thủ 2 Trước G ...