Tiến Sĩ Một số thuật toán trong lý thuyết trò chơi

Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/

2

MỞ ĐẦU
Lý thuyết trò chơi là một nhánh của Toán học ứng dụng. Ngành này
nghiên cứu các tình huống chiến thuật trong đó các đối thủ lựa chọn các hành
động khác nhau để cố gắng làm tối đa kết quả nhận được. Lý thuyết trò chơi
nghiên cứu các quyết định được đưa ra trong một môi trường gồm có các đối
thủ tương tác với nhau và nghiên cứu cách lựa chọn hành vi tối ưu khi chi phí
và lợi ích của mỗi lựa chọn là không cố định mà phụ thuộc vào lựa chọn của
các cá nhân khác. Mặc dù còn là lĩnh vực khá mới mẻ, song lý thuyết trò chơi
được sử dụng trong nhiều ngành khoa học, từ Sinh học, Triết học, khoa học
máy tính, kinh tế học . cho đến chính trị, quân sự và văn hóa.
Trong các trường đại học, lý thuyết trò chơi mới chủ yếu được giới
thiệu sơ lược với một số ngành thuộc lĩnh vực kinh tế.
Mục đích của đề tài này nhằm nghiên cứu khái quát về lý thuyết trò
chơi, một số chiến lược trong trò chơi ma trận và minh họa bằng những ví dụ
cụ thể.
Kết cấu của luận văn ngoài phần mở đầu và kết luận được chia làm hai
chương như sau:
Chương 1: Trình bày sơ lược về lý thuyết trò chơi từ sự ra đời và phát
triển cũng như các lĩnh vực ứng dụng. Một số ví dụ và các khái niệm cơ bản.
Chương 2: Trình bày một số thuật toán trò chơi ma trận và minh họa
trên những ví dụ cụ thể.
Do những hạn chế về thời gian và điều kiện nghiên cứu cũng như những
khó khăn của bản thân nên luận văn chắc chắn còn nhiều khiếm khuyết.
Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/

3

Chương 1: SƠ LƯỢC VỀ LÝ THUYẾT TRÒ CHƠI
Chương này trình bày về lý thuyết trò chơi và xuất xứ của nó, các bài
toán cũng như các khái niệm và ứng dụng của lý thuyết trò chơi trong thực tế.
Các kiến thức trong chương được tham khảo và sử dụng trong các tài liệu:
Don Ross (2010), Games Theory.
Jim Ratliff (1997), Strategic form Games.
Fudenberg (1991), Drew and Jean Tirole: Game Theory, MIT Press.
1.1 Xuất xứ
Lý thuyết trò chơi là một nhánh của Toán học ứng dụng. Ngành này
nghiên cứu các tình huống chiến thuật trong đó các đối thủ lựa chọn các hành
động khác nhau để cố gắng làm tối đa kết quả nhận được. Việc phân tích các
tình huống cạnh tranh có hai mục tiêu. Mục tiêu thứ nhất là tìm hiểu được tại
sao các bên tham gia trò chơi trong các tình huống cạnh tranh đó lại ứng xử
như họ làm. Mục tiêu thứ hai có tính thực dụng hơn là có khả năng gợi ra cho
người chơi cách chơi cách chơi nào tốt nhất. Mục tiêu thứ nhất đặc biệt quan
trọng khi trò chơi ở mức rộng, có nhiều người chơi và có các quy tắc chơi
phức tạp. Theo đuổi mục tiêu thứ hai có thể cho phép mô tả cho từng người
chơi một chiến lược tốt nhất mà người ta có thể chơi.
Những thảo luận đầu tiên được biết đến về lý thuyết trò chơi xuất hiện
trong một lá thư viết bởi James Waldegrave vào năm 1713. Trong lá thư này,
Waldegrave đưa ra lời giải chiến thuật hỗn hợp minimax cho một trò đánh bài
hai người chơi Le Her. Chỉ đến khi sự xuất bản “Nghiên cứu về những Định
luật toán học của lý thuyết Tài sản” của Antoine Augustin Cournot vào năm
1838 thì những phân tích chung về lý thuyết trò chơi mới được theo đuổi.
Mặc dù những phân tích của Cournot là tổng quát hơn là của
Waldegrave, lý thuyết trò chơi chưa thật sự tồn tại như là một ngành duy nhất
cho đến khi John von Neumann xuất bản một loạt các bài báo vào năm 1928.
Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/

4

Những kết quả này sau này được mở rộng thêm ra trong cuốn sách xuất bản
năm 1944 “Lý thuyết trò chơi và các hành vi kinh tế” bởi von Neumann và
Oskar Morgenstern. Tác phẩm uyên thâm này chứa đựng phương pháp tìm
những lời giải tối ưu cho những trò chơi tổng bằng không với hai người chơi.
Trong suốt khoảng thời gian này, những tác phẩm về lý thuyết trò chơi chủ
yếu tập trung vào lý thuyết các trò chơi hợp tác, phân tích về những chiến
thuật tối ưu cho một nhóm các cá nhân, giả sử rằng họ có thể bảo đảm những
thỏa thuận giữ họ với những chiến thuật thích hợp.
Vào năm 1950, thảo luận đầu tiên của Prisoner's dilemma xuất hiện, và
một thí nghiệm được làm về trò chơi này tại công ty RAND. Vào khoảng
cùng thời gian đó, John Nash phát triển một định nghĩa về một chiến thuật
"tối ưu" cho các trò chơi với nhiều người chơi, và được biết đến như là cân
bằng Nash. Cân bằng này là đủ tổng quát, cho phép sự phân tích về trò chơi
không hợp tác thêm vào những trò chơi có hợp tác.
Lý thuyết trò chơi trải qua một thời gian sôi động trong những năm
1950, trong những năm đó những khái niệm về cốt lõi, dạng trò chơi bao quát,
trò chơi giả, trò chơi lặp, và giá trị Shapley được phát triển. Thêm vào đó,
những ứng dụng đầu tiên của lý thuyết trò chơi vào triết học và khoa học
chính trị diễn ra trong thời gian này.
Vào năm 1965, Reinhard Selten giới thiệu khái niệm lời giải của các
cân bằng lý tưởng của các trò chơi con, làm chính xác thêm cân bằng Nash.
Vào năm 1967, John Harsanyi phát triển các khái niệm thông tin hoàn toàn và
trò chơi Bayesian. Ông ta, cùng với John Nash và Reinhard Selten, đoạt giải
thưởng Nobel về kinh tế vào năm 1994.
Trong những năm 1970, lý thuyết trò chơi được áp dụng rộng rãi vào
sinh học, chủ yếu là do kết quả của các công trình của John Maynard Smith
và chiến lược tiến hóa bền vững của ông. Thêm vào đó, những khái niệm về
Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/

5

cân bằng liên quan, sự hoàn toàn rung tay, và kiến thức chung được giới thiệu
và phân tích.
Vào năm 2005, những lý thuyết gia trò chơi Thomas Schelling và
Robert Aumann đoạt giải thưởng Nobel về kinh tế. Schelling là về các mô
hình động, các ví dụ ban đầu của lý thuyết tiến hóa trò chơi. Aumann đóng
góp thêm vào trường cân bằng (equilibrium school), phát triển một cân bằng
làm thô đi những cân bằng liên quan nhau và phát triển các phân tích chi tiết
về giả sử của kiến thức chung.
Năm 2012, hai người Mỹ là Alvin Roth và Lloyd Shapley cùng được
trao giải Nobel về kinh tế nhờ những công trình về lý thuyết phân phối ổn
định và thực tiễn tạo lập thị trường, trên cơ sở sử dụng lý thuyết trò chơi và
thực nghiệm.
Ngày nay, trong cuộc sống của chúng ta có rất nhiều ví dụ liên quan đến
áp dụng lý thuyết trò chơi như:
- Chơi cờ, chơi bài, đánh bạc hoặc chơi xổ số khi nghiên cứu tần số xuất hiện
các con số.
- Thi đấu thể thao
- Chiến thuật, chiến lược quân sự
- Cạnh tranh kinh tế của các doanh nghiệp với nhau hoặc chiến lược sản xuất
khi nghiên cứu thị trường tiêu thụ.
- Cạnh tranh với thời tiết và nói chung với thiên nhiên trong sản xuất nông
nghiệp nói riêng hay trong nền kinh tế nói chung.
- Phương án vận chuyển trên các tuyến đường trong tình thế khẩn cấp với thời
tiết thay đổi. vvv
Từ đây ta có thể thấy rằng, lý thuyết trò chơi giờ đây đã được ứng dụng
rộng khắp trong tất cả các lĩnh vực từ văn hóa, chính trị, quân sự, kinh tế cho
đến nhiều ngành khác
Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/

6


Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/


MỤC LỤC

MỤC LỤC
LỜI CẢM ƠN . 1
MỞ ĐẦU . 2
Chương 1: SƠ LƯỢC VỀ LÝ THUYẾT TRÒ CHƠI 3
1.1 Xuất xứ 3
1.2 Một số bài toán . 6
1.2.1 Bài toán 1 . 6
1.2.2 Bài toán 2 . 8
1.3 Một số khái niệm . 10
Chương 2: MỘT SỐ THUẬT TOÁN TRÒ CHƠI . 14
2.1 Trò chơi ma trận 14
2.2 Các chiến lược trong trò chơi ma trận . 16
2.2.1 Các chiến lược thuần túy trong trò chơi ma trận 16
2.2.2 Các chiến lược hỗn hợp trong trò chơi ma trận 20
2.2.3 Lý thuyết trò chơi dưới dạng qui hoạch tuyến tính 32
2.2.4 Chiến lược từng bước và phương pháp Brown 37
KẾT LUẬN . 43
TÀI LIỆU THAM KHẢO . 44


Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/

1

LỜI CẢM ƠN

Sau một thời gian nghiên cứu tìm hiểu, em đã hoàn thành Luận văn Thạc
sỹ toán học chuyên ngành Toán ứng dụng với đề tài: “Một số thuật toán
trong lý thuyết trò chơi”.
Lời đầu tiên em xin bày tỏ lòng biết ơn sâu sắc tới Thầy giáo TS. Vũ
Mạnh Xuân đã tận tình hướng dẫn em trong suốt quá trình nghiên cứu và
thực hiện luận văn. Em cũng xin chân thành cảm ơn Quý thầy cô tham gia
giảng dạy,các thầy cô phòng đào tạo và cô Nguyễn Thị Thu Thủy trưởng khoa
Toán Tin trường Đại học Khoa học – Đại học Thái Nguyên đã hướng dẫn,
truyền đạt kiến thức, tạo mọi điều kiện giúp đỡ cho em trong suốt thời gian
theo học và thực hiện luận văn này.
Qua việc nghiên cứu và hoàn thành luận văn, em đã có thêm nhiều kiến
thức bổ ích trong chuyên môn cũng như phương pháp luận nghiên cứu khoa
học. Trong khuôn khổ của một luận văn, chắc chắn chưa đáp ứng được đầy đủ
những vấn đề đặt ra. Vì điều kiện nghiên cứu còn hạn chế, nên mặc dù đã cố
gắng rất nhiều nhưng luận văn không tránh khỏi những thiếu sót. Em rất
mong nhận được sự đóng góp ý kiến, phê bình quý báu của các nhà khoa học,
các thầy cô và các bạn đồng nghiệp.
Một lần nữa em xin chân thành cảm ơn !
Thái Nguyên, tháng 09 năm 2014
Học viên