Tài liệu Lý thuyết trò chơi và ứng dụng trong kinh tế

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ĐÀM THỊ DƯỠNG LÝ THUYẾT TRÒ CHƠI VÀ ỨNG DỤNG TRONG KINH TẾ LUẬN VĂN THẠC SĨ TOÁN HỌC Thái Nguyên - 2016 ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ĐÀM THỊ DƯỠNG LÝ THUYẾT TRÒ CHƠI VÀ ỨNG DỤNG TRONG KINH TẾ LUẬN VĂN THẠC SĨ TOÁN HỌC Chuyên ngành: Toán ứng dụng Mã số: 60 46 01 12 NGƯỜI HƯỚNG DẪN KHOA HỌC TS. NGUYỄN VĂN MINH Thái Nguyên - 2016 i Mục lục Lời cảm ơn iv Mở đầu 1 Lý 1.1 1.2 1.3 thuyết trò chơi Khái niệm mở đầu . . . . . . . . . . . . . . . . . . . . Trò chơi ma trận . . . . . . . . . . . . . . . . . . . . Chiến lược đơn trong trò chơi ma trận . . . . . . . . . 1.3.1 Chiến lược maximin của người chơi thứ nhất . 1.3.2 Chiến lược minimax của người chơi thứ hai . . 1.4 Các chiến lược hỗn hợp trong trò chơi ma trận . . . . 1.4.1 Phần thắng trung bình của người chơi thứ nhất 1.4.2 Nghiệm của trò chơi trong chiến lược hỗn hợp . 1.4.3 Chiến lược thừa . . . . . . . . . . . . . . . . . 1.4.4 Phương pháp Quy hoạch tuyến tính . . . . . . 1.5 Trò chơi ma trận với tổng bất kỳ . . . . . . . . . . . . 1.5.1 Khái niệm mở đầu . . . . . . . . . . . . . . . . 1.5.2 Cân bằng Nash trong chiến lược đơn . . . . . . 1.5.3 Cân bằng Nash trong chiến lược hỗn hợp . . . 1.5.4 Chiến lược maximin . . . . . . . . . . . . . . . 1.5.5 Chiến lược thừa trong trò chơi ma trận kép . . 1.5.6 Trò chơi hợp tác . . . . . . . . . . . . . . . . . 1 . . . . . . . . . . . . . . . . . 3 3 6 9 9 10 11 13 14 16 19 21 21 22 23 25 26 27 2 Các thí dụ và ứng dụng của Lý thuyết trò chơi 2.1 Các thí dụ . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.1 Ma trận có điểm yên ngựa . . . . . . . . . . . . . . 2.1.2 Ma trận không có điểm yên ngựa . . . . . . . . . . . 31 31 31 32 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii 2.2 Các ứng dụng của lý thuyết trò chơi . . . . . . . . . . . . 2.2.1 Khó tăng giá trong thị trường cạnh tranh hoàn hảo 2.2.2 Hiện tượng trong thế giới động vật . . . . . . . . . 2.2.3 Giải trừ vũ khí hạt nhân . . . . . . . . . . . . . . 2.2.4 Tình thế lưỡng nan của hai nghi can . . . . . . . . 2.2.5 Ứng dụng của trò chơi hợp tác . . . . . . . . . . . . . . . . . 41 41 42 43 45 46 Kết luận 50 Tài liệu tham khảo 51 iii Danh sách hình vẽ 1.1 Minh họa ví dụ 1.11 . . . . . . . . . . . . . . . . . . . . . . 18 1.2 Trò chơi hợp tác . . . . . . . . . . . . . . . . . . . . . . . . 30 2.1 Ví dụ 2.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 2.2 Minh họa ví dụ 2.4 . . . . . . . . . . . . . . . . . . . . . . 36 iv Lời cảm ơn Luận văn này được thực hiện tại Trường Đại học Khoa học - Đại học Thái Nguyên và hoàn thành dưới sự hướng dẫn của thầy TS. Nguyễn Văn Minh. Tôi xin được bày tỏ lòng biết ơn chân thành và sâu sắc tới người thầy, người đã dìu dắt tôi từ buổi đầu tiên cho đến khi hoàn thành luận văn. Tác giả xin trân trọng cảm ơn Ban Giám hiệu Trường Đại học Khoa học - Đại học Thái Nguyên, Ban Chủ nhiệm Khoa Toán-Tin, cùng các thầy, các cô đã tham gia giảng dạy, đã tạo mọi điều kiện tốt nhất để tôi học tập và nghiên cứu. Nhân đây tôi xin có lời cảm ơn tới tập thể lớp cao học Toán K8C (khóa 2014-2016) đã động viên và giúp đỡ tôi rất nhiều trong quá trình học tập, nghiên cứu. Tôi xin chân thành cảm ơn gia đình và bạn bè. Đã động viên tôi về tinh thần và giúp đỡ về vật chất kể từ khi ôn thi đến ngày hôm nay. Thái Nguyên, tháng 11 năm 2016 Đàm Thị Dưỡng Học viên Cao học Toán K8c Chuyên ngành Toán ứng dụng Trường Đại học Khoa học - Đại học Thái Nguyên 1 Mở đầu Lý thuyết trò chơi là một nhánh của toán học ứng dụng nghiên cứu về các tình huống, chiến thuật trong đó các đối thủ lựa chọn các chiến lược khác nhau để cố gắng làm tối đa thắng lợi cho bản thân. Ban đầu lý thuyết trò chơi được phát triển như một công cụ để nghiên cứu các hành vi kinh tế học, ngày nay lý thuyết trò chơi được sử dụng trong rất nhiều nghành khoa học từ sinh học, quân sự,triết học, chính trị học, đạo đức học...gần đây lý thuyết trò chơi thu hút được sự chú ý của các nhà khoa học máy tính do ứng dụng của nó trong trí tuệ nhân tạo và điều khiển học. Năm 1950 đến năm 1951 John Nash đã phát triển định nghĩa về một chiến thuật tối ưu cho trò chơi sau này được biết đến đó là "cân bằng Nash" năm 1994 ông cùng hai nhà kinh tế học khác đã đạt giải Nobel kinh tế vì những đóng góp trong lĩnh vực lý thuyết trò chơi. Trong khuôn khổ luận văn này tác giả trình bày một số khái niệm cơ bản về lý thuyết trò chơi và một số ứng dụng có tranh chấp trong kinh tế. Nội dung Luận văn gồm 2 chương • Chương 1.Trong chương này tác giả trình bày những khái niệm cơ bản về lý thuyết trò chơi như: trạng thái chấp nhận được, trạng thái cân bằng... Một trường hợp riêng quan trọng có ý nghĩa thực tiễn lớn được trình bày tương đối đầy đủ, đó là Trò chơi ma trận. Trò chơi ma trận cũng có hai loại, đó là trò chơi ma trận đơn và trò chơi ma trận kép. Khái niệm điểm yên trong chiến lược đơn và điểm yên trong chiến lược hỗn hợp trong trò chơi ma trận đơn. Cuối chương tác giả trình bày trò chơi ma trận kép. Khái niệm trạng thái Cân bằng Nash được nói tới. Đây là trạng thái rất đặc trưng của 2 trò chơi ma trận kép, nó cho ta cơ sở toán học để giải thích một số hiện tượng trong tự nhiên, trong kinh tế, quân sự, ngoại giao... • Chương 2. Trong chương này tác giả trình bày một số ví dụ và ứng dụng của lý thuyết trò chơi trong kinh tế và một số lĩnh vực khác thông qua các ví dụ cụ thể. Một trường hợp điển hình của trạng thái cân bằng Nash là tình thế lưỡng nan của hai nghi can. Rất nhiều trường hợp trong tự nhiên và trong xã hội đưa về bài toán này. Mặc dù đã cố gắng hết sức thực hiện luận văn nhưng chắc chắn luận văn vẫn còn thiếu sót. Tác giả kính mong sự góp ý của các thầy cô, các bạn và các anh chị đồng nghiệp để luận văn này được hoàn chỉnh. Thái Nguyên, tháng 11 năm 2016 Đàm Thị Dưỡng Học viên Cao học Toán K8c Chuyên ngành Toán ứng dụng Trường Đại học Khoa học - Đại học Thái Nguyên 3 Chương 1 Lý thuyết trò chơi 1.1 Khái niệm mở đầu Lý thuyết trò chơi là lý thuyết toán học mô tả và giải quyết các tình thế tranh chấp giữa các bên. Ví dụ 1.1. -) Chơi cờ, xổ số, thi đấu thể thao. -) Chiến tranh quân sự, cạnh tranh kinh tế, cạnh tranh giữa con người với thiên nhiên. Mỗi cuộc chơi có thể -) Có hai đấu thủ (trò chơi đôi); -) Có n đấu thủ (chơi tập thể). Định nghĩa 1.1. Cuộc chơi được gọi là đối kháng khi quyền lợi các bên tham gia trái ngược nhau. Phần thắng của mỗi người dẫn đến thiệt hại ít nhất một người khác. Cuộc chơi được gọi là không đối kháng, nếu một nhóm trong số những người chơi có lợi ích chung ngoài lợi ích riêng. Trong suốt cuộc chơi, mỗi bước đi, mỗi bên đều tìm cách chơi sao cho -) Phần thắng cho bản thân lớn nhất (kể cả trò chơi đối kháng và không đối kháng). -) Tổn thất cho bản thân nhỏ nhất (trò chơi đối kháng và không đối kháng). -) Tổn thất cho đối phương lớn nhất (trò chơi đối kháng). 4 Định nghĩa 1.2. [Chiến lược của người chơi] Là một tập hợp các quy tắc, các chọn lựa của mỗi người chơi được xác định duy nhất trong hành vi của người chơi ở mỗi bước chơi, phụ thuộc vào mỗi trạng thái xảy ra trong quá trình chơi. Nó phụ thuộc vào kết quả ở mỗi bước do hành vi của đối phương gây ra. Giả sử có N người chơi trong một trò chơi. Gọi Ti; i = 1...N là tập hợp mọi chiến lược có thể có của người chơi thứ i. Quá trình chơi thể hiện ở chỗ: người chơi i chọn cho mình một chiến lược ti ∈ Ti trong suốt quá trình chơi. Kết quả là đạt được trạng thái s, do đó người chơi thứ i thu được phần thắng là Vi (s). Trò chơi cũng có thể được tiến hành theo nhiều bước, mà ở bước thứ j người i có thể áp dụng chiến lược tij ∈ Ti , và người chơi i thu được phần thắng là Vi (sj ). Lại áp dụng chiến lược ti,j+1 ∈ Ti ở bước j + 1. Tổng hợp tất cả phần thắng của người chơi i tại mọi bước sẽ là phần thắng của người đó trong suốt quá trình chơi. Định nghĩa 1.3. [Trạng thái chấp nhận được] Trạng thái s trong trò chơi được gọi là chấp nhận được đối với người chơi i, nếu trong trạng thái đó ′ người chơi i đổi từ chiến lược đang sử dụng ti sang bất cứ chiến lược ti nào khác cũng không tăng thêm thắng lợi cho bản thân. Định nghĩa 1.4. [Trạng thái cân bằng] Trạng thái s được gọi là trạng thái cân bằng, nếu nó là trạng thái chấp nhận được với mọi người chơi. Khái niệm trạng thái cân bằng ở đây giống như khái niệm điểm Pareto trong kinh tế thị trường (hiệu quả Pareto xảy ra trong một phân bố xác định tài nguyên hoặc lợi ích giữa các thành viên, mà bất cứ một thành viên nào muốn tăng thêm lợi ích cho mình đều làm giảm lợi lợi ích của ít nhất một thành viên khác). Trong trò chơi không liên hiệp thì quá trình giải trò chơi chính là quá trình tìm trạng thái cân bằng. Định nghĩa 1.5. [Trò chơi với tổng hằng số] Trò chơi được gọi là trò chơi với tổng hằng số nếu tại mỗi bước chơi tổng phần thắng của tất cả người chơi không đổi và luôn bằng một số C nào đó. Nói cách khác, tồn tại số 5 C sao cho N X Vi (s) = C i=1 với mọi trạng thái s ∈ S (S là tập hợp mọi trạng thái có thể xảy ra). Trường hợp C = 0 được gọi là trò chơi với tổng không. Người ta cũng đã chứng minh được định lý sau đây (xem [4]). Định lý 1.1. Mọi trò chơi có tổng C 6= 0, luôn luôn đưa về trò chơi có tổng bằng không. Ví dụ 1.2. Có N doanh nghiệp, gọi C là mức thuế mà Nhà nước ấn định cho các doanh nghiệp này trong một kỳ ngân sách. Đây là trò chơi với tổng là hằng C , mà những người chơi là các doanh nghiệp mà Nhà nước ấn định mức thuế. Trò chơi có 2 người chơi là trò chơi mà người này thắng bao nhiêu thì người kia thua bấy nhiêu, vì vậy trò chơi mà chỉ có hai người chơi luôn luôn là trò chơi đối kháng. Định nghĩa 1.6. Chiến lược đơn là chiến lược xác định riêng biệt và người chơi có thể chọn với tần suất (xác suất) bằng 1. Định nghĩa 1.7. Chiến lược hỗn hợp là chiến lược kết hợp các chiến lược đơn, mà mỗi chiến lược đơn này được sử dụng với một tần suất (xác suất) nào đó. Ví dụ 1.3. Giả sử theo TCVN bóng đèn sợi đốt dùng cho gia đình có ba loại, đó là loại có công suất tiêu thụ 15 w, 30 w và 60 w. Một nhà máy sản xuất bóng đèn trong một năm đã sản xuất 10000 bóng loại 15w, 50000 bóng loại 30 w và 40000 bóng loại 60 w. Như vậy nhà máy có ba chiến lược đơn là sản xuất loại nào trong ba loại trên, mỗi loại là một chiển lược đơn. Nhà máy đã sản xuất 100000 bóng, tỷ lệ bóng 15w là p1 = 10%; tỷ lệ bóng 50000 5 40000 4 30 w là p2 = 100000 = 10 = 50%; tỷ lệ bóng 60 w là p3 = 100000 = 10 = 40%. Chiến lược hỗn hợp là (p1 , p2 , p3 ). 6 1.2 Trò chơi ma trận Trong mục này ta xét trò chơi chỉ có hai người chơi. Ta sẽ ký hiệu P1 là người chơi thứ nhất, P2 là người chơi thứ hai. Ký hiệu T1 và T2 tương ứng là tập hợp các chiến lược đơn của P1 và P2 . Định nghĩa 1.8. Trò chơi được gọi là trò chơi ma trận nếu thỏa mãn các điều kiện 1. Trò chơi có hai người chơi, 2. Mỗi người có hữu hạn chiến lược đơn, 3. Nếu người thứ nhất chọn chiến lược i trong tập T1 và người chơi thứ hai chọn j trong tập T2 thì người thứ nhất thắng người thứ hai một số tiền là aij . Giả sử người chơi thứ nhất có m chiến lược đơn, còn người chơi thứ hai có n chiến lược đơn, khi đó trò chơi hoàn toàn được xác định bởi ma trận  a11 a12  a21 a22 A =  ... ... am1 am2  ... a1n ... a2n  ... ...  , ... amn (1.1) trong đó aij biểu thị phần thắng của người chơi P1 (đồng thời cũng là phần thua của người chơi P2 ) nếu người chơi P1 chọn chiến lược đơn i, còn người chơi P2 chọn chiến lược đơn j . Ma trận A được gọi là ma trận thanh toán hoặc ma trận trả tiền, nghĩa là với cặp chiến lược hi, ji người chơi P2 phải trả cho người chơi P1 một lượng tiền là aij . Ma trận A còn được gọi là ma trận thắng của người chơi P1 đồng thời là ma trận thua của người chơi P2 với nghĩa như sau: -) Nếu aij > 0, thì người chơi P1 thắng, còn P2 thua theo nghĩa thông thường, P2 phải trả aij đơn vị tiền cho P1 . -) Nếu aij < 0, thì thực chất là người chơi thứ hai thắng còn người chơi thứ nhất thua theo nghĩa thông thường, P1 phải trả |aij | cho P2 . -) Nếu aij = 0, P1 hòa P2 . 7 Vì những lý do nêu trên, ta luôn luôn quy ước gọi người chơi thứ nhất là người thắng, người chơi thứ hai là người thua. Ví dụ 1.4. [Trò chơi oản tù tỳ (One Two Three)] (xem [3]) Trò chơi dân gian có hai người chơi, mỗi người có tập chiến lược đơn giống nhau T1 = T2 = {Giấy, Búa, Kéo}. Luật chơi là Giấy thắng Búa, Búa thắng Kéo, Kéo thắng Giấy, Giấy hòa Giấy, Búa hòa Búa, Kéo hòa Kéo. Hãy lập ma trận của trò chơi. Giải. P1 Giấy Búa Kéo Giấy 0 -1 1 P2 Búa 1 0 -1 Kéo -1 1 0 Bảng 1.1: Oản tù tỳ 0 1 −1 A = −1 0 1 1 −1 0 " # Ma trận trò chơi Oản Tù Tỳ Ví dụ 1.5. [Trò chơi chẵn lẻ] Hai người chơi, người thứ nhất có hai mảnh bìa, một mảnh ghi số 1, mảnh kia ghi số 2; người thứ hai có ba mảnh bìa, trên mỗi mảnh bìa lần lượt ghi các số 1; 2; 3. Khi có hiệu lệnh (sau tiếng hô 1, 2, 3 chẳng hạn) mỗi người chọn đặt lên bàn một mảnh bìa. Nếu tổng các số trên hai mảnh bìa là số lẻ thì P2 trả cho P1 số tiền là 3 U SD. Nếu tổng các số trên hai mảnh bìa là số chẵn thì P1 trả cho P2 lượng tiền là 2 U SD. Hãy lập ma trận của trò chơi. Giải. Mỗi người có một tập hợp các chiến lược đơn T1 = {1, 2}; T2 = {1, 2, 3}, mỗi người chơi có thể chọn trong các mảnh bìa của mình một mảnh, tất nhiên đã chọn mảnh này thì không chọn mảnh khác.   −2 3 −2 A = 3 −2 3 8 P1 1 2 1 -2 3 P2 2 3 3 -2 -2 3 Bảng 1.2: Trò chơi Chẵn lẻ Ví dụ 1.6. [Đối với xí nghiệp] Giả sử trên thị trường tồn tại 3 kiểu máy phục vụ cùng một mục đích với công suất như nhau. Nhà máy Z có khả năng sản xuất 3 kiểu máy đó. Qua thăm dò thị trường, biết rằng trong năm t cần N máy. Biết rằng chi phí sản xuất mỗi máy kiểu j là rj và đơn giá bán dự định là pj , j = 1...3. Đương nhiên là pj > rj . Hãy lập bài toán để có thể tìm chiến lược sản xuất tối ưu cho nhà máy Z theo nghĩa lợi nhuận cao nhất, khi chưa xác định được thị hiếu của thị trường đối với mỗi kiểu máy. Giải. Nếu máy kiểu j được thị trường chấp nhận αN cái (0 ≤ α ≤ 1), thì nhà máy Z thu được lợi nhuận N (αpj − rj ) đồng. Đây là một trò chơi, người chơi thứ nhất là nhà máy Z với 3 chiến lược thuần túy: sản xuất máy 1, máy 2 hay máy 3, còn người chơi thứ hai là mức nhu cầu sử dụng máy kiểu j trên thị trường là α. Để đơn giản, ta cho α nhận các giá trị: 0 (không sử dụng), 1/2 sử dụng một nửa và 1 (sử dụng toàn bộ máy kiểu j ). Người chơi thứ hai là thị trường có 6 chiến lược đơn là (1, 0, 0); (1/2 ,1/2, 0); (1/2, 0, 1/2); (0, 1/2, 1/2); (0, 0, 1); (0, 1, 0). Ma trận của trò chơi là  N (p1 − r1 ) A =  −N r2 −N r3 N ( 12 p1 − r1 ) N ( 21 p2 − r2 ) −N r3 N ( 12 p1 − r1 ) −N r2 N ( 21 p3 − r3 ) −N r1 N ( 21 p1 − r1 ) N ( 21 p3 − r3 ) −N r1 −N r2 N (p3 − r3 )  −N r1 N (p2 − r2 ) . −N r3 Ví dụ 1.7. [Trong nông nghiệp] Trong một vùng đất có thể trồng 2 loại cây là ngô và lúa. Năng suất bình quân của mỗi loại phụ thuộc vào lượng mưa, giả sử lượng mưa được chia làm hai loại là mưa ít và mưa nhiều. Theo kinh nghiệm cho thấy: ngô gặp mưa ít cho thu nhập 18 triệu/ha, gặp mưa nhiều cho thu nhập 14 triệu/1 ha; lúa gặp mưa ít cho 12 triệu/ha, gặp mưa nhiều cho 30 triệu/ha. Giải. Người chơi thứ nhất là nông dân, có 2 chiến lược đơn là trồng ngô hoặc lúa. Người chơi thứ hai là thời tiết, cũng có 2 chiến lược đơn là 9 mưa ít hoặc mưa nhiều. Ma trận thu nhập của nông dân là   12 30 A = 18 14 . Ví dụ 1.8. [Trong thương nghiệp] Một mặt hàng có n kiểu mẫu mã. Bài toán đặt ra cho cửa hàng là nhập kiểu nào thì tốt nhất, theo nghĩa nếu hàng hóa kiểu j bán được thì cửa hàng được lãi pj ; nếu không bán được, cửa hàng tổn thất qj do chi phí bảo quản. Giải Trong điều kiện nhu cầu và thị hiếu của người tiêu dùng không được xác định thì cuộc đụng độ giữa các kiểu nhập hàng vào cửa hàng tạo thành trò chơi mà người thứ nhất là cửa hàng, còn người chơi thứ hai là thị hiếu khách hàng. Mỗi bên đều có n chiến lược đơn, chiến lược i của người chơi thứ nhất là nhập kiểu i. Chiến lược j của người chơi thứ hai (thị trường) là tiêu thụ hàng hóa kiểu j . Ma trận phần thắng của cửa hàng là   p1 −q1 −q1 . . . −q1  −q p −q . . . −q  A =  . . .2 . . .2 . . .2 . . . . . .2 . −qn −qn . . . −qn pn 1.3 Chiến lược đơn trong trò chơi ma trận 1.3.1 Chiến lược maximin của người chơi thứ nhất Khi người chơi thứ nhất (P1 ) chọn hàng thứ i hay là chọn chiến lược i, phần thằng của người đó sẽ là một trong các số ai1 , ai2, ..., ain, tùy theo người chơi P2 chọn cột nào. Trường hợp xấu nhất cho P1 nhận được phần thắng là số αi = min {aij }. 1≤j≤n Với mỗi hàng thứ i, người chơi P1 sẽ có phần thắng đảm bảo là αi . Đại lượng vd = max {αi } = max min {aij } (1.2) 1≤i≤m 1≤i≤m 1≤j≤n là phần thắng mà người chơi P1 chắc chắn nhận được, nghĩa là nếu người chơi P1 chọn chiến lược như (1.2) thì phần thắng không nhỏ hơn vd bất kể 10 đối phương chọn chiến lược nào. vd gọi là giá dưới của trò chơi. Chiến lược đơn i0 mà với nó αi0 = vd = max {αi } 1≤i≤m gọi là chiến lược maximin của người chơi thứ nhất. 1.3.2 Chiến lược minimax của người chơi thứ hai Đối phó với chiến lược của P1 , người chơi P2 trước hết tìm xem nếu sử dụng chiến lược j , thì phần thua lớn nhất là bao nhiêu? Trường hợp xấu nhất cho P2 là bị thua một lượng βj = max {aij }. 1≤i≤m Hợp lý nhất là P2 tìm cách cực tiểu hóa phần thua lớn nhất của mình, tức là trong mọi chiến lược j = 1..n, tìm chiến lược j0 sao cho v t = βj0 = min {βj } = min max {aij }. 1≤j≤n 1≤j≤n 1≤i≤n (1.3) Đại lượng v t = βj0 gọi là giá trên của trò chơi. Chiến lược đơn j0 mà với nó v t = min {βj } 1≤j≤n gọi là chiến lược minimax của người chơi thứ hai. Đại lượng v t cũng là phần thua chắc chắn mà người chơi P2 đạt được, nghĩa là nếu người chơi P2 chọn chiến lược như (1.3) thì phần thua sẽ không vượt quá v t bất kể đối phương chọn chiến lược nào. Trong mọi ma trận (aij )m×n, luôn luôn có max min{aij } ≤ min max{aij }. i j j i (1.4) Định nghĩa 1.9. Nếu trò chơi mà có vd = v t = v tại hàng i0 , cột j0 , ta nói trò chơi có điểm yên ngựa trong các chiến lược đơn hay là ma trận có điểm yên ngựa là hi0 , j0 i; còn v được gọi là giá của trò chơi. Một số tính chất của điểm yên ngựa 11 1. Ma trận có điểm yên ngựa khi và chỉ khi tồn tại phần tử ai0 j0 vừa là số nhỏ nhất trong hàng i0 vừa là số lớn nhất trong cột j0 , tức là  aij0 ≤ ai0 j0 ∀i = 1...m; . (1.5) ai0 j0 ≤ ai0 j ∀j = 1...n 2. Mỗi ma trận có thể không có điểm yên ngựa, có thể có một hoặc có nhiều điểm yên ngựa. Trong trường hợp ma trận có nhiều điểm yên ngựa, thì giá trị các điểm đó bằng nhau. Từ tính chất trên, ta có quy tắc tìm điểm yên ngựa trong ma trận Bước 1. Trong mỗi cột của ma trận A tìm tất cả các phẩn tử lớn nhất, đánh dấu các phần tử đó. Bước 2. Trong mỗi hàng của ma trận A tìm tất cả các phần tử nhỏ nhất, đánh dấu vào các phần tử đó. Bước 3. Phần tử nào được đánh dấu hai lần, đó chính là điểm yên ngựa của ma trận A. Bất đẳng thức thứ nhất trong (1.5) cho thấy khi người chơi P2 đã chọn cột j0 , thì người chơi P1 dù chọn bất cứ hàng nào, phần thắng cũng không cao hơn khi chọn i0 . Bất đẳng thức thứ hai trong (1.5) cho thấy khi P1 đã chọn hàng i0 , thì P2 dù chọn bất cứ cột nào, phần thua cũng không nhỏ hơn khi chọn j0 . Điểm yên ngựa còn gọi là điểm cân bằng của trò chơi. Quá trình giải trò chơi chính là quá trình tìm điểm cân bằng. Trường hợp ma trận có điểm yên ngựa, thì điểm yên ngựa đó chính là trạng thái cân bằng (người chơi P1 không thể tăng phần thắng của bản thân còn người chơi P2 không thể giảm phần thua của bản thân). 1.4 Các chiến lược hỗn hợp trong trò chơi ma trận Xét trò chơi, với ma trận là  a11  a21 ... am1 a12 a22 ... am2 ... ... ... ...  a1n a23  .... amn 12 Ở mục trên ta đã xét trường hợp cả hai người chơi đều chỉ áp dụng chiến lược đơn, nghĩa là khi đã sử dụng hàng nào (cột nào), thì sử dụng hàng đó (cột đó) với tần suất 100%. Nếu chỉ sử dụng chiến lược đơn sẽ không giải thích được ví dụ 2.2 vì ở ví dụ này, người chơi P1 có phần thắng chắc chắn là 1, còn người chơi P2 lại có phần thua chắc chắn là 3. Mà trò chơi ma trận là trò chơi đối kháng, nghĩa là người này thua bao nhiêu thì người kia thắng bấy nhiêu. Người chơi P1 tìm cách nâng phần thắng của bản thân lên, và người chơi P2 tìm cách hạ phần thua của bản thân xuống. Muốn vậy cả hai người chơi phải tìm cách pha trộn các chiến lược đơn để được chiến lược gọi là chiến lược hỗn hợp: Xét trò chơi có ma trận trả tiền là A = [aij ]m×n. Người chơi P1 sử dụng hàng thứ nhất với tần suất p1 %, sử dụng hàng thứ hai với tần suất p2 %,..., sử dụng hàng thứ m với tần suất pm%, ta thấy 0 ≤ pi ≤ 1, ∀i = 1...m; p1 + p2 + ... + pm = 1. Từ đây ta có vector p = (p1 , p2 , ..., pm) Vector p gọi là vector chiến lược hỗn hợp của người chơi thứ nhất. Tương tự, người chơi thứ hai sử dụng cột thứ nhất với tần suất q1 %, sử dụng cột thứ hai với tần suất q2 %,...,sử dụng cột thứ n với tần suất qn %. Cũng nhận được 0 ≤ qj ≤ 1, ∀j = 1...n; q1 + q2 + ... + qn = 1. Từ đây ta cũng có vector q = (q1 , q2 , ..., qn). Vector q gọi là vector chiến lược hỗn hợp của người chơi thứ hai. Chú ý 1.1. Từ cách xây dựng vector chiến lược hỗn hợp như trên ta nhận thấy -) Nếu vector p có thành phần thứ i = 1, thì tất cả các thành phần còn lại phải bằng 0. Điều này được hiểu là người chơi P1 sử dụng 100% hàng i và không sử dụng các hàng còn lại. Lúc này chiến lược hỗn hợp thực chất là chiến lược đơn, vậy chiến lược đơn là trường hợp riêng của chiến lược hỗn hợp. Lập luận cũng tương tự đối với người chơi P2 . 13 -) Mỗi người chơi có hữu hạn chiến lược đơn nhưng có vô hạn chiến lược hỗn hợp. Mỗi người chơi có bài toán cho riêng mình, đó là 1. Bài toán của người chơi P1 là tìm chiến lược p∗ = (p∗1, p∗2, ..., p∗m) ∈ T1 sao cho cực đại thắng lợi của mình trong khi không có thông tin về sự lựa chọn chiến lược của P2 . 2. Bài toán của người chơi P2 là tìm chiến lược q∗ = (q1∗, q2∗ , ..., qn∗ ) ∈ T2 sao cho cực tiểu thắng lợi của P1 , đồng nghĩa với cực tiểu hóa phần thua của bản thân, trong khi không có thông tin về lựa chọn của P1 . 1.4.1 Phần thắng trung bình của người chơi thứ nhất Định nghĩa 1.10. Nếu người chơi P1 chọn vector chiến lược p, người chơi P2 chọn vector chiến lược q thì thắng lợi trung bình của người chơi P1 là M(p, q) = m X n X aij pi qj = a11 p1q1 + a12 p1q2 + ... + a1n p1qn i=1 j=1 + a21p2 q1 + a22p2 q2 + ... + a2n p2qn ........... + an1 pnq1 + an2 pn q2 + ... + ann pnqn = pAqT . (1.6) Chú ý 1.2. Phần thắng trung bình M(p, q) còn được viết dưới các dạng sau M(p, q) = (p, AqT ) = (pA, qT ) với các quy ước -) p, q, qT tùy từng trường hợp có thể hiểu là ma trận hoặc vector. -) Ma trận chỉ có một phần tử [a] được xem là số thực a. 14 Ví dụ 1.9. Xét trò chơi với ma trận   5 −3 1 −3 1 −5 . Giải. Người chơi P1 có hai chiến lược đơn p(1) = (1, 0) : p(2) = (0, 1) : chỉ sử dụng hàng 1 chỉ sử dụng hàng 2 và một tập vô hạn chiến lược hỗn hợp  T1 = {p = p1 .p(1) + p2 .p(2)0 ≤ p1, p2 ≤ 1, p1 + p2 = 1} Người chơi thứ hai có ba chiến lược đơn q(1) = (1, 0, 0) : chỉ sử dụng cột 1 q(2) = (0, 1, 0) : chỉ sử dụng cột 2 q(3) = (0, 0, 1) : chỉ sử dụng cột 3 và một tập vô hạn chiến lược hỗn hợp  T2 = {q = q1q(1) + q2q(2) + q3q(3) 0 ≤ q1 , q2, q3 ≤ 1; q1 + q2 + q3 = 1} 1.4.2 Nghiệm của trò chơi trong chiến lược hỗn hợp Định nghĩa 1.11. (Xem [3], trang 171-172) Nghiệm của trò chơi ma trận là cặp chiến lược hỗn hợp (p∗ , q∗ ) sao cho M(i, q∗) ≤ M(p∗ , q∗); ∀i = 1, 2, .., m (1.7) M(p∗ , j) ≥ M(p∗ , q∗); ∀j = 1, 2, ..., n (1.8) ở đây i = (0, 0, ..., 0, 1, 0...0) là vector đơn vị thứ i trong không gian Rm ; j = (0, 0, ..., 0, 1, 0...0) là vector đơn vị thứ j trong không gian Rn . Giá trị M(p∗ , q∗ ) được gọi là giá của trò chơi, ký hiệu là v . Bất đẳng thức (1.7) có nghĩa là khi P2 sử dụng chiến lược q∗ , thì P1 sử dụng bất cứ chiến lược nào cũng không làm cho phần thắng của P1 vượt quá v = M(p∗, q∗). Bất đẳng thức (1.8) có nghĩa là khi P1 sử dụng chiến lược p∗ thì P2 dù áp dụng bất cứ chiến lược nào cũng không làm cho phần thua của P2 nhỏ hơn v = M(p∗ , q∗ ). Cặp vector (p∗ , q∗ ) còn được gọi là điểm yên ngựa của trò chơi. Người ta đã chứng minh được định lý sau