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/

ĐẠI HỌC THÁI NGUYÊN

TRƢỜNG ĐẠI HỌC KHOA HỌC

PHẠM THỊ THU PHƢƠNG

MỘT SỐ THUẬT TOÁN

TRONG LÝ THUYẾT TRÒ CHƠI

Chuyên ngành: TOÁN ỨNG DỤNG

Mã số: 60.46.01.12

LUẬN VĂN THẠC SĨ TOÁN HỌC

NGƢỜI HƢỚNG DẪN KHOA HỌC

TS. VŨ MẠNH XUÂN

THÁI NGUYÊN– 2014

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

Phạm Thị Thu Phƣơng

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.