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

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

Thêm vào BST

Báo xấu

115
lượt xem 12
download

Download Vui lòng tải xuống để xem tài liệu đầ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 đủ.

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 Các trò chơi tĩnh với thông tin đầy đủ

CHƯƠNG HAI CÁ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 khai Tù 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 khai Tù 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ày Xé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ải Xét trò chơi trừu tượng sau: Đấu thủ 2 Trước Giữa Phải Đấu thủ 1 Trên 1,0 1,2 0,2 Dưới 0,3 0,2 1,0
Giải thích thuật toán- Đấu thủ 1 nghĩ  §Êu thñ 1 cã hai chiÕn lîc cßn ®Êu thñ 2 cã ba: S1 = {Lªn, Xuèng} vµ S2 = {Tr¸i, Gi÷a, Ph¶i}. Víi ®Êu thñ 1, c¶ Lªn hay Xuèng ®Òu kh«ng bÞ tréi ngÆt: Lªn tèt h¬n Xuèng nÕu ®Êu thñ 2 ch¬i níc Tr¸i (v× 1>0), nhng Xuèng l¹i tèt h¬n Lªn nÕu ®Êu thñ 2 ch¬i níc Ph¶i (v× 2>0).  Víi ®Êu thñ 2, dï c¸ch g× th× chiÕn lîc Ph¶i còng bÞ tréi ngÆt bëi chiÕn kîc Gi÷a (v× 2>1 vµ 1>0), bëi vËy mét ®Êu thñ 2 s¸ng suèt sÏ kh«ng ch¬i níc Ph¶i.
Giải thích thuật toán  Nh vËy, nÕu ®Êu thñ 1 biÕt ®Êu thñ 2 lµ ngêi s¸ng suèt th× ®Êu thñ 1 cã thÓ lo¹i chiÕn lîc Ph¶i ra khái kh«ng gian chiÕn lîc cña ®Êu thñ 2.  §iÒu ®ã cã nghÜa lµ, nÕu ®Êu thñ 1 biÕt ®Êu thñ 2 lµ ngêi s¸ng suèt th× ®Êu thñ 1 cã thÓ ch¬i trß ch¬i trong h×nh 1 nh thÓ lµ ch¬i trß ch¬i trong h×nh 2.
Trò chơi rút gọn Đấu thủ 2 Tr¸i Giữa ĐÊu thñ 1 Lªn 1,0 1,2 Xuèng 0,3 0,1
Đấu thủ 2 nghĩ  Trong H×nh 2, ®èi víi ®Êu thñ 1, chiÕn lîc Xuèng b©y giê l¹i bÞ tréi ngÆt bëi chiÕn lîc Lªn, v× thÕ nÕu ®Êu thñ 1 s¸ng suèt (vµ ®Êu thñ 1 biÕt ®Êu thñ 2 lµ ngêi s¸ng suèt, do ®ã trß ch¬i trong h×nh 2 lµ thÝch øng) th× ®Êu thñ 1 sÏ kh«ng ch¬i chiÕn lîc Xuèng.  Nh vËy, nÕu ®Êu thñ 2 biÕt ®Êu thñ 1 lµ ngêi s¸ng suèt, vµ ®Êu thñ 2 biÕt r»ng ®Êu thñ 1 biÕt ®Êu thñ 2 lµ ngêi s¸ng suèt (do ®ã ®Êu thñ 2 biÕt r»ng h×nh 2 lµ thÝch øng), th× ®Êu thñ 2 cã thÓ lo¹i bá chiÕn lîc Xuèng ra khái kh«ng gian chiÕn lîc cña ®Êu thñ 1, cßn l¹i trß ch¬i nh trong h×nh 3.